AVL樹的插入操作（旋轉）圖解

AVL樹的概念

在說AVL樹的概念之前，我們需要清楚二茬搜索樹的概念。對於二叉搜索樹，我們知道它可以降低查找速率，但是如果一個二叉搜索樹退化成一棵只剩單支的搜索樹，此時的查找速率就相當於順序表中查找元素，效率變低，時間復雜度由原來的O（logN）變為O（N）。 此時就有了AVL（高度平衡二叉搜索樹），從它的名字就能知道它也是一棵二叉搜索樹，只是它在插入元素的時候，每插入一個新節點的時候就會調整整棵樹的結構，從而來保證這課搜索樹的平衡，即每一個節點的左右子樹高度差的絕對值不超過1. 那麼AVL樹的概念就可以總結如下： 滿足以下性質的二叉搜索樹： 1、左右子樹都是AVL樹 2、左右子樹的高度之差的絕對值不超過1 那麼對於像這樣的AVL樹，如果它有n個節點，則它的高度可以保持在log(n),那麼它的平均搜索時間復雜度也就是O(log(n)了。 ================================================================

AVL樹的插入

1、平衡因子 AVL樹也是一棵二叉搜索樹，所以它的插入是和二叉搜索樹的插入操作類似的，只是需要加上調整高度的操作，那麼就需要在節點的那個結構體類型中加一個用來反應這個節點的左右孩子高度的變量，平衡因子bf。 定義bf的值等於節點右孩子的高度減去左孩子的高度。如果節點的左右孩子高度相等,則bf等於0；如果左孩子比右孩子高度大1，則bf取-1；如果右孩子高度比左孩子高度大1，則bf取1.那麼如果不是上面的這三種情況，就不滿足AVL樹的定義了，即出現bf的絕對值大於1的時候就要進行高度調整了，所以就是當bf等與2或者-2的時候就要進行平衡化。 那麼當給一棵本來就平衡的AVL樹中插入一個新節點P的時候，從節點P到根節點的路徑上，每個節點為根的子樹的高度都可能增加1，即平衡因子發生改變，所以執行一次插入操作後，都需要沿路徑向根節點回溯，修改各節點的平衡因子，而如果遇到了哪一個節點的bf變成2或-2的時候就要進行平衡化處理，即調整棵樹的高度。 2、節點類型的結構體 我們已經知道在結構體中需要加一個變量 bf，而且我們在修改bf的時候是需要回溯的，所以如果我們還存放了每個節點的父節點就比較方便了，那麼可以設計如下的節點結構體類型：

 template<class K>
struct AVLTreeNode
{
    K _key;
    int _bf;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
 
    AVLTreeNode(const K& key, const V& value)
        :_key(key),
        _bf(0),
        _left(NULL),
        _right(NULL),
        _parent(NULL)
    {}
};

3、平衡化處理 在前面已經說了當更新到某個節點的平衡因子變成-2或者2的時候就需要進行平衡化處理，我們在AVL樹中的平衡化處理采用的是旋轉。對於平衡化處理中的旋轉分為以下幾種情況： 》左單旋： 》右單旋 》左右雙旋 》右左雙旋 下面是對於上述四種情況的圖解： 》【左單旋】當前節點較高右子樹的右側插入一個新節點，該子樹高度增加1導致節點平衡因子從1變為變為2而不平衡 》【右單旋】當前節點較高的左子樹左側插入一個新節點，該子樹的高度增加1,導致該節點的平衡因子從-1變為-2而不平衡 》【左右雙旋】當前節點的平衡因子為-1，在當前節點較高的左子樹的右子樹b或者c中插入一個節點，該子樹的高度增加1，使當前節點的左孩子的平衡因子變為1，當前節點的平衡因子變成-2，導致AVL樹不再平衡，需要進行調整，采用先左後右雙旋 （PPNode是10的父節點） 可以看到在這裡插入的節點是插在了6節點的左子樹，那麼它當然也可以插入到6的右子樹中，而且還可以是上圖中的方框代表的子樹都是空這種情況，此時就相當於是插入6這個節點。這樣的話，最後更新節點的平衡因子就要注意了，我們稍後再分析； 》【右左雙旋】當前節點的平衡因子為1，在當前節點較高的右子樹的左子樹b或者c插入新節點該子樹的高度增加1，當前節點的右孩子的平衡因子變成-1，當前節點的平衡因子變成2，導致AVL樹不再平衡，需要進行調整，采用先右後左雙旋 （PPNode是5的父節點） 》》》》注意：上面兩個雙旋的圖解只是其中的一種情況，在上面左右雙旋的下面我已經提出來了，這裡需要注意非常重要的一點，就是你插入了新節點之後會改變哪幾個節點的平衡因子，顯然插入的地方不一樣沒得到的結果也會有差異； 因為每插入一個節點都要向上更新bf，我們總結一下遇到什麼情況應該旋轉，采用什麼旋轉： 若parent->bf=-2或者2的時候需要進行調整 》parent->bf=2,說明它的右樹比左樹高，設它的右孩子為pcur >若pcur->bf==1，執行左單旋 >若pcur->bf==-1,執行右左雙旋旋 》parent->bf=-2,說明它的左樹比右樹高，設它的左孩子為pcur >若pcur->bf==-1，執行右單旋 >若pcur->bf==1,執行左右雙旋單旋 我們可以看到，在旋轉過程中平衡因子發生改變的節點只有parent和pcur這兩個節點，那麼旋轉之後該怎樣修改這兩個節點的平衡因子呢。 >對於左單旋和右單旋的情況，parent和pcur的平衡因子都會變為0，所以在旋轉完成後把它們的平衡因子置成0 >對於雙旋，我們最後更新平衡因子的時候是需要分情況的 那麼通過上圖的說明，我們就可以看出來，最終影響parent和subR節點平衡因子的是subRL這個節點，主要就是看新插入的節點到底是插在它的左子樹還是右子樹，當然還有一種情況就是圖中矩形代表的子樹都為空的情況，也就是subRL就是要插入的節點，那麼總共就是這三種情況，對應出來如下： 》subRL的平衡因子是0（插入的節點就是它本身） 》subRL的平衡因子是-1（新節點插在subRL的左子樹） 》subRL的平衡因子是1 （新節點插在subRL的右子樹） 對應的最終subR和parent的平衡因子調整我就不再贅述了，畫一畫很容易明白的。 ================================================================

程序代碼：

>>插入 insert函數

 1     bool Insert(const K& key, const V& value)
 2     {
 3         if (_root == NULL)
 4         {
 5             _root = new Node(key, value);
 6             return true;
 7         }
 8         Node* pcur = _root;
 9         Node* parent = NULL;
10         while (pcur)
11         {
12             if (pcur->_key == key)
13                 return false;
14             else if (pcur->_key < key)
15             {
16                 parent = pcur;
17                 pcur = pcur->_right;
18             }
19             else
20             {
21                 parent = pcur;
22                 pcur = pcur->_left;
23             }
24         }
25         if (parent->_key < key)
26         {
27             pcur = parent->_right = new Node(key, value);
28             pcur->_parent = parent;
29         }
30         else
31         {
32             pcur = parent->_left = new Node(key, value);
33             pcur->_parent = parent;
34         }
35 
36         while (parent)
37         {
38             //修正平衡因子
39             if (pcur == parent->_left)
40             {
41                 parent->_bf--;
42             }
43             if (pcur == parent->_right)
44             {
45                 parent->_bf++;
46             }
47             //
48             if (parent->_bf == 0)
49                 break;
50             else if (parent->_bf == -1 || parent->_bf == 1)
51             {
52                 pcur = parent;
53                 parent = pcur->_parent;
54             }
55             else   //parent->bf   -2  ||  2
56             {
57                 
58                 if (parent->_bf == -2)
59                 {
60                     if (pcur->_bf == -1)   //右單旋
61                         RotateR(parent);
62                     else                   //左右雙旋
63                         RotateLR(parent);
64                 }
65                 else 
66                 {
67                     if (pcur->_bf == 1)    //左單旋
68                         RotateL(parent);
69                     else                   //右左雙旋
70                         RotateRL(parent);
71                 }
72                 break;
73             }
74         }
75         return true;
76     }

>>旋轉

  1     void RotateR(Node* parent)
  2     {
  3         Node* subL = parent->_left;
  4         Node* subLR = subL->_right;
  5         //換指向
  6         parent->_left = subLR;
  7         subL->_right = parent;
  8 
  9         if (subLR)
 10         {
 11             subLR->_parent = parent;
 12         }
 13 
 14         Node* PParent = parent->_parent; //判斷parent是否有父節點
 15         if (PParent)
 16         {
 17             if (parent == PParent->_left)
 18             {
 19                 PParent->_left = subL;
 20                 subL->_parent = PParent;
 21             }
 22             else
 23             {
 24                 PParent->_right = subL;
 25                 subL->_parent = PParent;
 26             }
 27         }
 28         else
 29         {
 30             _root = subL;
 31             subL->_parent = NULL;
 32         }
 33         parent->_parent = subL;
 34         //修改bf
 35         subL->_bf = 0;
 36         parent->_bf = 0;
 37      }
 38 
 39     //
 40     void RotateL(Node* parent)
 41     {
 42         Node* subR = parent->_right;
 43         Node* subRL = subR->_left;
 44         //調整指向
 45         subR->_left=parent;
 46         parent->_right = subRL;
 47 
 48         if (subRL)    //如果subRL非空
 49         {
 50             subRL->_parent = parent;
 51         }
 52         
 53         Node* PPNode = parent->_parent;
 54         if (PPNode)
 55         {
 56             if (PPNode->_left == parent)
 57                 PPNode->_left = subR;
 58             else
 59                 PPNode->_right = subR;
 60 
 61             //subR的父節點改變
 62             subR->_parent = PPNode;
 63         }
 64         else
 65         {
 66             _root = subR;   //根節點
 67             subR->_parent = NULL;
 68         }
 69         parent->_parent = subR;
 70         /*修改bf*/
 71         parent->_bf = subR->_bf = 0;
 72     }
 73 
 74     //雙旋(左右、、右左)
 75     void RotateRL(Node* parent)
 76     {
 77         Node* subR = parent->_right;
 78         Node* subRL = subR->_left;
 79         int bf = subRL->_bf;
 80 
 81         RotateR(parent->_right);
 82         RotateL(parent);
 83 
 84         //調整subR和parent的平衡因子
 85         if (bf == -1)
 86             subR->_bf = 1; // subR的bf在左旋中已經置0了，這裡就沒有再寫
 87         else if (bf == 1)
 88             parent->_bf = -1;
 89 
 90         else
 91         {
 92             parent->_bf = 0;
 93             subRL->_bf = 0;
 94         }
 95     }
 96 
 97     void RotateLR(Node* parent)
 98     {
 99         Node* subL = parent->_left;
100         Node* subLR = subL->_right;
101         int bf = subLR->_bf;
102         RotateL(parent->_left);
103         RotateR(parent);
104 
105         //調整parent和subL的平衡因子
106         if (bf == -1)
107             parent->_bf = 1;  //subL的bf在左旋中已經置0了，這裡就沒有再寫
108         else if (bf == 1)
109             subL->_bf = -1;   //parent的bf在左旋中已經置0了
110         else
111         {
112             subL->_bf = 0;
113             parent = 0;
114         }
115     }