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的平衡因子調整我就不再贅述了,畫一畫很容易明白的。 ================================================================
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 }