平衡樹的模擬實現

一.平衡樹的介紹

平衡樹是以二叉樹結構為基礎，同時引入了平衡因子進行了限制，以保證樹的結點之間的高度差小于等于1，在插入刪除結點時通過旋轉的方法保持高度相對平衡，從而提高搜索等效率。

二.代碼實現

1.平衡樹結點

平衡樹結點是以二叉樹為基礎構建的，因此需要左右結點指針left與right。傳入pair一部分為值value另一部分為關鍵字key，以及平衡因子bf（左子樹高度減右子樹高度）。

下面是結點代碼：

template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};

?2.平衡樹的插入

插入結點時首先要找到合適的位置空間來放置新結點，所以我們需要遍歷樹。從根結點開始（cur），若值比當前結點小讓cur往左邊走，若值比當前結點大讓cur往右邊走，直到cur跑到空時停止。

接著進行判斷，根據結點高度差的不同，結點位置不一樣進行不同的旋轉方式，調整相應的平衡因子，根據parent結點的高度決定是否要繼續向上更新。

下面是尋找結點的相應代碼：
if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;
若樹的結點為空那么直接插入根結點，若不為空按照上述的方法遍歷到空結點后，需要注意要確定parent的位置。

?下面我們來討論一下旋轉

首先計算平衡因子，若cur在parent的左邊則bf--，若cur在parent的右邊則bf++，若parent的bf為0時直接跳出結果。

若parent的左右都存在結點，那么就是平衡的，反之則不平衡，若bf等于1或者-1,時繼續向上更新bf平衡值，讓cur等于parent，parent等于parent的parent。

向上遍歷若得到bf等于2或者-2時，說明此時樹已經不平衡了，需要進行旋轉調整樹的結構。

下面我們依次分析左旋，右旋，左右雙旋，右左雙旋的情況

1.右單旋

當parent的平衡因子為-2，cur的平衡因子為-1時我們需要右單旋

如圖p代表parent，c代表cur此時我們需要進行右旋操作d代表插入的結點。以parent為軸向右旋轉讓cur變成parent。

我們需要得到parent結點，cur結點（SUL），以及cur結點的右結點（SULR）。

讓SULR變成parent的左結點SUL的右結點變成parent，其他的不進行改變。

需要注意的是，首先需要判斷SULR結點是否存在，若存在就讓其變為parent的左結點，若不存在就不進行操作。以及我們需要找到parent結點的parent結點，若parentparent結點為空則則讓root結點直接變為SUL即可，若不為空需要判斷parent結點是parentparent結點的左還是右結點，然后將其左或右給給SUL。

下面放上代碼：
void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;//parent有可能是整棵樹的根，也有可能是局部子樹//如果是整棵樹的根則修改root//if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_bf = subL->_bf = 0;}

2.左單旋?

左單旋與右單旋類似，只是parent結點的左右子樹互換了位置。

當parent的bf為2時，cur的bf為1時，需要進行左旋操作。

如圖p代表parent ，c代表cur結點，插入的結點為a。以parent為軸向左旋轉。

我們需要得到cur結點的左結點（SURL），parent結點以及cur結點（SUR）。讓parent的右為SURL，SUR的左為parent。其他的不進行改變。?

與上文相同需要找到parent的parent，若parentparent不存在就將root結點設置為SUR，若存在，則根據parent是parentparent的左或者右結點來分配給SUR結點。

下面是代碼：
void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;}

3.左右雙旋?

當parent的bf等于-2，cur的bf等于1時，進行左右雙旋。先對cur進行左旋讓其bf等于-1，此時就回到了第一種情況，再對parent進行一次右旋就完成了操作。

當新增結點cur結點與parent結點形成一個角度時，需要進行雙旋操作，如果是開口向右則進行左右雙旋，若開口向左則進行右左雙旋。

此處的難點在于對插入結點bf的分類討論。

第一種情況當SULR（R）的bf為0時

?此時我們需要先對SUL進行左旋操作，使其滿足三個點連成一條直線，之后再對parent進行右旋操作，得到下圖。

我們可以根據最終結果直接寫出代碼，先對SUL進行左旋再對parent進行右旋，最后設置三個結點的bf都為0即可。

第二種情況當SULR（R）的bf為-1時

當我們進行左右雙旋操作后

變成如圖，此時需要將parent的bf設置為1，SUL和SULR設置為0。

第三種情況當SURL（R）的bf為1時

進行左右雙旋操作之后

?將SUL的bf設置為-1,parent與SULR的bf設置為0即可。

下面附上代碼：
	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else{assert(false);}}

4.右左雙旋

右左雙旋本質與左右雙旋一樣，只是左右子樹位置互換

所以我就直接附上代碼：

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else{assert(false);}}

?5.插入代碼總結

bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新平衡因子while (parent){//定義平衡因子左減右加if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0){//更新結果break;}else if (parent->_bf == 1 || parent->_bf == -1){//繼續向上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//旋轉處理不平衡if (parent->_bf == 2 && cur->_bf == 1)//左單旋{RotateL(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//右左雙旋{RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1)//左右雙旋{RotateLR(parent);}else if(parent->_bf == -2 && cur->_bf == -1)//右單旋{RotateR(parent);}break;}else{//說明傳入的有問題報錯日志assert(false);}}return true;}//右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;//parent有可能是整棵樹的根，也有可能是局部子樹//如果是整棵樹的根則修改root//if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_bf = subL->_bf = 0;}//左單旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else{assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else{assert(false);}}

3.鍵值查找 ?樹的高度計算與平衡樹判斷

查找值時，只需要遍歷整個樹即可，以根節點（cur）為起始點，當所找的值比cur小時向左樹尋找，比cur大時向右樹尋找，直到cur值等于尋找值時返回當前結點，若cur為空了仍未找到結點就返回空。
Node* find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}

計算樹的高度時我們采用遞歸左右子樹的方法實現，判斷左右子樹的大小取大值，逐層遞歸得到最終值。
int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}

?判斷是否平衡時，我們可以調用左右子樹的高度，然后相減，得到diff。若diff大于2說明高度異常，若根結點的bf不等于diff說明平衡因子計算存在錯誤。
bool _IsBalanceTree(Node* root){if (nullptr == root)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = leftHeight - rightHeight;if (abs(diff) >= 2){cout << root->_kv.first << "高度異常" << endl;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子異常" << endl;return false;}return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}