AVL树、红黑树和伸展树

二叉查找树

二叉查找树的特征(递归) ——或者是一棵空树或者是具有如下特性的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
• 它的左、右子树也分别是二叉排序树。
• 中序遍历二叉排序树可得到一个关键字的有序序列。

在一般情况下，查找和插入的时间复杂度为logN, 但是在极端情况下会退化为链表，此时查找变为顺序遍历，失去了排序树的意义。——构造的二叉查找树的形状依赖于数据项，且依赖于它们加载的顺序

二叉查找树平衡性很差（即失衡）时，可用AVL树、红黑树和伸展树进行改进。其中AVL树和红黑树是高度平衡的，伸展树是加权平衡的(将常用的数据项放在树中接近根部的位置)

AVL树

定义(递归)：或者是一棵空树，或者是具有如下特性的二叉查找树

• 左子树和右子树的高度最多相差1；
• 它的左、右子树也分别是平衡二叉树。

如何调整节点以维持高度的平衡？

Step1：找到不平衡（即左右子树高度差距大于1）的最小子树的根节点（记为A）

Step2：依据新插入节点与节点A的相对位置，进行相应处理。

• LL型失衡: 在A结点的左孩子的左子树上插入结点,导致A结点失去平衡.——单向右旋平衡处理
• RR型失衡: 单向左旋平衡处理
• LR型失衡: 双向旋转先左后右平衡处理型。先把下段左旋转换为LL型失衡，再将上段右旋解决LL型失衡
• RL型失衡: 双向旋转先右后左平衡处理型。先把下段右旋转换为RR型失衡，再将上段左旋解决RR型失衡

为修复失衡所进行的旋转操作可能需要对插入和删除期间所采用的访问路径执行向后遍历(当需要多次旋转时）——实现起来比较麻烦？

红黑树

红黑树是满足下列条件的二叉查找树：

• 每个节点都带有红色或黑色。节点的颜色由以下规则确定：
• 根节点是黑色的。
• 所有叶节点都是黑色的。
• 在沿着从根出发的任何路径上都不允许出现两个连续的红色节点，即：“红色”结点的两个子结点都是“黑色”的。
• 从任一节点到其每个子孙叶子节点的所有简单路径都包含相同数目的黑色节点（简称黑色高度）
  • 节点X的黑色高度：从节点X到其子孙叶子节点的简单路径中的黑色链的数量。
    • 不包括 X 结点本身，包括叶结点
    • 外部结点的阶是零；
  • 红黑树的黑色高度：根节点的黑色高度（称为：根节点的阶）
    • 阶为 k 的红黑树路径长度：最短是 k，最长是 2k ——实现平衡的原因

2-3-4树的二叉树的实现本质上就是红黑树——可利用颜色翻转和旋转来等价实现

两类基本操作：

颜色翻转

• 实质上为4-节点分裂
• 当某个结点的两个孩子结点都为红色时
• 将两个红色孩子结点和其黑色双亲结点的颜色翻转

旋转

• 出现右的红色链时；有连续两个红色链时
• 依据两个连续的红色链的形状，进行相应的旋转处理（类似AVL树的失衡旋转规则）；对于右的红色链，进行左旋处理

伸展树

实现一种恒定重排的方式：每次访问树时，都使用旋转操作重排树，使得访问过的节点位于树的根部。

优点：最近使用的数据比未使用过的数据可更快的被访问——局部性原理,可以用于缓存

自底向上的伸展(更好理解)

利用旋转，将访问的节点c搬根部。有三种基本操作：

Case1：若访问的节点c没有祖父节点，则：直接在c与其父节点p之间进行旋转。

Case2：若访问的节点c，其父节点p，其祖父节点g三者之间的相关位置呈LL或RR型，则：先在p和g间旋转，再在p和c间旋转。（由上至下）

Case3：若访问的节点，其父节点，其祖父节点三者之间的相关位置呈LR或RL型，则：先在c和p间旋转，再在c和g间旋转。（由下至上）

自顶向下的伸展

首先确定从根到访问节点的路径，然后依据路径的形状，进行“分裂”操作。最后，以目标节点作为根进行片断的重组。

每次分裂操作会将当前树分为左，中，右三个片断。左片断为中间片断的前驱，右片断为中间片断的后继；其中，前驱、后继是指中序遍历顺序。左，右片断分别插入到左右存储树中。

左连接点：指左存储树中插入新片断的位置，指向左存储树中最右下角的节点。

右连接点：右存储树中插入新片断的位置，指向右存储树中最左下角的节点。