平衡二叉搜索樹/AVL樹

VAL樹的特性

左右子樹高度差的絕對值不超過1。（即左右子樹高度差取值為-1，0，1）
且左右子樹均為VAL樹
右子樹的值大于左子樹的值

在搜索二叉樹中我們提及了搜索二叉樹的退化問題。

當有序（升序或降序）地插入時，搜索二叉樹就會出現下圖的情況，搜索次數從樹的高度次退化成n次。而平衡搜索二叉樹就解決了這一問題。

平衡方法

在解決方案中，左右子樹的差值被定為平衡因子，所以上述例子用平衡二叉搜索樹的角度來看如下圖。此時出現了不被允許的2和-2，意味著平衡被打破，需要進行調整平衡。

插入時平衡因子的變化邏輯

以下綠色方框代表一棵子樹，h為其高度，且h>=0，具體節點上方的數字為平衡因子。

因為插入節點，導致60這個節點的左右子樹失衡了。

????????如圖我們可以看到，根據插入位置的不同，其父節點的平衡因子的變化也不同。因為此處我使用的平衡因子 = 右子樹高度 - 左子樹高度。所以當插入到右子樹時，父節點平衡因子+1，插入到左子樹時，父節點平衡因子-1。

了解完插入時平衡因子的變化，我們再來了解一下變化的兩種情況。

（1）插入后父節點平衡因子變為1或-1的，那么其原來的平衡因子是0，意味著該父節點原本平衡，插入節點后打破了平衡使該父節點為根的整棵子樹高度產生變化，此時平衡因子需要繼續向上更新，于是60這個節點也受其影響改變了，此時出現了不被允許的失衡，此時就要旋轉調整平衡。

（2）第二種情況比較簡單，插入后父節點平衡因子變為0，意味著其原本有一些失衡，但還在允許范圍內，但插入后完全平衡了，此時無需再繼續更新，因為高度沒有改變。

總結：亞健康（-1、1）到健康（0）不用管，反之健康到亞健康要去向上更新平衡因子，因為其父節點可能直接就生病了。

// 在AVL樹中插入值為data的節點bool Insert(const T& data){if (_pRoot == nullptr){_pRoot = new Node(data);return true;}Node* parent = nullptr;Node* cur = _pRoot;while (cur){if (data > cur->_data){parent = cur;cur = cur->_pRight;}else if (data < cur->_data){parent = cur;cur = cur->_pLeft;}else{return false;}}cur = new Node(data);if (parent->_data < data){parent->_pRight = cur;}else{parent->_pLeft = cur;}cur->_pParent = parent;//調整平衡因子while (parent){if (cur == parent->_pLeft){parent->_bf--;}else{parent->_bf++;}//插入后恰好平衡了，跳出循環if (parent->_bf == 0){break;}    //高度出現變化但還未失衡，向上走進行判斷else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}	//已經失衡需要進行調整else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2 && cur->_bf == -1){//右單旋RotateR(parent);}else 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);}break;}else{//理論而言不可能出現這個情況（此時小于-2或大于2）assert(false);}}return true;}

旋轉調整?

有了前面插入時平衡因子變化邏輯的鋪墊，失衡時的情況就簡化成了：

失衡節點無非是-2或2，造就失衡節點的子節點無非是-1，1（產生高度變化）。排列組合后就出現了四種情況。于是出現四種旋轉方式與其一一對應。

?右單旋

此時的失衡情況為：左左（插入在失衡節點的左節點的左子樹中），此時失衡節點平衡因子為-2，產生高度變化的子節點平衡因子為-1。

所以右單旋適用于“左左”，即parent的平衡因子為-2，高度變化的子節點的平衡因子為-1。

?右單旋過程：
?

可以看到，調整后30和60這兩個節點的平衡因子都為0了。

那么為什么要這么做？?

現在我們先來分析一下他們的大小關系。

比較大小后發現，60非常適合當作30的右子樹根節點，同時又做b子樹的父節點，因為60>b子樹任意值>30。

所以右單旋就是將失衡節點及其右子樹下壓，當作高度出現變化的節點的右子樹，再連接上b子樹和60這個節點，就使30的左右子樹高度一致了。左子樹高度是h+1（1為插入的節點），右邊也是h+1（1為原父節點），此時30成為新父節點。

// 右單旋void RotateR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;pParent->_pLeft = subLR;if (subLR)subLR->_pParent = pParent;subL->_pRight = pParent;Node* temp = pParent->_pParent;pParent->_pParent = subL;//pParent有可能為根，右單旋后應該更新根節點指向。if (pParent == _pRoot){_pRoot = subL;_pRoot->_pParent = nullptr;}else{if (temp->_pLeft == pParent){temp->_pLeft = subL;}else{temp->_pRight = subL;}subL->_pParent = temp;}pParent->_bf = subL->_bf = 0;}

左單旋

與右單旋同理，不過多贅述。

左單旋適用于“右右”，即parent的平衡因子為2，高度變化的子節點的平衡因子為1。

旋轉過程：?

// 左單旋void RotateL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;pParent->_pRight = subRL;if (subRL)subRL->_pParent = pParent;subR->_pLeft = pParent;Node* temp = pParent->_pParent;pParent->_pParent = subR;//pParent有可能為根，右單旋后應該更新根節點指向。if (pParent == _pRoot){_pRoot = subR;_pRoot->_pParent = nullptr;}else{if (temp->_pLeft == pParent){temp->_pLeft = subR;}else{temp->_pRight = subR;}subR->_pParent = temp;}pParent->_bf = subR->_bf = 0;}

左右雙旋

如圖所示，當出現插入節點在失衡節點（90）其左孩子（30）的右孩子（60）下的子樹時，就需要用到左右雙旋，單旋是無法解決的。

