目錄

1.文章概括

2.AVL樹概念

3.AVL樹的性質

4.AVL樹的插入

5.旋轉控制

1.左單旋

2. 右單旋

3.左右雙旋

4.右左雙旋

6.全部代碼

---

1.文章概括

? ? ? ? 本文適合理解平衡二叉樹的讀者閱讀，因為AVL樹是平衡二叉樹的一種優化，其大部分實現邏輯與平衡二叉樹是相同的，相同的部分不做過多闡述。

2.AVL樹概念

? ? ? ? 平衡二叉樹主要用于查找數據，可提高查找效率，但如果數據有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下。在這樣的缺點下，AVL樹被發明了出來。AVL樹的優化點在于：當向二叉搜索樹中插入新結點后，如果能保證每個結點的左右子樹高度之差的絕對值不超過1（需要對樹中的結點進行調整），即可降低樹的高度，從而減少平均搜索長度。

3.AVL樹的性質

? ? ? ? 一棵AVL樹或者是空樹，或者是具有以下性質的二叉搜索樹：

1.它的左右子樹都是AVL樹；

2.左右子樹高度之差（簡稱平衡因子）的絕對值不超過1（-1,0,1）。

AVL樹 == 高度平衡二叉搜索樹，說是平衡，為什么不是相等？

因為高度差不超過1，不是高度相等。

AVL樹圖片示例：

? ? ? ? 如此控制后，增刪改查的時間復雜度即為高度次 == O(logN)。

4.AVL樹的插入

????????對于一個結點的插入，分析如下：

1.新增在該結點的左，parent平衡因子減減；

2.新增在該結點的右，parent平衡因子加加；

3.更新后parent平衡因子 == 0，說明parent所在的子樹的高度不變，不會再影響祖先，不用再沿著到root的路徑往上更新；

4.更新后parent平衡因子 == 1 or -1，說明parent所在的子樹的高度變化，會再影響祖先，需要沿著到root的路徑往上更新；

5.更新后parent平衡因子 == 2 or -2，說明parent所在的子樹的高度變化且不平衡，對parent所在子樹進行旋轉，讓它平衡；

6.更到根結點。

補充說明：執行到4時會從1,2,開始繼續循環，執行到3,5,6時插入結束。

旋轉時需要注意的問題：

1.保持它是搜索樹；

2.變成平衡樹且降低這個子樹的高度。

代碼：

bool Insert(const T& data){Node* parent = nullptr;Node* cur = _pRoot;if (cur == nullptr){cur = new Node(data);_pRoot = cur;}while (cur){if (cur->_data > data){parent = cur;cur = cur->_pLeft;}else if (cur->_data < data){parent = cur;cur = cur->_pRight;}elsereturn false;}cur = new Node(data);if (parent->_data > data){parent->_pLeft = cur;cur->_pParent = parent;}else{parent->_pRight = cur;cur->_pParent = parent;}while (parent){if (parent->_pLeft == cur)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)return true;else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}else{if (cur->_bf == 1 && parent->_bf == 2){RotateL(parent);}else if (cur->_bf == -1 && parent->_bf == -2){RotateR(parent);}else if (cur->_bf == -1 && parent->_bf == 2){RotateRL(parent);}else if (cur->_bf == 1 && parent->_bf == -2){RotateLR(parent);}break;}}}

? ? ? ? 代碼中，我使用了平衡因子來控制這棵樹的高度。

5.旋轉控制

1.左單旋

2. 右單旋

3.左右雙旋

?新節點插入較高左子樹的右側---左右：

4.右左雙旋

6.全部代碼

#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;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){}// 在AVL樹中插入值為data的節點bool Insert(const T& data){Node* parent = nullptr;Node* cur = _pRoot;if (cur == nullptr){cur = new Node(data);_pRoot = cur;}while (cur){if (cur->_data > data){parent = cur;cur = cur->_pLeft;}else if (cur->_data < data){parent = cur;cur = cur->_pRight;}elsereturn false;}cur = new Node(data);if (parent->_data > data){parent->_pLeft = cur;cur->_pParent = parent;}else{parent->_pRight = cur;cur->_pParent = parent;}while (parent){if (parent->_pLeft == cur)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)return true;else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}else{if (cur->_bf == 1 && parent->_bf == 2){RotateL(parent);}else if (cur->_bf == -1 && parent->_bf == -2){RotateR(parent);}else if (cur->_bf == -1 && parent->_bf == 2){RotateRL(parent);}else if (cur->_bf == 1 && parent->_bf == -2){RotateLR(parent);}break;}}}// AVL樹的驗證bool IsAVLTree(){return _IsAVLTree(_pRoot);}private:// 根據AVL樹的概念驗證pRoot是否為有效的AVL樹bool _IsAVLTree(Node* root){if (root == nullptr)return true;int leftHight = Height(root->_pLeft);int rightHight = Height(root->_pRight);if (rightHight - leftHight != root->_bf){cout << "平衡因子異常:" << root->_data << "->" << root->_bf << endl;return false;}return abs(rightHight - leftHight) < 2&& _IsAVLTree(root->_pLeft)&& _IsAVLTree(root->_pRight);}size_t Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_pLeft);int rightHeight = Height(root->_pRight);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}// 右單旋void RotateR(Node* pParent) {Node* cur = pParent->_pLeft;Node* curRight = cur->_pRight;Node* parentP = pParent->_pParent;pParent->_pLeft = curRight;if(curRight)curRight->_pParent = pParent;cur->_pRight = pParent;pParent->_pParent = cur;if (parentP == nullptr){_pRoot = cur;cur->_pParent = nullptr;}else{cur->_pParent = parentP;if (parentP->_pLeft == pParent)parentP->_pLeft = cur;elseparentP->_pRight = cur;}if(curRight)curRight->_bf = 0;pParent->_bf = cur->_bf = 0;}// 左單旋void RotateL(Node* pParent){Node* cur = pParent->_pRight;Node* curLeft = cur->_pLeft;Node* parentP = pParent->_pParent;pParent->_pRight = curLeft;if(curLeft)curLeft->_pParent = pParent;cur->_pLeft = pParent;pParent->_pParent = cur;if (parentP == nullptr){_pRoot = cur;cur->_pParent = nullptr;}else{cur->_pParent = parentP;if (parentP->_pLeft == pParent)parentP->_pLeft = cur;elseparentP->_pRight = cur;}if(curLeft)curLeft->_bf = 0;pParent->_bf = cur->_bf = 0;}// 右左雙旋void RotateRL(Node* pParent){Node* cur = pParent->_pRight;Node* curLeft = cur->_pLeft;int temp = curLeft->_bf;RotateR(cur);RotateL(pParent);if (temp == 0)return;else if (temp == 1){pParent->_bf = -1;cur->_bf = 0;curLeft->_bf = 0;}else if (temp == -1){pParent->_bf = 0;cur->_bf = 1;curLeft->_bf = 0;}elseassert(false);}// 左右雙旋void RotateLR(Node* pParent){Node* cur = pParent->_pLeft;Node* curRight = cur->_pRight;int temp = curRight->_bf;RotateL(cur);RotateR(pParent);if (temp == 0)return;else if (temp == 1){pParent->_bf = 0;cur->_bf = -1;curRight->_bf = 0;}else if (temp == -1){pParent->_bf = 1;cur->_bf = 0;curRight->_bf = 0;}elseassert(false);}private:Node* _pRoot;
};

??