AVL平衡二叉樹圖解

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

//  AVLTree插入算法 template < class K,  class V> bool AVLTree<K,V>::Insert( const K& key,  const V& value) { //1.空樹 if (_root == NULL) { _root =  new AVLTreeNode<K, V>(key, value); return true ; } //2.AVL樹不為NULL AVLTreeNode<K, V>* parent = NULL; AVLTreeNode<K, V>* cur = _root; //找到資料插入位置 while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false ; } } //插入資料 cur =  new AVLTreeNode<K, V>(key, value); cur->_parent = parent; if (parent->_key > key) parent->_left = cur; else parent->_right = cur; while (parent) { //更新平衡因子 if (cur == parent->_left) parent->_bf--; else if (cur == parent->_right) parent->_bf++; //檢驗平衡因子是否合法 if (parent->_bf == 0) break ; else if (parent->_bf == -1 || parent->_bf == 1) {   // 回溯上升 更新祖父節點的平衡因子并檢驗合法性 cur = parent; parent = cur->_parent; } else //  2 -2 平衡因子不合法 需要進行旋轉 降低高度 { if (parent->_bf == 2) { if (cur->_bf == 1) _RotateL(parent); else _RotateRL(parent); } else if (parent->_bf == -2) { if (cur->_bf == -1) _RotateR(parent); else _RotateLR(parent); } break ; } } }

　　　

左旋的兩種情況：

1.parent有兩個孩子：沒有插入節點c之前處于平衡狀态，插入c之後，平衡被破壞，向上回溯檢驗祖父節點的平衡因子，當其bf=2 時，以此節點為軸進行左旋

2.parent有一個孩子：沒有插入節點a之前處于平衡狀态，插入節點a之後，parent節點的平衡因子bf=2不滿足AVL樹的性質，要以parent為軸進行左旋

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

//左旋 template < class K,  class V> void AVLTree<K, V>::_RotateL(AVLTreeNode<K, V>*&  parent) { AVLTreeNode<K, V>* subR = parent->_right; AVLTreeNode<K, V>* subRL = subR->_left; AVLTreeNode<K, V>* ppNode = parent->_parent;       //标記祖先節點 //1.建構parent子樹 連結parent和subRL parent->_right = subRL; if (subRL) subRL->_parent = parent; //2.建構subR子樹 連結parent和subR subR->_left = parent; parent->_parent = subR; //3.連結祖先節點和subR節點 subR->_parent = ppNode; if (ppNode== NULL) { //如果祖先節點為NULL，說明目前的根節點為subR _root = subR; } else {   //将祖先節點和subR節點連結起來 if (parent == ppNode->_left) ppNode->_left = subR; else ppNode->_right = subR; } //4.重置平衡因子 parent->_bf = 0; subR->_bf = 0; //5.更新subR為目前父節點 parent = subR; }

右旋的兩種情況：

1. parent既有左孩子又有右孩子：插入c之前處于平衡态，插入c之後parent的平衡因子變為-2，這時要以parent為軸進行旋轉

2. parent隻有一個孩子：插入a之前處于平衡狀态，插入之後subL與parent的平衡因子被改變，需要以parent為軸進行旋轉

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

///右旋 template < class K,  class V> void AVLTree<K, V>::_RotateR(AVLTreeNode<K, V>*&  parent) { AVLTreeNode<K, V>* subL = parent->_left; AVLTreeNode<K, V>* subLR = subL->_right; AVLTreeNode<K, V>* ppNode = parent->_parent;       //标記祖先節點 //1.建構parent子樹 将parent和subLR連結起來 parent->_left = subLR; if (subLR) subLR->_parent = parent; //2.建構subL子樹 将subL與parent連結起來 subL->_right = parent; parent->_parent = subL; //3.将祖先節點與sunL連結起來 if (ppNode == NULL) {   //如果祖先為NULL，說明目前subL節點為根節點 subL->_parent = NULL; _root = subL; } else { subL->_parent = ppNode; if (ppNode->_left == parent) ppNode->_left = subL; else if (ppNode->_right == parent) ppNode->_right = subL; } //4.重置平衡因子 parent->_bf = 0; subL->_bf = 0; //5.更新subL為目前父節點 parent = subL; }

 左右雙旋：

1. parent隻有一個孩子：在插入節點sunLR之前，AVL樹處于平衡狀态，左右子樹高度差的絕對值不超過1。

