Avltree

AVL木のバランスの取れた回転と挿入について



About Balanced Rotation



1つは、AVLツリーの概念です。
1.定義 ：バランスのとれた二分探索木はAVL木です。
2.自然 ：
（1）その左右のサブツリーはAVLツリーです
（2）左側のサブツリーと右側のサブツリーの高さの差の絶対値（バランス係数と呼ばれる）が1（-1、0、1）を超えないこと
3.バランスファクターの計算方法 ：左右のサブツリーの高さの違い

2.AVLツリーのバランスの取れた回転
1.左単一回転：挿入されたノードは、右上のサブツリーの右側（右右）にあります。
******* ノードfを挿入した後、ノードaのバランス係数の絶対値は2です。この時点で、ツリーはAVLツリーのプロパティを満たしていないため、バランスに達するには、左1回転でバランス係数を調整する必要があります。木の。 （cノードを上げ、aノードを下げます）
画像
画像
コードは次のとおりです。



void RotateL(pNode pParent) { //Find the right subtree of the parents first, the left subtree of the right subtree pNode pSubR = pParent->_pRight pNode pSubRL = pSubR->_pLeft //Process pSubRL first pParent->_pRight = pSubRL if(pSubRL) pSubRL->_pParent = pParent pSubR->_pLeft = pParent pNode ppParent = pSubR->_pParent pParent->_pParent = pSubR if(pParent == _pRoot) { pSubR->_pLeft = pParent pSubR->_pParent = NULL } // Determine whether pParent is the left subtree or the right subtree else if(ppParent->_pLeft == pParent) { ppParent->_pLeft = pSubR } else { ppParent->_pRight = pSubR } pSubR->_pParent = ppParent //Update balance factor pParent->_bf = pSubR->_bf = 0 }

2.右単一回転：挿入されたノードは左上のサブツリーの左側（左左）にあります
**** ノードfを挿入した後、ノードaのバランス係数の絶対値は2です。この時点で、ツリーはAVLツリーのプロパティを満たしていないため、バランスに達するには、右1回転でバランス係数を調整する必要があります。木の。 （ノードbを上げ、ノードaを下げます）
画像
画像

void RotateR(pNode pParent) { //First find the left subtree of the parents, and the right subtree of the left subtree pNode pSubL = pParent->_pLeft pNode pSubLR = pSubL->_pRight //Process pSubLR first pParent->_pLeft = pSubLR if(pSubLR) pSubLR->_pParent = pParent pSubL->_pRight = pParent pNode ppParent = pSubL->_pParent pParent->_pParent = pSubL if(pParent == _pRoot) { pSubL->_pRight = pParent pSubL->_pParent = NULL } // Determine whether pParent is the left subtree or the right subtree else if(ppParent->_pLeft == pParent) { 1 ppParent->_pLeft = pSubL } else { ppParent->_pRight = pSubL } pSubL->_pParent = ppParent //Update balance factor pParent->_bf = pSubL->_bf = 0 }

3.左右の二重回転（最初に左の単一​​回転、次に右の単一回転）：挿入されたノードは左上のサブツリーの右側にあります
******* ノードfを挿入した後、ノードaのバランス係数の絶対値は2です。この時点で、ツリーはAVLツリーのプロパティを満たしていないため、バランス係数を調整するには、左右の1回転で調整する必要があります。木のバランス。最初にノードbをルートノードとして使用して、aの左側のサブツリーのバランスを左単一回転で調整し、次にサブツリー全体を全体的な右単一回転に調整します。
画像



void RotateLR(pNode pParent) { pNode pSubL = pParent->_pLeft pNode pSubLR = pSubL->_pRight RotateL(pParent) RotateR(pParent->_pLeft) //Update balance factor int bf = pSubLR->_bf if(bf == 1) pSubL->_bf = -1 else if(bf == -1) pSubL->_bf = 1 }

4.右と左の二重回転（最初に右の単一回転、次に左の単一​​回転）：挿入されたノードは右上のサブツリーの左側にあります
**** ノードfを挿入した後、ノードaのバランス係数の絶対値は2です。この時点で、ツリーはAVLツリーのプロパティを満たしていないため、バランス係数を調整するには、左右の1回転で調整する必要があります。木のバランス。最初にノードcをルートノードとして使用して、aの右のサブツリーと右の単一回転のバランスを調整し、次にサブツリー全体を左の単一回転全体として調整します。

画像

void RotateRL(pNode pParent) { pNode pSubR = pParent->_pRight pNode pSubRL = pSubR->_pLeft RotateR(pParent) RotateL(pParent) //Update balance factor int bf = pSubRL->_bf if(bf == 1) pSubR->_bf = -1 else if(bf == -1) pSubR->_bf = 1 }

三、AVL木の挿入
アルゴリズムは次のとおりです。
1.ツリーが空の場合、挿入後はルートノードになり、挿入後すぐにtrueを返します。
2.ツリーが空でない場合は、挿入する位置を探します（検索プロセス中にキーが見つかった場合、挿入は失敗し、falseを返します）
3.ノードを挿入します
4.バランス係数を調整します



注：新しいノードのバランス係数は0ですが、その親pParentのバランス係数には次の3つの状況があります。

  • （1）pParentのバランス係数が0の場合、つまりpParentの短いサブツリーに新しいノードを挿入する場合、この時点でpParentはバランスが取れていますが、この時点で、pParentからルートノードへのパス上の各ノードはルートサブツリー高さは変更されません。つまり、各ノードのバランス係数は変更されません。バランスファクターを調整する必要はありません
  • （2）pParentのバランス係数の絶対値が1の場合、挿入前のpParentのバランス係数は0です。挿入後、pParentをルートとするサブツリーはバランスを失いませんが、サブツリーの高さは増加します。 pParentからルートノードまでのpParentの親のバランス係数を表示します
  • （3）ステップ2でバランス係数を更新した後、pParentのバランス係数の絶対値が2の場合、新しいノードは上位のサブツリーに挿入され、バランスを取る必要があります。
  • （3.1）pParent-> _ bt == 2の場合、右側のサブツリーは高く、pParentの右側のサブツリーはpSubRです。 pSubRのバランスファクターが1の場合、左シングルローテーションを実行します。pSubRのバランスファクターが-1の場合、右左ダブルローテーションを実行します。
  • （3.2）pParent-> _ bt == -2の場合、左側のサブツリーは高く、pParentの左側のサブツリーはpSubLです。 pSubLのバランス係数が-1の場合、pSubLのバランス係数が1の場合、右1回転を実行します。左右の2回転を実行します。
  • 回転後、pParentをルートとするサブツリーの高さが低くなり、検索を続ける必要はありません。

完全なコードは次のとおりです。

#include<math.h> #include<iostream> using namespace std template <class V, class K> struct AVLTreeNode { //Give left and right subtrees, parent nodes AVLTreeNode<V,K>* _pLeft AVLTreeNode<V,K>* _pRight AVLTreeNode<V,K>* _pParent K _key //Key code V _value int _bf //Balance factor //Constructor AVLTreeNode(const K& key, const V& value) :_pLeft(NULL) ,_pRight(NULL) ,_pParent(NULL) ,_key(key) ,_value(value) ,_bf(0) {} } template <class V, class K> class AVLTree { typedef AVLTreeNode<V,K> Node typedef Node* pNode public: //Constructor AVLTree() :_pRoot(NULL) {} //Insert node bool Insert(const K& key, const V& value) { //If the tree is empty, insert directly if(NULL == _pRoot) //Create a new node and make it equal to the root of the search binary tree { _pRoot = new Node(key, value) return true } else { //The tree is not empty, divide the situation pNode pParent = NULL pNode pCur = _pRoot //Insert node while(pCur) { if(key > pCur->_key) { pParent = pCur pCur = pCur->_pRight } else if(key < pCur->_key) { pParent = pCur pCur = pCur->_pLeft } else return true } pCur = new Node(key, value) if(key > pParent->_key) { pParent->_pRight = pCur pCur->_pParent = pParent } else { pParent->_pLeft = pCur pCur->_pParent = pParent } //Adjust the balance factor while(pParent) { if(pParent->_pLeft = pCur) { pParent->_bf-- } else { pParent->_bf++ } if(pParent->_bf == 0) break else if(pParent->_bf == 1 || pParent->_bf == -1) { pCur = pParent pParent = pCur->_pParent } else { if(pParent->_bf == 2) { if(pCur->_bf == 1) RotateL(pParent) else //-1 RotateRL(pParent) } else { if(pCur->_bf == -1) RotateR(pParent) else //1 RotateLR(pParent) } } break } } return true } void Inorder() { _Inorder(_pRoot) cout<<endl } bool IsBalance() { return _IsBalance(pRoot) } private: //Left single rotation---Insert the right side of the higher right subtree void RotateL(pNode pParent) { //Find the right subtree of the parents first, the left subtree of the right subtree pNode pSubR = pParent->_pRight pNode pSubRL = pSubR->_pLeft //Process pSubRL first pParent->_pRight = pSubRL if(pSubRL) pSubRL->_pParent = pParent pSubR->_pLeft = pParent pNode ppParent = pSubR->_pParent pParent->_pParent = pSubR if(pParent == _pRoot) { pSubR->_pLeft = pParent pSubR->_pParent = NULL } //Determine whether pParent is the left subtree or the right subtree else if(ppParent->_pLeft == pParent) { ppParent->_pLeft = pSubR } else { ppParent->_pRight = pSubR } pSubR->_pParent = ppParent //Update balance factor pParent->_bf = pSubR->_bf = 0 } //Right single spin---Insert the left side of the higher left subtree void RotateR(pNode pParent) { //First find the left subtree of the parents, and the right subtree of the left subtree pNode pSubL = pParent->_pLeft pNode pSubLR = pSubL->_pRight //Process pSubLR first pParent->_pLeft = pSubLR if(pSubLR) pSubLR->_pParent = pParent pSubL->_pRight = pParent pNode ppParent = pSubL->_pParent pParent->_pParent = pSubL if(pParent == _pRoot) { pSubL->_pRight = pParent pSubL->_pParent = NULL } //Determine whether pParent is the left subtree or the right subtree else if(ppParent->_pLeft == pParent) { ppParent->_pLeft = pSubL } else { ppParent->_pRight = pSubL } pSubL->_pParent = ppParent //Update balance factor pParent->_bf = pSubL->_bf = 0 } //Left and right double rotation---Insert the right side of the higher left subtree (first left and then right) void RotateLR(pNode pParent) { pNode pSubL = pParent->_pLeft pNode pSubLR = pSubL->_pRight RotateL(pParent) RotateR(pParent->_pLeft) //Update balance factor int bf = pSubLR->_bf if(bf == 1) pSubL->_bf = -1 else if(bf == -1) pSubL->_bf = 1 } //Right-left double-rotation-Insert the left side of the higher right subtree (first right-handed and then left-handed) void RotateRL(pNode pParent) { pNode pSubR = pParent->_pRight pNode pSubRL = pSubR->_pLeft RotateR(pParent) RotateL(pParent) //Update balance factor int bf = pSubRL->_bf if(bf == 1) pSubR->_bf = -1 else if(bf == -1) pSubR->_bf = 1 } void _Inorder(pNode pRoot) { if(NULL == pRoot) return _Inorder(pRoot->_pLeft) _Inorder(pRoot->_pRight) } bool _IsBalance(pNode pRoot) { //The tree is empty if(NULL == pRoot) return true //The tree exists int leftHeight = _Height(pRoot->_pLeft) int rightHeight = _Height(pRoot->_pRight) if(abs(rightHeight - leftHeight) >= 2) return false return _IsBalance(pRoot->_pLeft)&&_IsBalance(pRoot->_pRight) } int _Height(pNode pRoot) { if(NULL == pRoot) return 0 int leftHeight = _Height(pRoot->_pLeft) int rightHeight = _Height(pRoot->_pRight) return ((leftHeight>rightHeight?leftHeight:rightHeight)+1) } protected: pNode _pRoot } void AVLTreeTest() { int array[] = {16, 3, 7, 11, 9, 26, 18, 14, 15} AVLTree A for(int i = 0 i[0]) ++i) { A.Insert(array[i], i) } A.Inorder() } int main() { void AVLTreeTest() return 0 }

ははは、AVLツリーの4回転に関連する状況はいくつありますか。私は一部を描いただけで、読者はすべて自分で描くことができます。 ！ ！