01. 初始AVL樹

AVL樹是最早發明的自平衡二叉搜索樹。在AVL樹中，任何節點的兩個子樹的高度差（平衡因子）最多為1，這使得AVL樹能夠保持較好的平衡性，從而保證查找、插入和刪除操作的時間復雜度都是O(log n)。

包含n個節點的AVL樹的高度始終保持在O(log n)

---

02. AVL樹的結構

AVL 樹在原 二叉搜索樹 的基礎上添加了 平衡因子 bf 以及用于快速向上調整的 父親指針 parent，所以 AVL 樹是一個三叉鏈結構。

2.1 AVL樹節點定義

template <class K, class V>
struct AVLTreeNode // 定義借點類型
{AVLTreeNode(const std::pair<K, V> kv): _parent(nullptr), _left(nullptr), _right(nullptr), _kv(kv), _bf(0){}AVLTreeNode<K, V> *_parent;AVLTreeNode<K, V> *_left;AVLTreeNode<K, V> *_right;//這里并沒有直接存儲數據K，和V，而是像map那樣將其封裝成一個pair<K,V>類型。std::pair<K, V> _kv; // 存儲鍵值對int _bf;             // 平衡因子
};

那么在AVLTree類方法實現只需創建一個AVLTreeNode<K,V>*類型的_root根節點。

規定： 當前實現的平衡因子，規定差值為 右 - 左，因此如果右子樹增高，_bf++，左子樹增高 _bf–，具體操作將在后面體現。

---

2.2 AVL樹的方法

template<class K,class V>
class AVLTree{typedef TreeNode<K, V> Node;
public://插入bool insert(const pair<K, V> kv) {}//查找bool find(const K& kev) {}//中序遍歷void order() {}void RotateR(Node* parent) {}	//右單旋void RotateL(Node* parent) {}	//左單旋void RRotateRL(Node* parent) {}	//右左雙選void RotateLR(Node* parent) {}	//左右雙選void order(Node* root) {}	//中序遍歷private:Node* _root;
};

---

03. AVL樹的插入

3.1插入過程

對于avl樹的插入，實際是在二叉搜索樹基礎之上，增加了更新平衡因子和在這個過程中進行旋轉調整的過程。

1. 空樹檢查
   • 若樹為空 (_root == nullptr)，直接創建新節點作為根節點，返回 true
2. 搜索插入位置
   • 從根節點開始比較 key：
     • key < 當前節點：向左子樹搜索
     • key > 當前節點：向右子樹搜索
     • key == 當前節點：鍵已存在，返回 false
3. 插入新節點
   • 創建新節點并鏈接到父節點：
     • key < 父節點：作為左孩子插入
     • key > 父節點：作為右孩子插入
4. 平衡因子更新與調整（下面完成）

• 更新平衡因子，然后判斷是否需要進行旋轉調整高度

---

