红黑树

性质

• 红黑性质

  1. 节点红或黑
  2. root 节点是黑的
  3. 每个叶节点是黑的
  4. 红节点的儿子都是黑的
  5. 对每个节点，从该节点到其子孙节点的所有路径上的包含相同的黑节点。

• 好的查找树性质

  一棵有 $n$ 个内节点的红黑树的高度至多为 $2\log{(n+1)}$。

操作

• 旋转

  旋转操作可以不改变二叉查找树的性质而对树进行调整，可以有左旋(逆时针)和右旋(顺时针)。 复杂度为 $O(1)$，因为全部都是指针的移动。

• 插入

  先将红黑树当作是普通的二叉查找树进行插入，并着为红色，然后使用一个辅助函数进行调整：

  1. 首先确定红黑性质有哪些不能继续保持。(在这一点上，性质 1，3，5都是会成立的。) 当插入的 z 是根节点时，性质 2 被破坏。如果 z 的父节点是红色的，性质 4 被破坏。

  2. 之后对插入节点 z 进行迭代操作。分三种情况进行讨论。

• 删除

  思想和插入类似，都是先按照普通二叉树进行，然后进行调整。但是情况多了一点更复杂。

AVL 树

之前经常听到 AVL 树，但是在书里面却是以练习题的形式出现的。

操作

• Balance

  分四种情况，对单个节点直接最多两次旋转即可。

  然后再分情况对子树进行检验，如果改变了平衡因子的子树们的平衡因子都还是0，-1，1的话说明已经平衡，否则再进行平衡操作。