【数据结构】树家族

当谈到数据结构中的树时，我们通常指的是一种分层的数据结构，它由节点（nodes）组成，这些节点之间以边（edges）相连。树的一个重要特性是它们具有一个根节点（root），它位于树的顶部，并且每个节点都有一个父节点（parent）以及零个或多个子节点（children）。树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

树的相关术语

根节点（Root）：树的顶层节点，它没有父节点，是树的起点。父节点（Parent）：一个节点的直接上级节点。子节点（Children）：一个节点的直接下级节点。叶子节点（Leaf）：没有子节点的节点称为叶子节点，它们位于树的末端。深度（Depth）：一个节点的深度指的是从根节点到该节点的唯一路径的边数。高度（Height）：树的高度是指树中任意节点的最大深度。子树（Subtree）：一个节点及其所有子孙节点构成的集合，也是一个树。节点的度（Degree）：一个节点拥有的子节点数目。树的度（Degree of Tree）：树中节点的最大度数。层级（Level）：根节点在第一层，其子节点在第二层，以此类推。兄弟节点（Siblings）：具有相同父节点的节点称为兄弟节点。有序树与无序树：如果树中的节点是按照一定的顺序排列的，那么称它为有序树，否则称为无序树。

树家族

二叉树

二叉树的任意节点至多包含两棵子树。

二叉树遍历:
二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。二叉树的访问次序可以分为四种：
前序遍历 中序遍历 后序遍历 层次遍历

霍夫曼树

霍夫曼树的构建过程是基于一个给定的字符集合，每个字符都有一个权值（通常是它在文本中出现的频率）。构建霍夫曼树的目标是使得权值较大的字符在树中的深度相对较小，从而实现了最优前缀编码。霍夫曼编码可以借助霍夫曼树实现。

二叉查找树 BST

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

平衡二叉树 AVL

平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。
平衡二叉树是一棵相对平衡的树，它的高度近似于 $lo{g}_2(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 满足：$\lceil \frac{m}{2}\rceil -1<=j<=m-1$；
• 除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：$\lceil \frac{m}{2}\rceil <=k<=m$；
• 所有的叶子结点都位于同一层。
  

B树(B-Tree)是一种自平衡的树,它是一种多路搜索树（并不是二叉的），能够保证数据有序。同时它还保证了在查找、插入、删除等操作时性能都能保持在O(logn)，为大块数据的读写操作做了优化,同时它也可以用来描述外部存储(支持对保存在磁盘或者网络上的符号表进行外部查找)

B+树

B+树是在B树的基础上又一次的改进，其主要对两个方面进行了提升，一方面是查询的稳定性，另外一方面是在数据排序方面更友好。

B+树构建规则：

• B+树的非叶子节点不保存具体的数据，而只保存关键字的索引，而所有的数据最终都会保存到叶子节点。因为所有数据必须要到叶子节点才能获取到，所以每次数据查询的次数都一样，这样一来B+树的查询速度也就会比较稳定，而B树的查找过程中，不同的关键字查找的次数很有可能都是不同的（有的数据可能在根节点，有的数据可能在最下层的叶节点）。
• B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的。
• 非叶子节点的子节点数=关键字数；另一种为非叶节点的关键字数=子节点数-1。这里有两种算法的实现方式，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现。

B树与B+树的比较：

1. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定。

2. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

3. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字和数据，所以在查询这种数据检索的时候会要比B+树快。

B* 树

B*树又是对B+数的再一次改进。

两者有以下两方面的不同：

• 首先是关键字个数限制问题，B+树初始化的关键字初始化个数是$\lceil \frac{m}{2}\rceil$，b*树的初始化个数为$\lceil \frac{2m}{3}\rceil$
• B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来。