常见的几种树小知识

这篇文章的出现，主要是因为在复习数据库的时候，涉及到了b树和b+树，再加上之前复习多路复用的时候也会涉及到红黑树，所以就想把这几种树统统总结一下，做一个知识点的概括。

1. 二叉查找树

要了解B树，B+树和红黑树首先要了解二叉查找树，二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

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

mOk8AA.png

中序遍历二叉查找树可得到一个节点值的有序序列。
二叉搜索树在多次插入后可能会退化成一个线性链表。

2. B树

一颗m阶的B树定义如下：：

• 每一个节点最多有 m 个子节点
• 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
• 如果根节点不是叶子节点，那么它至少有两个子节点
• 有 k 个子节点的非叶子节点拥有 k − 1 个键
• 所有的叶子节点都在同一层

3个子节点，2个键的B树

2.1 模拟查找过程

假如说我们要查找10这个数字：

• 1. 从根节点发现，10小于17，要走P1节点（磁盘块2）
• 2. 10大于8，小于12，走P2节点（磁盘块6）
• 3. 在磁盘块6上面找到了10
     如果用其存储数据，每一个块节点都是一个磁盘块。

3. B+树

B+树的定义各有不同，一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。

B+树的性质：

• 1）B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

• 2）B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

• 3） m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

• 4）内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

• 5）每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

(2)，(5)是B+树用来做INNODB索引数据结构的重要原因。

3阶B+树

查找原理和上面B树的类似，但是要记住。只有叶子节点存储了真实数据，内部节点再真实也只是存储了索引而已。

4. 红黑树：

1. 是一种自平衡二叉查找树(红黑树严格来说并不遵守平衡二叉树的定义，其左右子树的高度差可以超过1)， 可以在O(logn)时间内完成查找，插入和删除，这里的n是树中元素的数目。

• 红黑树的五个性质：
  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点都是黑色的空节点（NIL节点）。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
• 这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

2. 红黑树调整的方法有两种：变色和旋转，旋转又分为左旋和右旋。

• 左旋：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
  n9l3xP.png
• 右旋：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
  n9lDx0.png

2. 红黑树比AVL树的优势在哪？

• 查找显然，avl树要比红黑树更平衡，因此avl树的查找效率更高。
• 插入不论是avl树还是红黑树，旋转的时间复杂度都是O(1)对于avl树，旋转的时候，需要找到第一个不平衡节点，这就需要我们维护一个平衡因子，每一次插入，旋转，删除等操作，都要更新从跟节点到被修改节点这个路径上的平衡因子，最差情况下，需要O(logn)的时间复杂度，对于红黑树，除了旋转外，最差情况下也需要O(logn)的时间复杂度来调整平衡，注意这只是极端情况下，比如父节点和伯父节点都是红色，曾祖父节点也是红色，这个时候，就要递归的去平衡父节点，然而，采用自顶向下的方法（就是如果一个节点的两个子节点都是红色，就把这个节点变成红色，它的两个子节点变成黑色），减少了多次旋转操作，但也使得调整颜色的操作时间复杂度最差情况下是O(logn)。但这仅仅是很少的情况，所以红黑树的插入操作统计上比avl树要好
• 删除对于avl树，删除意味着某个子树深度减少，这个时候，我们找到第一个不平衡的点，像插入操作那样进行旋转，使得子树平衡，然后，递归的使它的祖先节点也平衡。对于红黑树，也是只有个别情况才会递归平衡父节点，它发生在：兄弟节点是黑色，两个侄儿也是黑色。当兄弟节点是红色的时候，转化为兄弟节点是黑色的情况处理，当两个侄儿有红色节点的时候，则在常数时间内就可以达到平衡。所以，删除操作红黑树的平均效率也比avl树高。

B树B+树这么好，为什么还要用红黑树

一般都是在内存操作或者数据量不大的时候采用红黑树，因为红黑树没有索引节点，会节省内存。如果数据量很大，就像是数据库那样，还是需要使用b+树的。