B-Tree

本篇文章为shaoyuanhangyes.github.io/Binary_Tree的拆分后续 将继续讲述B-Tree红黑树 B+树 的区别

BST复习

Binary Search Tree 二叉搜索树 or 二叉查找树

BST的特点为 某一节点的值 总是大于其任意左侧子节点的值 总是小于其任意右侧子节点的值

这么设计的目的是为了提高查找的性能 使得查找效率接近于二分查找

但是 当二叉树高度和二叉树节点数量相同的时候 即

1
2
3
4
5
6
7
8
9
10
11
          6
/
5
/
4
/
3
/
2
/
1

在此BST中查找元素1 需要查找6次

它已经退化为一个单向链表 其查找效率就会很低 最坏情况下的时间复杂度为O(H) H为二叉树的高度

若变更为如下的存储方式呢

1
2
3
4
5
    3  
/ \
2 5
/ / \
1 4 6

此时查询元素1 只需要查找3次 查找效率得到提高

可以得出结论BST的查找效率 取决于树的高度 因此只要能保持树的高度最小 就能保证BST的查找效率

因此 就需要引入平衡二叉树的概念

AVL复习

AVL 平衡二叉查找树 简称平衡二叉树

AVL的任何一个节点的左右子树高度差不能超过1

1
2
3
4
5
    3  
/ \
2 5
/ / \
1 4 6 这就是一个平衡二叉树
1
2
3
4
5
6
7
      4
/ \
3 5
/ / \
2 6 7
/
1 这不是平衡二叉树 因为节点3的左子树不是平衡二叉树

平衡因子

为能够准确判断某个二叉搜索树是否为平衡二叉树 引入平衡因子的概念

二叉树中某节点的左子树和右子树的高度(深度)差值即为该节点的平衡因子BF(Balance Factor)

当某个树的平衡因子为 -101时 说明此树为平衡二叉树

当平衡二叉树不平衡时 就需要对此二叉树进行平衡调整

调整的策略为 旋转最小失衡子树

最小失衡子树的定义为 在新插入的节点向上查找 以第一个平衡因子绝对值超过1的节点为root的子树 为最小失衡子树

一个失衡的树 是有可能有多个子树同时失衡的 而我们只需要调整最小的不平衡子树 就可以将不平衡的树调整为平衡的树

旋转最小失衡子树有两种旋转方式 左旋 右旋

旋转的目的是减少高度 通过降低树的高度来实现平衡 哪边的树高 就把哪边的树向上旋转

旋转

针对不平衡的二叉搜索树 共总结出四个常用结论 分别为 LL RR LR RL

右旋

1
2
3
4
5
    3                                  2
/ / \
2 此为LL型 旋转后变为 1 3
/
1

左旋

1
2
3
4
5
1                                  2
\ / \
2 此为RR型 旋转后变为 1 3
\
3
1
2
3
4
5
  4                       4                   3
/ / / \
2 此为LR型 先左旋变为 3 再经右旋变为 2 4
\ /
3 2
1
2
3
4
5
2                        2                        3
\ \ / \
4 此为RL型 先右旋旋变为 3 再经左旋变为 2 4
/ \
3 4

红黑树复习

虽然AVL的查找效率很高 但是对AVL进行插入和删除操作的时候需要大量的自旋来满足平衡要求 而AVL的旋转特别的麻烦 因此 引入了一个新的概念 ——RBT红黑树

红黑树是一个自平衡的二叉查找树 RBT的平衡性没有AVL那么强 并且在插入和删除操作时的旋转操作也没有AVL那么多

因此 在插入和删除较少 但查找更为频繁的情况下 AVL会是更好的选择
相反 在插入和删除较多 查找没那么频繁的情况下 RBT会是更好的选择

性质

结点是红色或黑色
根结点一定是黑色的
每一个叶子结点(NIL)都是黑色
每个红色结点的两个子结点都是黑色
没有两个相邻的红色结点(红色结点不能有红色父结点和红色子结点 并没有说不能有两个连续的黑结点)
任意一个结点到其每个叶子结点(NIL)的路径都包含相同数目的黑色结点 简称为黑高

红黑树的高度 一定小于 $2·log_2(n+1)$
由此可见 RBT和AVL的时间复杂度大致接近

插入新结点

  1. 若一个树为空树 则插入的新结点必是黑色的
  2. 若一个树不为空 则插入的新结点总是先当作红色结点
  3. 若新插入的结点的父结点是黑色的 则符合要求 不做修改
  4. 若新插入的结点的父结点是红色的 则需要检查父结点的兄弟结点是否也为红色 若为红色 则将父结点及其兄弟结点一起变色(变黑) 然后继续父结点的父结点也要变色 (除非它是根结点可以不用变色 因为根结点必是黑色)
  5. 若新插入的结点的父结点是红色的 则需要检查父结点的兄弟结点是否也为红色 若不为红色或没有兄弟结点 则需要先进行相应的自旋之后 再按照4的要求变色

删除新结点

  1. 要删除的结点没有子结点
    若是红色结点 直接删除即可
    若是黑色结点 需要进行平衡操作
  2. 要删除的结点有一个子结点
End of reading! -- Thanks for your supporting