資料結構——平衡二叉樹（AVL）

平衡二叉樹

世界需要平衡，破壞平衡的一方，也許會一時很強勢的稱霸，最終的結局逃不過孤立和落空

定義

• 左、右子樹是平衡二叉樹；
• 所有結點的左、右子樹深度之差的絕對值≤ 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樹——紅黑樹

• 顔色特征：每個結點為“黑色”或“紅色”
• 根特征：根結點永遠是“黑色”的
• 外部特征：擴充外部葉結點都是空的“黑色”結點
• 内部特征：“紅色”結點的兩個子結點都是“黑色”的，即：不允許兩個連續的紅色結點
• 深度特征：對于每個結點，從該結點到其所有子孫葉結點的路徑中所包含的黑色結點數量必須相同