Question

关于算法导论

Answer 1

红黑树是一种二叉平衡树搜索树，相关背景知识此处不再叙述。

节点与关键值之间的关系与普通二叉树 一致，只是在插入时要保证红黑规则，如果插入过程中违反了红黑规则，树则会通过自我调整，改变树的结构和节点的颜色，使之满足红黑规则。满足红黑规则的树是平衡树。

红黑规则如下：

1. 每一个节点不是黑的就是红的
2. 根总是黑的
3. 红色节点的子节点必定是黑的，反之未必
4. 从根到叶节点或空子节点的每条路径中必然包含同样高度的黑色节点（从根到叶节点或空子节点的每条路径中必然有同样的高度）

为了保证红黑规则，程序按照如下方式工作：

新插入的节点（除了根以外）的是红的
插入过程中如果有一个黑色节点且它有两个红色节点，就需要颜色变化，如果该节点是根节点，则根节点不变化
右旋必须有一个左子节点，左旋必须有一个右子节点
旋转时，外侧子孙上升，内侧子孙断开其与父节点的连接，并成为其祖父节点的子节点

向下查找子节点的时候，发现一个黑色节点有两个红色节点时候，就执行一次颜色变化。
之后检查红黑冲突，发生冲突时
红色节点为X，红色节点的父节点为P，祖父节点为G，

旋转后继续向下查找

插入子节点X后
如果P为红色
如果X为G的外侧子孙，旋转一次
以G为顶点作一次旋转
如果X为G的内侧子孙，旋转两次

红黑树与Tree-2-3-4 原理非常相似，事实上可以相互转换。