罗罗编程学习记录
本页内容 展开查看

02.11.3 平衡树家族

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.11 高级数据结构

覆盖范围

  • AVL 旋转(LL/RR/LR/RL)
  • 红黑树性质与插入
  • Treap 随机堆
  • Splay 伸展树
  • 旋转操作本质与适用场景

高频题速览

编号 题目 难度 频率
02.11.3-001 AVL 树四种旋转 进阶 ★★★★
02.11.3-002 红黑树五条性质 基础 ★★★★★
02.11.3-003 红黑树插入调整 高级 ★★★★
02.11.3-004 Treap 随机堆原理 进阶 ★★★
02.11.3-005 Splay 伸展树原理 高级 ★★★
02.11.3-006 旋转操作本质 基础 ★★★
02.11.3-007 各平衡树适用场景 基础 ★★★★
02.11.3-008 BST 退化与平衡动机 基础 ★★★

02.11.3-001 AVL 树四种旋转

频率 ★★★★ | 难度 进阶

一句话结论

AVL 树要求每个节点左右子树高度差不超过 1;失衡分四种:LL(左左)右旋、RR(右右)左旋、LR(左右)先左旋再右旋、RL(右左)先右旋再左旋。

概念解释

  • LL:新节点插在左子树的左子树,右旋。
  • RR:新节点插在右子树的右子树,左旋。
  • LR:新节点插在左子树的右子树,先左旋左子树再右旋。
  • RL:新节点插在右子树的左子树,先右旋右子树再左旋。

原理流程

  1. 插入新节点。
  2. 沿插入路径向上找第一个失衡节点。
  3. 判断失衡类型(LL/RR/LR/RL)。
  4. 执行对应旋转。

代码 / 图示

LL 失衡:
    z
   /
  y
 /
x
右旋 z:
    y
   / \
  x   z

RR 失衡:
z
 \
  y
   \
    x
左旋 z:
    y
   / \
  z   x

常见误区

  • 误区:旋转后忘记更新高度;正解:旋转后要从下往上更新所有节点高度。
  • 误区:LR 直接右旋;正解:LR 先左旋 y 节点变成 LL,再右旋 z。

追问 / 延伸

  • Q:AVL 树平衡因子? A:左右子树高度差,绝对值 <= 1。
  • Q:AVL 复杂度? A:查找/插入/删除 O(log n),严格平衡。

02.11.3-002 红黑树五条性质

频率 ★★★★★ | 难度 基础

一句话结论

红黑树五条性质:节点是红或黑;根是黑;叶子(NIL)是黑;红节点的子节点是黑(不能有两个连续红);任一节点到其叶子的所有路径包含相同数目的黑节点。

概念解释

  • 颜色:红或黑。
  • 根黑:根节点必须黑。
  • 叶黑:NIL 叶子是黑。
  • 红不连续:红节点的父节点不能是红。
  • 黑高:任一节点到叶子的黑节点数相同。

原理流程

  1. 插入新节点默认红(插入黑会破坏黑高)。
  2. 父节点红则违反性质 4,需要调整。
  3. 调整手段:变色 + 旋转。

代码 / 图示

性质:
1. 节点红或黑
2. 根黑
3. 叶子 NIL 黑
4. 红节点的子节点黑(不能连续红)
5. 任一节点到叶子路径黑节点数相同

常见误区

  • 误区:红黑树是严格平衡;正解:红黑树是近似平衡,最长路径不超过最短路径 2 倍。
  • 误区:插入节点默认黑;正解:默认红,因为插入黑会破坏黑高(性质 5)。

追问 / 延伸

  • Q:红黑树 vs AVL? A:AVL 严格平衡,查找更快但插入删除旋转更多;红黑树近似平衡,插入删除旋转少。
  • Q:JDK 哪些地方用红黑树? A:TreeMap、HashMap(链表转红黑树)。

02.11.3-003 红黑树插入调整

频率 ★★★★ | 难度 高级

一句话结论

插入新节点默认红;若父节点黑则无需调整;若父节点红(叔节点红)则变色:父黑、叔黑、祖父红,沿祖父继续向上检查;若叔节点黑则需要旋转 + 变色。

概念解释

  • 父黑:插入红不违反任何性质。
  • 父红叔红:变色(父黑、叔黑、祖父红),祖父变红可能继续违反,沿祖父向上。
  • 父红叔黑:旋转 + 变色,分 LL/RR/LR/RL 四种情况。

