本篇文章为shaoyuanhangyes.github.io/Binary_Tree
的拆分后续 将继续讲述B-Tree
与红黑树
B+树
的区别
BST复习
Binary Search Tree
二叉搜索树 or 二叉查找树
BST的特点为 某一节点的值 总是大于其任意左侧子节点的值 总是小于其任意右侧子节点的值
这么设计的目的是为了提高查找的性能 使得查找效率接近于二分查找
但是 当二叉树高度和二叉树节点数量相同的时候 即
1 | 6 |
在此BST中查找元素1 需要查找6次
它已经退化为一个单向链表 其查找效率就会很低 最坏情况下的时间复杂度为O(H) H为二叉树的高度
若变更为如下的存储方式呢
1 | 3 |
此时查询元素1 只需要查找3次 查找效率得到提高
可以得出结论BST的查找效率 取决于树的高度 因此只要能保持树的高度最小 就能保证BST的查找效率
因此 就需要引入平衡二叉树的概念
AVL复习
AVL 平衡二叉查找树 简称平衡二叉树
AVL的任何一个节点的左右子树高度差不能超过1
1 | 3 |
1 | 4 |
平衡因子
为能够准确判断某个二叉搜索树是否为平衡二叉树 引入平衡因子的概念
二叉树中某节点的左子树和右子树的高度(深度)差值即为该节点的平衡因子BF(Balance Factor)
当某个树的平衡因子为 -1
或0
或1
时 说明此树为平衡二叉树
当平衡二叉树不平衡时 就需要对此二叉树进行平衡调整
调整的策略为 旋转最小失衡子树
最小失衡子树的定义为 在新插入的节点向上查找 以第一个平衡因子绝对值超过1的节点为root的子树 为最小失衡子树
一个失衡的树 是有可能有多个子树同时失衡的 而我们只需要调整最小的不平衡子树 就可以将不平衡的树调整为平衡的树
旋转最小失衡子树有两种旋转方式 左旋 右旋
旋转的目的是减少高度 通过降低树的高度来实现平衡 哪边的树高 就把哪边的树向上旋转
旋转
针对不平衡的二叉搜索树 共总结出四个常用结论 分别为 LL
RR
LR
RL
右旋
1 | 3 2 |
左旋
1 | 1 2 |
1 | 4 4 3 |
1 | 2 2 3 |
红黑树复习
虽然AVL的查找效率很高 但是对AVL进行插入和删除操作的时候需要大量的自旋来满足平衡要求 而AVL的旋转特别的麻烦 因此 引入了一个新的概念 ——RBT红黑树
红黑树是一个自平衡的二叉查找树 RBT的平衡性没有AVL那么强 并且在插入和删除操作时的旋转操作也没有AVL那么多
因此 在插入和删除较少 但查找更为频繁的情况下 AVL会是更好的选择
相反 在插入和删除较多 查找没那么频繁的情况下 RBT会是更好的选择
性质
结点是红色或黑色
根结点一定是黑色的
每一个叶子结点(NIL)都是黑色
每个红色结点的两个子结点都是黑色
没有两个相邻的红色结点(红色结点不能有红色父结点和红色子结点 并没有说不能有两个连续的黑结点)
任意一个结点到其每个叶子结点(NIL)的路径都包含相同数目的黑色结点 简称为黑高
红黑树的高度 一定小于 $2·log_2(n+1)$
由此可见 RBT和AVL的时间复杂度大致接近
插入新结点
- 若一个树为空树 则插入的新结点必是黑色的
- 若一个树不为空 则插入的新结点总是先当作红色结点
- 若新插入的结点的父结点是黑色的 则符合要求 不做修改
- 若新插入的结点的父结点是红色的 则需要检查父结点的兄弟结点是否也为红色 若为红色 则将父结点及其兄弟结点一起变色(变黑) 然后继续父结点的父结点也要变色 (除非它是根结点可以不用变色 因为根结点必是黑色)
- 若新插入的结点的父结点是红色的 则需要检查父结点的兄弟结点是否也为红色 若不为红色或没有兄弟结点 则需要先进行相应的自旋之后 再按照4的要求变色
删除新结点
- 要删除的结点没有子结点
若是红色结点 直接删除即可
若是黑色结点 需要进行平衡操作 - 要删除的结点有一个子结点