深入理解AVL樹及其旋轉操作

AVL樹的概念

二叉搜索樹雖可以縮短查找的效率，但如果數據有序或接近有序二叉搜索樹將退化為單枝樹，查找元素相當于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數學家G.M.Adelson-Velskii和E.M.Landis在1962年發明了一種方法：當二叉樹搜索樹中插入新節點后，如果能保證每個系欸但的左右子樹的高度之差的絕對值不超過1，也就是說要降低樹的高度，從而減少平均搜索長度。

一棵AVL樹，它具有以下的性質：

它的左右子樹都是AVL樹
左右子樹高度之差的絕對值不超過1

如果一棵搜索二叉樹的高度是平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在log2(n)，搜索時間復雜度log2(n)。

AVL樹結點的定義

struct AVLTreeNode
{AVLTreeNode<K, V>* _left;//左孩子AVLTreeNode<K, V>* _right;//右孩子AVLTreeNode<K, V>* _parent;//父節點std::pair<K, V> _kv;//鍵值對int _bf;//平衡因子AVLTreeNode(const std::pair<K, V>& kv) : _left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

這里定義了對AVL樹的結點的描述，一個結點應當有左右孩子結點，父節點，鍵值對，以及平衡因子。
左右孩子結點和鍵值對是基于搜索二叉樹（AVL樹是在搜索二叉樹的基礎上建立的）。
平衡因子用來衡量這顆樹是否是平衡的。
平衡因子=右子樹高度-左子樹高度
至于父節點，則是未來方便平衡因子的更新而添加進去的。

AVL樹的插入

AVL樹是在搜索二叉樹的基礎上引入了平衡因子，因此AVL樹也可以看成是二叉搜索樹。所以，插入的過程可以分為兩步：

按照搜索二叉樹的方式插入新節點
調整結點的平衡因子

bool Insert(const std::pair<K,V>&kv)
{Node* cur = _root;Node* parent = nullptr;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 == nullptr){_root = cur;return true;}if (parent->_kv.first < kv.first){parent->_right = cur;}elseparent->_left = cur;cur->_parent = parent;return true;
}

按照搜索二叉樹的規則，查找到我們需要插入的地方。

插入的鍵比當前結點的鍵小，遞歸左子樹
插入的鍵比當前節點的鍵大，遞歸右子樹
插入的鍵等于當前節點的鍵，說明已經插入過了，本次插入是失敗的
然后開始new一個新的結點，把結點之前的父子關系處理好

AVL樹的調整（旋轉）

如果在一棵原本是平衡的AVL樹中插入一個新的結點，可能會造成不平衡的情況，此時就必須要調整A樹的結構，使其平衡話。AVL樹的旋轉大致分為四種，這里采用畫圖的方式來理解這四種旋轉的方式：

左左：右單旋

在這里插入圖片描述

右右：左單旋

在這里插入圖片描述

左右：先左旋，后右旋

在這里插入圖片描述
這里的插入情況不唯一，但是值得一提的是
在調整之后，subLR的左子樹一定是充當subL的右子樹，subLR的右子樹一定是充當了parent的左子樹，可以根據這個來計算平衡因子

右左：先右旋，后左旋

在這里插入圖片描述
同左右情況，這里也有相似的結論：
再調整之后，subRL的左子樹充當為parent的右子樹，subRL的右子樹充當為subR的左子樹

AVL樹的完整實現代碼

#include <iostream>
#include <cassert>template <class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;std::pair<K, V> _kv;int _bf;//平衡因子AVLTreeNode(const std::pair<K, V>& kv) : _left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};template <class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;public:bool Insert(const std::pair<K,V>&kv){Node* cur = _root;Node* parent = nullptr;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 == nullptr){_root = cur;return true;}if (parent->_kv.first < kv.first){parent->_right = cur;}elseparent->_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){//說明之前是0，需要繼續向上更新cur = parent;parent = parent->_parent;}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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else {//理論上不可能出現這種情況assert(false);}}return true;}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;}void InOrder(){_InOrder(_root);}//右旋轉void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//整棵樹的根節點if (parent == _root){_root = subL;_root->_parent = nullptr;}//某個子樹的根節點else{subL->_parent = ppNode;if (ppNode->_left == parent){ppNode->_left = subL;}else {ppNode->_right = subL;}}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;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else {subR->_parent = ppNode;if (parent == ppNode->_left){ppNode->_left = subR;}else {ppNode->_right = subR;}}parent->_bf = subR->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){//說明是在subLR的左邊插入subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){//說明是在subLR的右邊插入subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 0) {subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}
private:bool _IsBalance(Node*node){if (node == nullptr)return true;int leftHeight = _Height(node->_left);int rightHeight = _Height(node->_right);if (abs(leftHeight - rightHeight) >= 2)return false;//檢查一下平衡因子是否是正確的if (rightHeight - leftHeight != node->_bf){std::cout << node->_kv.first << std::endl;return false;}return _IsBalance(node->_left) &&_IsBalance(node->_right);}int _Height(Node* node){if (node == nullptr)return 0;return std::max(_Height(node->_left), _Height(node->_right)) + 1;}void _InOrder(Node* node){//中序遍歷if (node == nullptr)return;_InOrder(node->_left);std::cout << node->_kv.first << ": " << node->_kv.second << std::endl;_InOrder(node->_right);}
private:Node* _root = nullptr; // 根節點
};

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/86719.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/86719.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/86719.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！