原理流程

  1. 插入红节点。
  2. 若父节点黑:结束。
  3. 若父节点红: a. 叔节点红:父黑、叔黑、祖父红,沿祖父向上检查。 b. 叔节点黑:旋转 + 变色(类似 AVL 四种情况)。
  4. 根节点强制黑。

代码 / 图示

情况 1:父红叔红
  祖父(红)
  /    \
父(红)  叔(红)
变色:父黑、叔黑、祖父红
沿祖父向上检查

情况 2:父红叔黑(LL)
  祖父(黑)
  /
父(红)
/
新(红)
右旋祖父 + 变色:父黑、祖父红

常见误区

  • 误区:变色后不继续向上检查;正解:祖父变红后可能其父节点也是红,需要继续向上。
  • 误区:叔节点判断用 null;正解:NIL 叶子视为黑。

追问 / 延伸

  • Q:红黑树删除调整? A:删除更复杂,分双黑情况,需要旋转 + 变色,面试一般不深入。
  • Q:红黑树最多旋转几次? A:插入最多 2 次旋转,删除最多 3 次旋转。

02.11.3-004 Treap 随机堆原理

频率 ★★★ | 难度 进阶

一句话结论

Treap = Tree + Heap:节点按键保持 BST 性质,按随机优先级保持堆性质;插入时先按 BST 插入,再按堆性质旋转调整;随机优先级保证树高期望 O(log n)。

概念解释

  • BST 性质:左子树键 < 节点键 < 右子树键。
  • 堆性质:父节点优先级 < 子节点优先级(小根堆)。
  • 随机优先级:插入时随机分配,避免最坏情况。

原理流程

  1. 插入新节点:随机分配优先级,按 BST 插入。
  2. 若违反堆性质(父优先级 > 子优先级):旋转调整。
  3. 旋转方向:父 > 右子则左旋,父 > 左子则右旋。

代码 / 示例

class TreapNode {
    int key;
    int priority;
    TreapNode left, right;
    TreapNode(int k) { key = k; priority = new java.util.Random().nextInt(); }
}
// 左旋
TreapNode rotateLeft(TreapNode x) {
    TreapNode y = x.right;
    x.right = y.left;
    y.left = x;
    return y;
}
// 右旋
TreapNode rotateRight(TreapNode x) {
    TreapNode y = x.left;
    x.left = y.right;
    y.right = x;
    return y;
}
TreapNode insert(TreapNode node, int key) {
    if (node == null) return new TreapNode(key);
    if (key < node.key) {
        node.left = insert(node.left, key);
        if (node.left.priority < node.priority) node = rotateRight(node);
    } else if (key > node.key) {
        node.right = insert(node.right, key);
        if (node.right.priority < node.priority) node = rotateLeft(node);
    }
    return node;
}

常见误区

  • 误区:Treap 是严格平衡;正解:随机优先级保证期望 O(log n),最坏 O(n) 但概率极低。
  • 误区:优先级固定;正解:优先级随机分配,才能期望平衡。

追问 / 延伸

  • Q:Treap vs 红黑树? A:Treap 实现简单,期望 O(log n);红黑树最坏 O(log n),实现复杂。
  • Q:Treap 用于什么? A:竞赛中常用,工程中红黑树更多。

02.11.3-005 Splay 伸展树原理

频率 ★★★ | 难度 高级

一句话结论

Splay 树每次访问节点后将其旋转到根;摊还 O(log n);好处是刚访问的节点下次访问更快;缺点是树高可能很高,但摊还复杂度保证。

概念解释

  • 伸展:访问后将节点旋转到根。
  • 摊还复杂度:O(log n)。
  • 局部性:刚访问的节点移到根,下次访问更快。

原理流程

  1. 访问节点 x。
  2. 旋转 x 到根(分 zig、zig-zig、zig-zag 三种情况)。
  3. 摊还 O(log n)。

代码 / 图示

zig:x 是根的子节点,直接旋转 x 到根
zig-zig:x 和父节点同方向,先旋转父节点再旋转 x
zig-zag:x 和父节点反方向,先旋转 x 再旋转 x

常见误区

  • 误区:Splay 树是严格平衡;正解:Splay 树高可能很高,但摊还 O(log n)。
  • 误区:每次访问都旋转到根是 O(1);正解:旋转到根是 O(log n) 摊还。

