8.平衡二叉搜索树

Balanced Binary Search Tree : BBST

当节点数量固定时，左右子树的高度越接近，那么这棵二叉树就越平衡（高度越低），保持二叉树的平衡可以避免二叉树退化成链表，防止操作二叉树的复杂度增加。

常见的平衡二叉搜索树：

AVL树：Windows NT 内核中广泛使用

红黑树：C++ STL（比如map 、set）,java 的Tree Map 、Tree Set 、HashMap、HashSet，Linux 进程调度，Ngix的timer管理

一般它们也称为：自平衡的二叉搜索树（Self-balancing Binary Search Tree）

AVL树

失衡：每个节点的平衡因子绝对值 ≤ 1

某节点的平衡因子 = 左子树高度 - 右子树高度

添加、删除、搜索的复杂度 O(logn)

添加节点造成的失衡

LL-右旋转（单旋）平衡

note(n)、parent(p)、g(grandfather)

g为失衡节点

如何找到失衡节点：节点类多维护一个height属性，

• g.left = p.right

• p.right = g

• 同时维护 T2、g、p 的 parent 属性

RR-左旋转（单旋）

LR-RR左旋转，LL右旋转（双旋）

RL-LL右旋转，RR左旋转（双旋）

image-20220113143328884.png

伪代码：
// Note添加高度属性height
// 1.成功添加完节点的操作后，延着节点的父节点链条遍历父节点
// 2.父节点对应子节点高度+1，接着对比左右子节点高度，如果没有失衡，更新高度，失衡->做对应的旋转，节点高度不变
示例：13，14，15，12，11，17，16，8，9，1

删除节点造成的失衡

绿色代表着T2的最大高度，会影响旋转后的子树的整体高度，如果子树高度发生变化，需要向上检查是否失衡

要在删除操作结束后，才去平衡树

LL右旋转

RR右旋转

LR-RR左旋转，LL右旋转

RL-LL右旋转，RR左旋转