演示动画
- 外网地址, 打开可能有点慢: 演示地址
红黑树的特征要求
- 所有节点不是红色的就是黑色的.
- 根节点是黑色的.
- 所有叶子都是NUIL节点, 所有叶子都是黑色.
- 每个红色节点的两个子节点都是黑色, 也就是不可能有两个相连的红色节点
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点.
( 两个相连的黑色节点算一步, 一个节点到其叶子节点的步数要相同 )
优点
- 能够在极端查询条件下, 仍然保持O(log n)时间复杂度进行查找插入删除操作.
平衡规则
平衡规则
- 新节点都为红色节点
- 从下向上逐级平衡
- 平衡一级的过程 (用几个谓语句伪代码表达)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
if (空树) { 新节点改为红色; return; } if (父亲 == 黑色) { return; } if (叔叔 == 红色) { 父亲变黑色; return; } /* * 父亲是红色, 叔叔是黑色 */ // 祖父, 父亲, 当前在一条直线上 if (当前节点和父亲在同侧) { 旋转一次,父亲还是父亲, 让祖父和当前节点当兄弟; 变色; return; } // 祖父, 父亲, 当前不在一条直线上 if (当前节点和父亲不在同侧) { 旋转两次, 让当前节点当父亲, 祖父,父亲当兄弟; 变色; return; }