9 红-黑树
- 二叉搜索树最大的缺点：如果插入的数据有序，就是非平衡树，此时效率大大降低
9.1 本章讨论的方法
- 通过研究代码学习算法是十分困难的，不够形象，本章不提供代码清单。
9.1.1 概念
9.1.2 自顶向下插入
9.2 平衡树和非平衡树
9.2.1 时间复杂度降低到O(N)
- 当树没有分支时，它其实就是一个链表。
9.2.2 平衡的补救
- 如果插入（删除）动作破坏了树的特征，就需要更改树的结构。通过维持树的特征，保持树的平衡。
9.2.3 红-黑树特征
- 节点都有颜色
- 红-黑规则
- 每一个节点不是红色的就是黑色的
- 根总是黑色的
- 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
- 从根到叶节点或空子节点，必须包含相同数目的黑色节点。
- 重复的关键字
- 分散在两侧
- 暂时假定没有重复的关键字
9.2.4 修正违规的情况
- 有且仅有两个修正颜色违规的情况
- 改变节点的颜色
- 执行旋转操作
9.3 使用RBTree专题applet
9.3.1 点击一个节点
- 红色箭头指示当前选择的节点
9.3.2 Start按钮
9.3.3 Ins按钮
9.3.4 Del按钮
9.3.5 Flip颜色变换按钮
- 父节点和子节点之间的颜色发生了转换
9.3.6 RoL按钮
- 左旋
9.3.7 RoR按钮
- 右旋
9.3.8 R/B变色按钮
- 把一个节点红转黑，或黑转红
9.3.9 文本信息
- 显示是否为正确的红黑树
9.3.10 Find按钮在哪里
- 没有Find按钮
9.4 用专题applet做试验
9.4.1 试验1：插入两个红色节点
9.4.2 试验2：旋转
9.4.3 试验3：颜色变换
9.4.4 试验4：非平衡树
9.4.5 更多试验
9.4.6 红-黑规则和平衡树
- 红-黑规则能保证树是平衡的
9.4.7 空子节点
9.5 旋转
- 旋转必须一次做两件事情
- 使一些节点上升，一些节点下降，帮助树平衡
- 保证不破坏二叉搜索树的特征
9.5.1 简单旋转
- 顶端相当于胎面
9.5.2 奇异的横向移动节点
- 这就是红黑树的精华啊
9.5.3 移动子树
- 旋转不会改变子树节点的相互关系，整棵子树作为一个整体移动
9.5.4 人类与计算机
计算机并不善于“只靠观察”，如果计算机能遵守几个简单的规则，它们就会做得更好。这就是4个红黑规则
