北京朝阳区地图高清版大图,双滦区seo整站排名,大学生个人简历电子版,教学网站模板下载目录 树的相关术语树家族二叉树霍夫曼树二叉查找树 BST平衡二叉树 AVL红黑树伸展树替罪羊树 B树B树B* 树 当谈到数据结构中的树时#xff0c;我们通常指的是一种分层的数据结构#xff0c;它由节点#xff08;nodes#xff09;组成#xff0c;这些节点之间以边#xff08… 目录 树的相关术语树家族二叉树霍夫曼树二叉查找树 BST平衡二叉树 AVL红黑树伸展树替罪羊树 B树B树B* 树 当谈到数据结构中的树时我们通常指的是一种分层的数据结构它由节点nodes组成这些节点之间以边edges相连。树的一个重要特性是它们具有一个根节点root它位于树的顶部并且每个节点都有一个父节点parent以及零个或多个子节点children。树结构是一种非线性存储结构存储的是具有“一对多”关系的数据元素的集合。 树的相关术语
根节点Root树的顶层节点它没有父节点是树的起点。父节点Parent一个节点的直接上级节点。子节点Children一个节点的直接下级节点。叶子节点Leaf没有子节点的节点称为叶子节点它们位于树的末端。深度Depth一个节点的深度指的是从根节点到该节点的唯一路径的边数。高度Height树的高度是指树中任意节点的最大深度。子树Subtree一个节点及其所有子孙节点构成的集合也是一个树。节点的度Degree一个节点拥有的子节点数目。树的度Degree of Tree树中节点的最大度数。层级Level根节点在第一层其子节点在第二层以此类推。兄弟节点Siblings具有相同父节点的节点称为兄弟节点。有序树与无序树如果树中的节点是按照一定的顺序排列的那么称它为有序树否则称为无序树。树家族 二叉树
二叉树的任意节点至多包含两棵子树。
二叉树遍历: 二叉树的遍历是指从二叉树的根结点出发按照某种次序依次访问二叉树中的所有结点使得每个结点被访问一次且仅被访问一次。二叉树的访问次序可以分为四种 前序遍历 中序遍历 后序遍历 层次遍历 满二叉树除了子结点之外的每一个结点都有两个孩子每一层(当然包含最后一层)都被完全填充。完全二叉树除了最后一层之外的其他每一层都被完全填充并且所有结点都保持向左对齐。严格二叉树除了叶子结点之外的每一个结点都有两个孩了结点。
霍夫曼树 霍夫曼树的构建过程是基于一个给定的字符集合每个字符都有一个权值通常是它在文本中出现的频率。构建霍夫曼树的目标是使得权值较大的字符在树中的深度相对较小从而实现了最优前缀编码。霍夫曼编码可以借助霍夫曼树实现。
二叉查找树 BST 若任意节点的左子树不空则左子树上所有节点的值均小于它的根节点的值若任意节点的右子树不空则右子树上所有节点的值均大于它的根节点的值任意节点的左、右子树也分别为二叉查找树没有键值相等的节点。
平衡二叉树 AVL 平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树同时平衡二叉树必定是二叉搜索树。 平衡二叉树是一棵相对平衡的树它的高度近似于 l o g 2 ( n ) log₂(n) log2(n)其中 n 是节点的数量。 平衡二叉树又称为AVL树得名于其发明者 Adelson-Velsky 和 Landis。 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 AVL树是一种特殊的BST树它满足以下额外的条件:
每个结点的左右子树的高度之差的绝对值平衡因子最多为1平衡因子 | 左子树高度 - 右子树高度 |
在一些情况下添加删除会打破AVL树的自平衡性。所以 AVL树定义了旋转操作, 在平衡因子大于等于2时, AVL树会旋转来调整树的结构, 来重新满足平衡因子小于2。
AVL树适合用于插入删除次数比较少但查找多的情况。
红黑树 红黑树和AVL树一样也是自平衡二叉查找树。 红黑树是每个节点都带有颜色属性的二叉查找树颜色或红色或黑色。在二叉查找树强制一般要求以外对于任何有效的红黑树我们增加了如下的额外要求:
节点是红色或黑色。根节点是黑色。每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
我们构建红黑树的过程是通过逐个插入新节点来完成的在插入节点时初始化根节点为黑节点随后插入子节点时初始为红色然后通过修改颜色和旋转节点来完成平衡最终使一棵子树完成平衡操作。
伸展树
伸展树是二叉查找树满足左子树的key根节点的右子树的key的特点。不保证树是平衡的但各种操作的平摊的复杂度是logn。从效率上上和平衡树的效率差不多。从编码复杂度上伸展树比红黑树和AVL简单了很多。 伸展树的思想二八原则 也就是把那些访问频率高的的字段尽可能移到离根节点近的位置所以每次访问节点都会通过各种旋转的方法将访问节点旋转到根节点。 替罪羊树
替罪羊树是计算机科学中一种基于部分重建的自平衡二叉搜索树。在替罪羊树上插入或删除节点的平摊最坏时间复杂度是O(log n)搜索节点的最坏时间复杂度是O(log n)。 在非平衡的二叉搜索树中每次操作以后检查操作路径找到最高的满足max(size(son_L),size(son_R))alpha*size(this)的结点重建整个子树。这样就得到了替罪羊树而被重建的子树的原来的根就被称为替罪羊节点。
替罪羊树替罪羊树是一棵自平衡二叉搜索树由ArneAndersson提出。替罪羊树的主要思想就是将不平衡的树压成一个序列,然后暴力重构成一颗平衡的树。 B树
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树或者是满足下列性质的树
根结点至少有两个子女每个非根节点所包含的关键字个数 j 满足 ⌈ m 2 ⌉ − 1 j m − 1 \left \lceil \frac{m}{2} \right \rceil - 1 j m - 1 ⌈2m⌉−1jm−1除根结点以外的所有结点不包括叶子结点的度数正好是关键字总数加1故内部子树个数 k 满足 ⌈ m 2 ⌉ k m \left \lceil \frac{m}{2} \right \rceil k m ⌈2m⌉km所有的叶子结点都位于同一层。
B树(B-Tree)是一种自平衡的树,它是一种多路搜索树并不是二叉的能够保证数据有序。同时它还保证了在查找、插入、删除等操作时性能都能保持在O(logn)为大块数据的读写操作做了优化,同时它也可以用来描述外部存储(支持对保存在磁盘或者网络上的符号表进行外部查找)
B树 B树是在B树的基础上又一次的改进其主要对两个方面进行了提升一方面是查询的稳定性另外一方面是在数据排序方面更友好。
B树构建规则
B树的非叶子节点不保存具体的数据而只保存关键字的索引而所有的数据最终都会保存到叶子节点。因为所有数据必须要到叶子节点才能获取到所以每次数据查询的次数都一样这样一来B树的查询速度也就会比较稳定而B树的查找过程中不同的关键字查找的次数很有可能都是不同的有的数据可能在根节点有的数据可能在最下层的叶节点。B树叶子节点的关键字从小到大有序排列左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的。非叶子节点的子节点数关键字数另一种为非叶节点的关键字数子节点数-1。这里有两种算法的实现方式虽然他们数据排列结构不一样但其原理还是一样的Mysql 的B树是用第一种方式实现。
B树与B树的比较 B树查询速度更稳定B所有关键字数据地址都存在叶子节点上所以每次查找的次数都相同所以查询速度要比B树更稳定。 B树天然具备排序功能B树所有的叶子节点数据构成了一个有序链表在查询大小区间的数据时候更方便数据紧密性很高缓存的命中率也会比B树高。 B树全节点遍历更快B树遍历整棵树只需要遍历所有的叶子节点即可而不需要像B树一样需要对每一层进行遍历这有利于数据库做全表扫描。
B树相对于B树的优点是如果经常访问的数据离根节点很近而B树的非叶子节点本身存有关键字和数据所以在查询这种数据检索的时候会要比B树快。
B* 树
B*树又是对B数的再一次改进。
两者有以下两方面的不同
首先是关键字个数限制问题B树初始化的关键字初始化个数是 ⌈ m 2 ⌉ \left \lceil \frac{m}{2} \right \rceil ⌈2m⌉b*树的初始化个数为 ⌈ 2 m 3 ⌉ \left \lceil \frac{2m}{3} \right \rceil ⌈32m⌉B树节点满时就会分裂而B*树节点满时会检查兄弟节点是否满因为每个节点都有指向兄弟的指针如果兄弟节点未满则向兄弟节点转移关键字如果兄弟节点已满则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来。
