9 红-黑树

• 二叉搜索树最大的缺点：如果插入的数据有序，就是非平衡树，此时效率大大降低

9.1 本章讨论的方法

• 通过研究代码学习算法是十分困难的，不够形象，本章不提供代码清单。

9.1.1 概念

9.1.2 自顶向下插入

9.2 平衡树和非平衡树

9.2.1 时间复杂度降低到O(N)

• 当树没有分支时，它其实就是一个链表。

9.2.2 平衡的补救

• 如果插入（删除）动作破坏了树的特征，就需要更改树的结构。通过维持树的特征，保持树的平衡。

9.2.3 红-黑树特征

• 节点都有颜色
• 红-黑规则
  1. 每一个节点不是红色的就是黑色的
  2. 根总是黑色的
  3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
  4. 从根到叶节点或空子节点，必须包含相同数目的黑色节点。
• 重复的关键字
  • 分散在两侧
  • 暂时假定没有重复的关键字

9.2.4 修正违规的情况

• 有且仅有两个修正颜色违规的情况
  1. 改变节点的颜色
  2. 执行旋转操作

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 旋转

• 旋转必须一次做两件事情
  1. 使一些节点上升，一些节点下降，帮助树平衡
  2. 保证不破坏二叉搜索树的特征

9.5.1 简单旋转

• 顶端相当于胎面

9.5.2 奇异的横向移动节点

• 这就是红黑树的精华啊

9.5.3 移动子树

• 旋转不会改变子树节点的相互关系，整棵子树作为一个整体移动

9.5.4 人类与计算机

计算机并不善于“只靠观察”，如果计算机能遵守几个简单的规则，它们就会做得更好。这就是4个红黑规则

9.6 插入一个新节点