红黑树的定义
红黑树是特殊的二叉搜索树, 拥有自平衡的能力, 解决了BST树有可能退化成单链表的情况, 效率良好, 可以在O(log N)时间内完成查找, 删除, 添加. 红黑树应用很广泛, 主要用来存储有序的数据, STL 中的 set, map 等的内部实现就是红黑树
红黑树较之普通BST树的每个结点增加了颜色的属性, 其标准如下:
- 所有结点要么是红色, 要么是黑色
- 根结点是黑色的
- 叶子结点都是黑色的空结点
- 如果一个结点是红色, 那么它的左右子结点都是黑的(即从叶子结点到根结点的路径上不会有两个连续的红色结点)
- 从任一结点到其每个叶子结点的所有路径上都包含了相同数目的黑色结点
红黑树叶子结点为黑色, 指的是传统意义上的叶子结点的左右空结点, 下文中画图时都将省略画出叶子结点
红黑树的上述性质中的 4 5 性质, 确保了任一结点到其所有叶子结点的路径都包含了相同数目的黑色结点
这也意味着: 任意结点到其每个叶子结点路径最长不会超过最短路径的 2 倍
红黑树的插入操作
既然红黑树本质是二叉搜索树, 其插入操作与其基本类似, 只不过红黑树需要在插入后进行调整来满足红黑树的性质
新插入的结点是红点的, 因为如果插入的是结点为黑色, 会直接改变某一条路径上黑色结点的数量
我们需要做的就是在插入结点后仍让其符合上述性质 4 5,
- 如果一个结点是红色, 那么它的左右子结点都是黑的(即从叶子结点到根结点的路径上不会有两个连续的红色结点)
- 从任一结点到其每个叶子结点的所有路径上都包含了相同数目的黑色结点
红黑树的自平衡
我们在对红黑树进行插入和删除操作时, 可能会导致破坏红黑树的性质, 这时我们需要对结点进行变色或者旋转, 继续保持他的性质或平衡
- 变色
将结点的颜色从红变黑或者反之来重新符合红黑树规则 - 旋转
红黑树的旋转操作分为左旋和右旋, 和AVL树中"右右"和"左左"情况下的旋转操作是一样的
红黑树的插入删除有很多case, 什么情况下采用变色, 什么情况下旋转要根据情况而定
case 1
新插入的结点为根节点, 直接将其颜色变为黑色
case 2
新插入的结点是黑色的, 无需做任何调整
case 3
新插入当前结点 D, 父结点 B 为红, 叔叔结点 C 为红, 这时不满足红结点左右子结点为黑, 所以我们进行依次将 B C A 结点变色, 并将当前结点指向 A, 这时重新满足红黑树性质
当 A 结点不是根节点时, 我们需要进行递归向上调整
至于结点 D 是 B 的左子还是右子, B C 是 A 的左子还是右子都是对称的情况, 视为同一类
case 4
当前节点 D 为红, 父结点 B 为红, 叔叔结点 C 为黑, D 为 B 的右子, 这时我们需要将当前结点指向 B, 并进行左旋
case 5
当前结点 B 为红, 父结点 D 为红, 叔叔结点为黑, B 为 D 的左子, 这时我们要将父结点变为黑, 祖父结点变为红, 并以祖父节点为支点进行右旋
描述完这五种情况, 我们发现第一 二种相对简单, 而第四第五种情况又都是针对第三种情况插入新节点后的一系列修补操作.
红黑树与平衡二叉树
AVL树每个结点都有一个平衡因子, 它必须小于2, AVL树通过它来严格控制平衡, 所以在插入删除结点时要通过一次或多次的旋转来重新平衡
红黑树并不追求“完全平衡”, 它只要求部分地达到平衡要求, 降低了对旋转的要求, 从而提高了性能, 红黑树的所有不平衡情况都能在三次旋转之内来重新满足红黑树性质
红黑树是通过对结点颜色的控制来达到相对平衡的, 其每个结点的左右子树的高度差最多相差一倍(前面也说了, 最长路径最大会是最短路径的两倍)
比如, 上图也是一颗红黑树
所以, 红黑树的插入效率更高(少了很多旋转操作), AVL树的查询性能更好(平衡度更好)
红黑树的删除我还不是很理解…日后更新吧…