　　由于插入了節點subLR導緻grandfather的平衡因子變為-2，平衡樹失衡，是以需要利用旋轉來降低高度！

• 首先以subL為軸，将subLR向上提（左旋），将grandfather、parent和subL旋轉至一條直線上；
• 再以parent為軸将之前的subLR向上提（右旋），左樹的高度降1，grandfather的平衡因子加1後變為-1，恢複平衡狀态。
• 雙旋完成後将parent、subL的平衡因子置為0即可，左右雙旋也就完成啦！

  

2. parent有兩個孩子：沒有插入subRL或subRR之前的AVL樹一定是處于平衡狀态的，并且滿足AVL樹的性質。

　　正是由于插入了節點subRL或者subRR，導緻其祖先節點的平衡因子被改變，grandfather的平衡因子變為-2，平衡态比打破，需要進行旋轉來降低高度！

• 首先parent為軸将subR節點往上提至原parent的位置（左旋），将grandfather、parent 和 subR旋至一條直線上；
• 再以grandfather為軸将subR往上提至grandfather的位置（右旋），此時以subR為根的左右子樹的高度相同，恢複了平衡态！

  

parent有兩個孩子時，要看插入的節點是subR的右孩子還是左孩子，雙旋後對平衡因子的修改分兩種情況：

• subR的平衡因子為1，即subR有右孩子無左孩子（有subRR但無subRL），雙旋之後将grandfather的平衡因子置為0，将parent的平衡因子置為-1；
• subR的平衡因子為-1，即subR有左孩子無右孩子（有subRL但無subRR），雙旋之後将grandfather的平衡因子置為1，将parent的平衡因子置為0；

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

//左右雙旋 template < class K,  class V> void AVLTree<K, V>::_RotateLR(AVLTreeNode<K, V>*&  parent) { AVLTreeNode<K, V>* pNode = parent; AVLTreeNode<K, V>* subL = parent->_left; AVLTreeNode<K, V>* subLR = subL->_right; int bf = subLR->_bf; _RotateL(parent->_left); _RotateR(parent); if (bf == 1) { pNode->_bf = 0; subL->_bf = -1; } else if (bf == -1) { pNode->_bf = 1; subL->_bf = 0; } else { pNode->_bf = 0; subL->_bf = 0; } }

　右左雙旋：

1. parent隻有一個孩子：由于節點subRL的插入破壞了AVL樹的平衡，parent的平衡因子變為2，需要利用旋轉來降低高度！

• 首先，以subR為軸，将subRL提上去（右旋），保證parent、subR 和 subRL在一條直線上；
• 以parent為軸，将上一步标記為subRL的節點向上升（左旋），這樣達到了降低高度的目的；
• 雙旋之後，parent和subR的平衡因子都要置為0

2.parent有兩個孩子：沒有插入subLL或者subLR之前的AVL樹一定是處于平衡狀态的，并且滿足AVL樹的性質。

　　正是由于插入了節點subLL或者subLR，導緻其祖先節點的平衡因子被改變，grandfather的平衡因子變為2，平衡态比打破，需要進行旋轉來降低高度！

• 首先parent為軸将subL節點往上提至原parent的位置（右旋），将grandfather、parent 和 subL旋至一條直線上；
• 再以grandfather為軸将subL往上提至grandfather的位置（左旋），此時以subL為根的左右子樹的高度相同，恢複了平衡态！

parent有兩個孩子時，要看插入的節點是subL的右孩子還是左孩子，雙旋後對平衡因子的修改分兩種情況：

• subL的平衡因子為1，即subL有右孩子無左孩子（有subLR但無subLL），雙旋之後将grandfather的平衡因子置為-1，将parent的平衡因子置為0；
• subL的平衡因子為-1，即subL有左孩子無右孩子（有subLL但無subLR），雙旋之後将grandfather的平衡因子置為0，将parent的平衡因子置為1；　

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

//右左雙旋 template < class K,  class V> void AVLTree<K, V>::_RotateRL(AVLTreeNode<K, V>*&  parent) { AVLTreeNode<K, V>* pNode = parent; AVLTreeNode<K, V>* subR= parent->_right; AVLTreeNode<K, V>* subRL = subR->_left; int bf = subRL->_bf; _RotateR(parent->_right); _RotateL(parent); if (bf == 1) { pNode->_bf = 0; subR->_bf = -1; } else if (bf == -1) { pNode->_bf = 1; subR->_bf = 0; } else { pNode->_bf = 0; subR->_bf = 0;