平衡二叉树

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

定义

• 左、右子树是平衡二叉树；
• 所有结点的左、右子树深度之差的绝对值≤ 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树——红黑树

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