即：失衡節點平衡因子為-2，且其左孩子的平衡因子為1時使用左右雙旋，以下簡稱“左右”。

第一步，我們對30為根的子樹進行左單旋。（第一次旋轉后，失衡的狀況從“左右”變成了可以使用右單旋的“左左”）

?第二步，我們對90為根的子樹進行右單旋。

?代碼實際上是對左單旋和右單旋的復用，然后再處理節點間的連接關系。

// 左右雙旋void RotateLR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;RotateL(subL);RotateR(pParent);subLR->_bf = 0;if (bf == 1){pParent->_bf = 0;subL->_bf = -1;}else if (bf == -1){pParent->_bf = 1;subL->_bf = 0;}else{pParent->_bf = 0;subL->_bf = 0;}}

右左雙旋

失衡節點平衡因子為2，且其左孩子的平衡因子為-1時使用左右雙旋。

第一步，我們對90為根的子樹進行右單旋。（第一次旋轉后，失衡的狀況從“右左”變成了可以使用左單旋的“右右”）

?第二步，我們對30為根的子樹進行左單旋。

// 右左雙旋void RotateRL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(subR);RotateL(pParent);subRL->_bf = 0;if (bf == 1){pParent->_bf = -1;subR->_bf = 0;}else if (bf == -1){pParent->_bf = 0;subR->_bf = 1;}else{pParent->_bf = 0;subR->_bf = 0;}}

完整代碼實現

#pragma once
#include<assert.h>
#include<vector>
#include<iostream>
using namespace std;namespace VAL
{template<class T>struct AVLTreeNode{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf;   // 節點的平衡因子};// AVL: 二叉搜索樹 + 平衡因子的限制template<class T>class AVLTree{typedef AVLTreeNode<T> Node;public:AVLTree(): _pRoot(nullptr){}Node* Find(const T& data){Node* cur = _pRoot;while (cur){if (cur->_data < data){cur = cur->_pRight;}else if (cur->_data > data){cur = cur->_pLeft;}else{return cur;}}return nullptr;}// 在AVL樹中插入值為data的節點bool Insert(const T& data){if (_pRoot == nullptr){_pRoot = new Node(data);return true;}Node* parent = nullptr;Node* cur = _pRoot;while (cur){if (data > cur->_data){parent = cur;cur = cur->_pRight;}else if (data < cur->_data){parent = cur;cur = cur->_pLeft;}else{return false;}}cur = new Node(data);if (parent->_data < data){parent->_pRight = cur;}else{parent->_pLeft = cur;}cur->_pParent = parent;//調整平衡因子while (parent){if (cur == parent->_pLeft){parent->_bf--;}else{parent->_bf++;}//插入后恰好平衡了，跳出循環if (parent->_bf == 0){break;}    //高度出現變化但還未失衡，向上走進行判斷else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}	//已經失衡需要進行調整else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else 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);}break;}else{// 理論而言不可能出現這個情況assert(false);}}return true;}// AVL樹的驗證bool IsAVLTree(){return _IsAVLTree(_pRoot);}int Size(){return _Size(_pRoot);}void InOrder(){_InOrder(_pRoot);cout << endl;}size_t Height(){return _Height(_pRoot);}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_pLeft);cout << root->_data << endl;_InOrder(root->_pRight);}bool _IsAVLTree(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_pLeft);int rightHeight = _Height(root->_pRight);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_data << endl;return false;}// 順便檢查一下平衡因子是否正確if (rightHeight - leftHeight != root->_bf){cout << root->_data << endl;return false;}return _IsAVLTree(root->_pLeft)&& _IsAVLTree(root->_pRight);}size_t _Height(Node* _pRoot){if (_pRoot == nullptr) return 0;return max(_Height(_pRoot->_pLeft), _Height(_pRoot->_pRight)) + 1;}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_pLeft) + _Size(root->_pRight) + 1;}// 右單旋void RotateR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;pParent->_pLeft = subLR;if (subLR)subLR->_pParent = pParent;subL->_pRight = pParent;Node* temp = pParent->_pParent;pParent->_pParent = subL;//pParent有可能為根，右單旋后應該更新根節點指向。if (pParent == _pRoot){_pRoot = subL;_pRoot->_pParent = nullptr;}else{if (temp->_pLeft == pParent){temp->_pLeft = subL;}else{temp->_pRight = subL;}subL->_pParent = temp;}pParent->_bf = subL->_bf = 0;}// 左單旋void RotateL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;pParent->_pRight = subRL;if (subRL)subRL->_pParent = pParent;subR->_pLeft = pParent;Node* temp = pParent->_pParent;pParent->_pParent = subR;//pParent有可能為根，右單旋后應該更新根節點指向。if (pParent == _pRoot){_pRoot = subR;_pRoot->_pParent = nullptr;}else{if (temp->_pLeft == pParent){temp->_pLeft = subR;}else{temp->_pRight = subR;}subR->_pParent = temp;}pParent->_bf = subR->_bf = 0;}// 右左雙旋void RotateRL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(subR);RotateL(pParent);subRL->_bf = 0;if (bf == 1){pParent->_bf = -1;subR->_bf = 0;}else if (bf == -1){pParent->_bf = 0;subR->_bf = 1;}else{pParent->_bf = 0;subR->_bf = 0;}}// 左右雙旋void RotateLR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;RotateL(subL);RotateR(pParent);subLR->_bf = 0;if (bf == 1){pParent->_bf = 0;subL->_bf = -1;}else if (bf == -1){pParent->_bf = 1;subL->_bf = 0;}else{pParent->_bf = 0;subL->_bf = 0;}}private:Node* _pRoot;};
}