bool Insert(const std::pair<K, V> kv){if (_root == nullptr){                         // 樹中沒有任何節點，直接new_root = new Node(kv); // 未使用Node(key, value)，而是采用簡直對的形式return true;}// 不為空樹時的操作,找到插入點Node *parent = nullptr;Node *cur = _root;while (cur){if (kv.first < cur->_kv.first){ // 左走parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}elsereturn false;} // 退出的時候找到,即找到葉節點仍需要判斷往那邊走，插入數據(cur==null)// 創建新節點插入cur = new Node(kv);if (kv.first < parent->_kv.first0){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//控制平衡//1、更新平衡因子----更新新增節點到根節點的祖先路徑//2、出現異常平衡因子，那么需要旋轉平衡處理while (parent) {if (cur == parent->_right)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0) {break;}else if (abs(parent->_bf) == 1) {//繼續往上更新cur = parent;parent = parent->_parent;}else if (abs(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){RotateLR(parent);//左右雙旋}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);//右左雙旋}else{assert(false);}break;}else {//說明插入更新平衡因子之前，樹中平衡因子就有問題了assert(false);}} return true;}

---

3.1 左單旋

左單旋適用場景：

  P (_bf=+2)\							    C (_bf=0)C (_bf=+1)     調整為    		 /	   \\						     P       RR							  (_bf=0)

當插入10的時候出現不平衡。

左單旋：

1. 確定parent，subR，subRL
2. 使subRL成為parent右孩子
3. subR左孩子變為parent
4. 注意pparent的更新，和paarent為根節點情況

    void RotateL(Node *parent){ // parent在_bf=2處Node *subR = parent->_right;Node *subRL = subR->_left;// 先將subR的左孩子交給parentparent->_right = subRL;if (subRL != nullptr){subRL->_parent = parent;}Node *pparent = parent->_parent;//保存parent的父節點，確保更新平衡因子subR->_left = parent;parent->_parent = subR;if (_root == parent){//是否是根節點subR->_parent = nullptr;_root = subR;}else{if (pparent->_right == parent){pparent->_right = parent;}else{pparent->_left = subR;}subR->_parent = pparent;}parent->_bf = subR->_bf = 0;}

注意事項

1. 空指針檢查：
   • subRL 可能為 nullptr，需判斷后再操作其父指針
2. 根節點更新：
   • 若 parent 是根節點，旋轉后需更新 _root 指向 subR
3. 平衡因子重置：
   • 左單旋后，parent 和 subR 的平衡因子必為 0

---

3.2 右單旋

          P (_bf=-2)/						   C (_bf=0)C (_bf=-1)				 /	   \/						L	   PL (_bf=0)					  (_bf=-0)

當插入10的時候出現不平衡。

右單旋：

1. 確定parent，subL，subLR
2. 使subLR成為parent左孩子
3. subR右孩子變為parent
4. 注意pparent的更新，和paarent為根節點情況

//右單旋
void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//先將 subL 的右孩子移交給父親parent->_left = subLR;if (subLR != nullptr)subLR->_parent = parent;Node* pparent = parent->_parent;subL->_right = parent;parent->_parent = subL;//再將父親移交給 subL，subL 成為新父親if (parent == _root){//如果原父親為根，那么此時需要更新 根subL->_parent = nullptr;_root = subL;}else{//單純改變鏈接關系if (pparent->_right == parent)pparent->_right = subL;elsepparent->_left = subL;subL->_parent = pparent;}//更新平衡因子parent->_bf = subL->_bf = 0;
}

注意事項

1. 空指針檢查：
   • subLR 可能為 nullptr，需判斷后再操作其父指針。
2. 根節點更新：
   • 若 parent 是根節點，旋轉后需更新 _root 指向 subL。
3. 平衡因子重置：
   • 右單旋后，parent 和 subL 的平衡因子必為 0。

---

3.3 右左單旋

//右左雙旋
void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int BF = subRL->_bf;//先右單旋RotateR(subR);//再左單旋RotateL(parent);//根據不同的情況更新平衡因子if(BF == 0){parent->_bf = subR->_bf = 0;}else if (BF == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (BF == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{//非法情況std::cerr << "此處的平衡因子出現異常!" << std::endl;assert(false);	//直接斷言報錯}
}

右左單旋：

1. 右單旋：
   1. 確定 parent、subR、subRL
   2. 將subRL的右子樹變為 subR左子樹，parent右子樹為subRL左子樹
   3. subRL向上提

平衡因子調整（分三類）

情況	subRL->_bf	調整后平衡因子	觸發條件
情況1	0	parent = subR = subRL = 0	新節點是 subRL 自身
情況2	-1	parent = 0, subR = +1, subRL = 0	新節點在 subRL 左子樹
情況3	+1	parent = -1, subR = 0, subRL = 0	新節點在 subRL 右子樹

---

3.4 左右雙旋

右左雙旋和左右雙旋邏輯非常像，這里就不演示了，直接看代碼實現：

//左右雙旋
void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int BF = subLR->_bf;//先左單旋RotateL(subL);//再右單旋RotateR(parent);//根據不同的情況更新平衡因子if (BF == 0){parent->_bf = subL->_bf = 0;}else if (BF == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (BF == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{//非法情況std::cerr << "此處的平衡因子出現異常!" << std::endl;assert(false);	//直接斷言報錯}
}

---

3.5 AVL查找

	//查找bool find(const K& kv) {Node* ptail = _root;while (ptail){if (kv.first > ptail->_kv->first){ptail = ptail->_right;}else if (kv.first < ptail->_kv->first){ptail = ptail->_left;}else{return true;}}return false;}

---