AVL樹是啥

一提到AVL樹，腦子里不是旋了，就是懸了。

AVL樹之所以難，并不是因為結構難以理解，而是因為他的旋轉。

AVL樹定義

• 平衡因子：對于一顆二叉樹，某節點的左右子樹高度之差，就是該節點的平衡因子
• AVL樹：對于一顆二叉樹，任意節點的平衡因子bf 在范圍[-1，1]之間（即左右子樹高度差的絕對值<=1），則該樹就是平衡二叉樹

為何會有AVL樹

AVL樹是二叉搜索樹的衍生，其名字來源是根據兩位俄羅斯的數學家G.M.Adelson-Velskii 和E.M.Landis，他們在1962年發明的一種用來解決二叉搜索樹在極端情況下時間復雜度變為O(n)的情況。而其解決該情況的方法便是：通過旋轉旋轉來調整二叉搜索樹的平衡

AVL樹的節點

AVL樹的節點實現方式有很多，這里采取下面的方法定義節點：

template<class T>struct AVLTreeNode{AVLTreeNode(const T& data): _left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_bf(0){}AVLTreeNode<T>* _left;  // 該節點的左孩子AVLTreeNode<T>* _right; // 該節點的右孩子AVLTreeNode<T>* _parent;// 該節點的父親T _data;//存儲數據int _bf;//平衡因子  
};

這里AVL樹節點的實現增加了_bf （平衡因子）成員變量，用來記錄每個點的平衡因子。同時用了父節點的指針_parent ，目的是方便調整平衡因子。

AVL樹的插入

這里AVL樹的插入操作與二叉搜索樹一樣，唯一不同的是，在插入后要調整平衡因子

• 對于插入的節點，因為其是插入到葉節點位置，所以他的平衡因子為0
• 將節點插入后，樹的高度可能會發生改變，此時則要調整他父親，甚至還要調整父親的父親的平衡因子。主要分為以下幾種情況

情況1：

如果在節點的右孩子插入，則該節點的bf需要+1（節點70、50的bf連鎖著發生了變化，后面有說明）

---

情況2：

如果在節點的左孩子插入，則該節點的bf需要-1（節點70、50的bf連鎖著發生了變化，后面有說明）

但是沒完！

如果節點的平衡因子因為插入而變成了1 或者-1 ，則說明子樹的高度發生了變化，此時該節點的父節點的bf也應發生變化（如果父節點的bf更改之后影響了“爺爺節點”，則爺爺節點也要跟著跟著變化）。所以上圖中的70和50兩節點的bf也要發生變化。

---

但是還沒完！

bf 的值有可能會變為2、-2，則此時就需要進行旋轉操作（旋轉完成后，會手動調整bf，保證其符合要求）

代碼：

//插入操作
...
//調整平衡因子
cur = newnode;
parent = newnode->_parent;
while (parent)
{if (parent->_right == cur){++parent->_bf;}else if (parent->_left == cur){--parent->_bf;}if (parent->_bf == 0)//AVL樹穩定了，break出去break;else if (parent->_bf == 1 || parent->_bf == -1)//無需旋轉但是需要更改父親的平衡因子{cur = parent;parent = parent->_parent;}else if ()//需要旋轉{}
}

AVL樹的旋轉

重中之重，也是難中之難

AVL樹旋轉的目的

AVL樹是一個平衡二叉搜索樹，因為某些插入操作導致它不再平衡（具體表現是平衡因子變為2或-2），則此時為了使之平衡，就需要進行旋轉操作

AVL樹旋轉操作

AVL樹的旋轉主要分為4種情況：

1. 左旋
2. 右旋
3. 左旋再右旋（雙旋）
4. 右旋再左旋（雙旋）

情況1：左旋

對于插入后父親的bf=2，右孩子的bf=1的情況，采用左旋。且左旋后平衡因子都是0

---

情況2：右旋

對于插入后父親的bf=-2，左孩子的bf=-1的情況，采用右旋。且右旋后平衡因子都是0

---

雙旋

這種情況的發生是因為發現對該節點無論左旋還是右旋，都無法使其平衡，原因是插入節點的位置比較特殊

情況3：左旋再右旋

對于插入（這里插入b還是c只會影響旋轉完后的平衡因子）后父親的bf=-2，左孩子的bf=1的情況，采用左旋再右旋。這里的平衡因子更新規則與前不同，詳見后文。

---

情況4：先右旋再左旋

對于插入（這里插入b還是c只會影響旋轉完后的平衡因子）后父親的bf=2，右孩子的bf=-1的情況，采用右旋再左旋。這里的平衡因子更新規則與前不同，詳見后文。

雙旋的平衡因子更新規則

更新規則相比旋轉規則就簡單許多

分為以下3種情況（以上圖為例）：

1. 如果60的平衡因子（旋轉前）是-1，則更新后的60的平衡因子變為0，左孩子變為0，右孩子變為1
2. 如果60的平衡因子（旋轉前）是1，則更新后60的平衡因子變為0，左孩子變為-1，右孩子變為0
3. 如果60的平衡因子（旋轉前）是0，則更新后60的平衡因子變為0，左孩子變為0，右孩子變為0

代碼：

這里只給出一部分代碼，剩下的可以自己嘗試寫出來，然后可以到倉庫對照

bool insert(const pair<K,V>& kv)
{//插入Node* newnode = new Node(kv);if (newnode == nullptr) return false;if (_root == nullptr){_root = newnode;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (kv.first > cur->_kv.first){cur = cur->_right;}else cur = cur->_left;}//調整節點連接if (kv.first > parent->_kv.first)parent->_right = newnode;else parent->_left = newnode;newnode->_parent = parent;//調整平衡因子cur = newnode;parent = newnode->_parent;while (parent){if (parent->_right == cur){++parent->_bf;}else if (parent->_left == cur){--parent->_bf;}if (parent->_bf == 0)//AVL樹穩定了，break出去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){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else{assert(false);}}}return true;
}
//左旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_parent = subR;subR->_left = parent;parent->_right = subRL;if (subRL){subRL->_parent = parent;}if (!pparent){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}parent->_bf = 0;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){subLR->_bf = 0;parent->_bf = 0;subL->_bf = 0;}else if (bf == 1){subLR->_bf = 0;parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){subLR->_bf = 0;parent->_bf = 1;subL->_bf = 0;}else{assert(false);}
}