追问 / 延伸

  • Q:Splay 适合什么场景? A:访问有局部性的场景,如缓存。
  • Q:Splay vs Treap? A:Splay 有局部性,Treap 随机平衡。

02.11.3-006 旋转操作本质

频率 ★★★ | 难度 基础

一句话结论

旋转是在保持 BST 性质的前提下改变树高:左旋把右子节点提升为父,右旋把左子节点提升为父;旋转不改变中序遍历顺序。

概念解释

  • 左旋:父节点右子节点提升,父节点变成左子节点。
  • 右旋:父节点左子节点提升,父节点变成右子节点。
  • 中序不变:旋转不改变中序遍历顺序。

原理流程

  1. 左旋 x:y = x.right;x.right = y.left;y.left = x;返回 y。
  2. 右旋 x:y = x.left;x.left = y.right;y.right = x;返回 y。
  3. 中序遍历不变:旋转只是重新组织父子关系。

代码 / 图示

左旋 x:
    x               y
     \             / \
      y    ->     x   c
     / \           \
    b   c           b

右旋 x:
    x               y
   /               / \
  y       ->      a   x
 / \                 /
a   b               b

常见误区

  • 误区:旋转改变中序顺序;正解:旋转保持中序不变。
  • 误区:左旋和右旋对称;正解:左旋是右旋的逆操作。

追问 / 延伸

  • Q:旋转后高度怎么变? A:左旋降低右子树高度,右旋降低左子树高度。
  • Q:AVL 和红黑树都用旋转吗? A:都用,但触发条件不同。

02.11.3-007 各平衡树适用场景

频率 ★★★★ | 难度 基础

一句话结论

AVL 适合查找密集(严格平衡);红黑树适合插入删除密集(旋转少);Treap 实现简单适合竞赛;Splay 适合有局部性的访问;工程中红黑树最常用。

概念解释

  • AVL:严格平衡,查找快,插入删除旋转多。
  • 红黑树:近似平衡,插入删除旋转少。
  • Treap:随机平衡,实现简单。
  • Splay:局部性,摊还 O(log n)。

原理流程

  1. 查找多、插入删除少:AVL。
  2. 插入删除多:红黑树。
  3. 竞赛快速实现:Treap。
  4. 访问有局部性:Splay。

代码 / 图示

树       平衡程度   插入删除   查找   实现复杂度
AVL      严格       旋转多     快     中
红黑树   近似       旋转少     较快   高
Treap    随机期望   旋转       较快   低
Splay    摊还       旋转到根   局部快 中

常见误区

  • 误区:红黑树比 AVL 查找快;正解:AVL 更平衡,查找更快,但插入删除旋转更多。
  • 误区:Treap 是严格平衡;正解:Treap 是期望平衡,最坏 O(n) 但概率低。

追问 / 延伸

  • Q:Java TreeMap 用什么? A:红黑树。
  • Q:C++ std::map 用什么? A:红黑树(通常)。

02.11.3-008 BST 退化与平衡动机

频率 ★★★ | 难度 基础

一句话结论

普通 BST 在插入有序数据时退化为链表,查找 O(n);平衡树通过旋转或随机化保证树高 O(log n),使查找/插入/删除都是 O(log n)。

概念解释

  • 退化:插入有序数据,BST 变成链表。
  • 树高:O(n) -> O(log n)。
  • 平衡动机:保证 O(log n) 复杂度。

原理流程

  1. 插入有序数据 1,2,3,4,5:BST 变成右斜链。
  2. 查找 5 需要 5 步,O(n)。
  3. 平衡树通过旋转或随机化,树高 O(log n)。

代码 / 图示

插入 1,2,3,4,5 后:
1
 \
  2
   \
    3
     \
      4
       \
        5

查找 5:O(n)
平衡后:树高 O(log n)

常见误区

  • 误区:BST 查找永远 O(log n);正解:BST 树高取决于数据分布,有序数据退化为 O(n)。
  • 误区:平衡树是为了提高插入速度;正解:平衡树是为了保证最坏 O(log n)。

追问 / 延伸

  • Q:BST 中序遍历有序? A:是,左子树 < 根 < 右子树。
  • Q:有哪些平衡方法? A:AVL(旋转)、红黑树(旋转+变色)、Treap(随机+旋转)、跳表(多层索引)。

待整理清单

  • [ ] 红黑树删除调整
  • [ ] B 树/B+ 树
  • [ ] 跳表与红黑树对比