平衡二叉树

世界需要平衡，破坏平衡的一方，也许会一时很强势的称霸，最终的结局逃不过孤立和落空

定义

• 左、右子树是平衡二叉树；
• 所有结点的左、右子树深度之差的绝对值≤ 1

平衡因子:该结点左子树与右子树的高度差

• 任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于 1，则这棵二叉树就失去平衡，不再是 AVL 树；
• 对于一棵有 n 个结点的 AVL 树，其高度保持在 O(log2n)数量级，ASL 也保持在 O(log2n)量级。

存储结构

typedef struct BSTNode{  ElemType data;  int bf;  // 平衡因子  struct BSTNode* lchild, *rchild; } BSTNode, *BSTree;

复制代码

平衡旋转

LL 平衡旋转

• LL 型：定义失去平衡的最小子树根节点为 a，则该类不平衡可归纳为，在 a 的左子树根节点的左子树上插入导致的不平衡可使用单向右旋平衡处理，可以记为左左->右。

• 在单向右旋平衡处理后 BF(B)由 1 变为 0，BF(A)由 2 变为 0。

RR 平衡旋转

• RR 型：在 a 的右子树根节点的右子树上插入导致的不平衡可使用单向左旋平衡处理，可以记为右右->左。

在单向左旋平衡处理后 BF(B)由-1 变为 0，BF(A)由-2 变为 0。

LR 平衡旋转

• LR 型：在 3 的左子树根节点 1 的右子树上插入节点 2 导致不平衡，可使用双向旋转：先使其子树左旋再整棵树右旋，可记为左右->左右。

在双向旋转平衡处理后 BF(A)由 2 变为-1，BF(B)由-1 变为 0，BF(C)由 1 变为 0。

RL 平衡旋转

• RL 型：在 19 的右子树根节点 25 的左子树上插入节点 23 导致不平衡，可使用双向旋转：先使其子树右旋再整棵树左旋，可记为右左->右左

在双向旋转平衡处理后 BF(A)由-2 变为 0，BF(B)由 1 变为-1,BF(C)由 1 变为 0。

旋转操作特点

• 对不平衡的最小子树操作。
• 旋转后子树根节点平衡因子为 0。
• 旋转后子树深度不变故不影响全树，也不影响插入路径上所有祖先结点的平衡度。

依次插入的关键字为 5, 4, 2, 8, 6, 9

平衡二叉树插入算法思想

• 若是空树，插入节点作为根节点，树深度加 1。
• 插入节点 key 值等于根节点 key 值，则不插入。
• 插入节点 key 值小于根节点 key 值，插入在左子树上，左子树深加 1 并且：
• 左子树深度<右子树深度
• 插入前若根节点平衡因子为-1，插入后则改为 0，树深不变。

• 左子树深度＝右子树深度
• 插入前若根节点平衡因子为 0，插入后则改为 1，树深加 1。

• 左子树深度>右子树深度 LL 型
• 插入前若根节点平衡因子为 1,插入后其左子树的平衡因子为 1（左左），则单向右旋，旋转后根节点和右子树的平衡因子改为 0，树深不变。

• 左子树深度>右子树深度 LR 型
• 插入前若根节点平衡因子为 1,插入后左子树的平衡因子为-1（左右），则先左旋再右旋，旋转后根节点和其左子树的平衡因子改为 0，右子树的平衡因子改为-1,树深不变。

• 插入节点 key 值大于根节点 key 值，插入在右子树上，方法类似

平衡二叉树的查找性能分析

• 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。

在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和 log(n) 相当。

变种的 AVL 树——红黑树

• 颜色特征：每个结点为“黑色”或“红色”
• 根特征：根结点永远是“黑色”的
• 外部特征：扩充外部叶结点都是空的“黑色”结点
• 内部特征：“红色”结点的两个子结点都是“黑色”的，即：不允许两个连续的红色结点
• 深度特征：对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同