网站类网站开发教程,WordPress获取评论内容,专业网站定制报价,佳木斯seo一、树是什么#xff1f;
有根有枝叶便是树#xff01;根只有一个#xff0c;枝叶可以有#xff0c;也可以没有#xff0c;可以有一个#xff0c;也可以有很多。
就像这样#xff1a;
嗯#xff0c;应该是这样#xff1a; 二、一些概念
1、高度
树有多高#x…一、树是什么
有根有枝叶便是树根只有一个枝叶可以有也可以没有可以有一个也可以有很多。
就像这样
嗯应该是这样 二、一些概念
1、高度
树有多高嗯我一米八三
树的高度怎么算
高度是啥就是从下往上到最顶端从叶节点到根节点。
从每个叶节点开始一个节点一个节点往上数数到根节点最长的那个数就是数的高度。叶节点起始为0.
上面这个树的高度是4。 2、深度
深度顾名思义就是从上往下到最低端从根节点到叶节点。
从根开始一个节点一个节点往下数数到每个叶子节点最长的那个数就是数的深度。根节点的起始为0.
上面这个树的深度是4。 对比上面的高度看到了哈数值是一样的
3、层
一层是什么呢。就是横向的同一高度的所有节点凑一块儿就是一层。
像下面一条线连接了第二层所有的节点 三、二叉树的遍历
二叉树是什么
二叉树就是每个节点最多有两个分叉子节点。
遍历是什么意思
遍历就是一个树的所有节点都点一遍那么既然要点一遍总归要遵循一个特定的顺序不然乱来的话总会可能漏一个或者多一个。
像下面这棵树 1、前序遍历
顺序中左右
中 6 - 左中 5 - 左 2 - 右 3 - 右中 7 - 右 8
结果就是6、5、2、3、7、8。
2、中序遍历
顺序左中右
左 2 - 中 5 - 右 3 - 中 6 - 右中 7 - 右 8
结果就是 2、5、3、6、7、8。
3、后序遍历
顺序左右中
左 2 - 右 3 - 中左 5 - 右 8 - 中右 7 - 中 6
结果就是2、3、5、8、7、6.
这个顺序其实很容易混乱。想要记得牢只需要一点
【前、中、后】前为左右为后哪个顺序遍历那么哪个节点就会顺序居中其它的节点靠左的居前。
节点的巡查是从根节点出发从上到下从左至右巡查每个节点及其子点巡查完毕后再跳出到其它节点。
4、附加层序遍历
层序遍历很简单就是从上到下一层一层的收拢节点。
第一层 6 - 第二层 5、7 - 第三层 2、3、8
结果就是6、5、7、2、3、8.
四、树能干什么
树能盖房子
没错树通常用来搭建存储数据的房子。
数据存储是对数据的持久化保存针对数据的操作包括读和写。不过无论是读还是写都离不开对数据的检索操作。
1、B树
之前文章介绍过B树及在数据库存储方面的应用
你好我是B树
MySQL InnoDB 是怎么使用 B 树存数据的
B 树即balance tree。其结构及节点数据分布遵循特定的规则。
B 树的算法运行时间通常由它所执行的【磁盘读写操作次数】决定所有一般会一次尽可能的读写更多的信息。一个B树节点通常和一个完整的磁盘页大小相同所以磁盘页的大小限制了一个B树节点所能包含孩子节点的个数。
B 树每个节点会包含多少个分支称之为分支因子。分支因子越大B 的高度越低查找关键字所需的磁盘存取次数越少查询时间越短。这也是为什么会推崇使用B树结构来作为数据底层存储。
2、二叉搜索树
二叉搜索树是以一棵二叉树来组织数据存储每个节点除了包含数据本身外还包括指向左节点、右节点及父节点的指针即key、left、right、p。其中存储数据需满足左中右非降序存储即left.key key right.key。
左中右是不是很熟悉就是我们上面讲到过的【中序遍历】顺序。【中序遍历】输出的话整个数列会是非降序排序数列。
搜索树结构通常支持包括查找最大值最小值插入删除等操作。嗯这些操作是不是又很熟悉总之就是一个【日常操作】。
二叉搜索树上的操作时间和它的高度成正比对于n节点二叉树通常最坏运行时间为O(lgn)为什么是O(lgn)呢这个需要推导先记住就行了这个就是树元素随机分步的情况下的结果。极端情况下一条链从根到叶的话时间固定就是O(n)了。就像下面这个棵树 3、红黑树
红黑树也是一个二叉搜索树。那为什么会需要这么一棵树呢
就是为了避免上面哪种极端或者接近极端情况的出现。它可以【保证最坏的情况下操作时间复杂度为O(lgn)】。
对的是保证那怎么保证呢当然是通过维持红黑树本身的结构特点来实现。
我们上面及到过二叉搜索树节点包含的数据红黑树会在其基础上增加一个存储位来表示节点的颜色红或者黑。通过【对任何一条从根到叶子节点的简单路径上的各个节点颜色进行约束】来确保【没有一路径会比其它路径长2倍】。
红黑树的特点 a)【节点要么红要么黑】 b)【根节点是黑的】 c)【叶节点是黑的】 d)【如果一个节点是红色的那么它的子节点是黑色的】 e)【对任何一个节点从该节点到其所有后代叶节点的简单路径上的黑节点数据是相同的】
这里有个点需要强调一下红黑树里所说的叶子节点指的是【外部节点】也就是不包含 key 的节点。
黑高从某个节点到达其叶节点的【任何一个参考e】简单路径上的黑色节点个数称之为黑高。红黑树的黑高即为其根节点的黑高。
一颗有 n 个内部节点的红黑树的高度至多为 2lgn1也即我们前面说的能够保证最坏的情况下操作时间复杂度为O(lgn)。
红黑树有哪些应用呢
最常见的就是 HashMap了用于解决存储元素哈希冲突当链表元素个数超过8时即转为红黑树。
