您好,登錄后才能下訂單哦!
這篇“C++ AVLTree高度平衡的二叉搜索樹怎么實(shí)現(xiàn)”文章的知識(shí)點(diǎn)大部分人都不太理解,所以小編給大家總結(jié)了以下內(nèi)容,內(nèi)容詳細(xì),步驟清晰,具有一定的借鑒價(jià)值,希望大家閱讀完這篇文章能有所收獲,下面我們一起來看看這篇“C++ AVLTree高度平衡的二叉搜索樹怎么實(shí)現(xiàn)”文章吧。
二叉搜索樹雖可以縮短查找的效率,但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹,查找元素相當(dāng)于在順序表中搜索元素,效率低下。
因此,兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法:當(dāng)向二叉搜索樹中插入新結(jié)點(diǎn)后,如果能保證每個(gè)結(jié)點(diǎn)的左右子樹高度之差的絕對(duì)值不超過1(需要對(duì)樹中的結(jié)點(diǎn)進(jìn)行調(diào)整),即可降低樹的高度,從而減少平均搜索長度。
一棵AVL樹或者是空樹,或者是具有以下性質(zhì)的二叉搜索樹:
它的左右子樹都是AVL樹
左右子樹高度之差(簡稱平衡因子)的絕對(duì)值不超過1(-1/0/1)
平衡因子= 右子樹高度-左子樹高度
如果一棵二叉搜索樹是高度平衡的,它就是AVL樹。如果它有n個(gè)結(jié)點(diǎn),其高度可保持在O(log2N) ,搜索時(shí)間復(fù)雜度O(log2N)
節(jié)點(diǎn)結(jié)構(gòu):三叉鏈結(jié)構(gòu)(左、右、父),以及平衡因子bf+構(gòu)造函數(shù)(左右為空,平衡因子初始化為0)
template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf;//balance factor AVLTreeNode(const pair<K,V>&kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };
AVL樹在二叉搜索樹的基礎(chǔ)上引入了平衡因子,因此AVL樹也可以看成是二叉搜索樹。步驟過程:
找到插入的位置:根據(jù)二叉搜索樹的做法
進(jìn)行插入:判斷插入的位置是parent的左還是右
更新平衡因子:如果不平衡的話,就要進(jìn)行旋轉(zhuǎn)
找到插入位置(比較節(jié)點(diǎn)大小即可):
插入的節(jié)點(diǎn)key值 >
當(dāng)前位置的key值,往右子樹走
插入的節(jié)點(diǎn)key值 <
當(dāng)前位置的key值,往左子樹走
插入的節(jié)點(diǎn)key值等于當(dāng)前位置的key值,不能插入,返回false
插入之后,與二叉搜索樹不同的是:我們還需要去進(jìn)行平衡因子的更新,調(diào)平衡:
如果新增加的在右,平衡因子加加
如果新增加的在左,平衡因子減減
更新一個(gè)結(jié)點(diǎn)之后我們需要去進(jìn)行判斷,子樹的高度是否發(fā)生了變化:
1.如果parent的平衡因子是0:說明之前parent的平衡因子是1或-1,說明之前parent一邊高、一邊低;這次插入之后填入矮的那邊,parent所在的子樹高度不變,不需要繼續(xù)往上更新
2.如果parent的平衡因子是1或者-1:說明之前parent的平衡因子是0,兩邊一樣高,插入之后一邊更高,parent所在的子樹高度發(fā)生變化,繼續(xù)往上更新
3.平衡因子是2或-2,說明之前parent的平衡因子是1或-1,現(xiàn)在插入嚴(yán)重不平衡,違反規(guī)則,需要進(jìn)行旋轉(zhuǎn)處理
最壞的情況下:需要一直更新到根root:
我們更新平衡因子時(shí)第一個(gè)更新的就是parent,如果parent->_bf1或parent->_bf-1需要繼續(xù)往上進(jìn)行平衡因子的更新,向上迭代,直到parent為空的情況:
else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; }
當(dāng)parent->_bf = 2或parent->_bf==-2時(shí),我們就需要進(jìn)行旋轉(zhuǎn)了:
????如果parent的平衡因子是2,cur的平衡因子是1時(shí),說明右邊的右邊比較高,我們需要進(jìn)行左單旋
????如果parent的平衡因子是-2,cur的平衡因子是-1時(shí),說明左邊的左邊比較高,我們需要進(jìn)行右單旋
????如果parent的平衡因子是-2,cur的平衡因子是1時(shí),我們需要進(jìn)行左右雙旋
????如果parent的平衡因子是2,cur的平衡因子是-1時(shí),我們需要進(jìn)行右左雙旋
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; 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->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } //更新平衡因子 while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } else if(parent->_bf==2||parent->_bf==-2) { //左旋轉(zhuǎn) 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) { RotateLR(parent); } //右左雙旋 else if (parent->_bf ==2&&cur->_bf ==-1) { RotateRL(parent); } else { assert(false); } break; } else { assert(false); } } return true; }
在一棵原本是平衡的AVL樹中插入一個(gè)新節(jié)點(diǎn),可能造成不平衡,此時(shí)必須調(diào)整樹的結(jié)構(gòu),使之平衡化。根據(jù)節(jié)點(diǎn)插入位置的不同,AVL樹的旋轉(zhuǎn)分為四種。
旋轉(zhuǎn)規(guī)則:
1.讓這顆子樹左右高度差不超過1
2.旋轉(zhuǎn)過程中繼續(xù)保持它是搜索樹
3.更新調(diào)整孩子節(jié)點(diǎn)的平衡因子
4.讓這顆子樹的高度根插入前保持一致
新節(jié)點(diǎn)插入較高右子樹的右側(cè)—右右:左單旋
抽象圖:
a/b/c是高度為h的AVL子樹,代表多數(shù)情況:h>=0,其中h可以等于0、1、2…,不過都可以抽象成h,處理情況都一樣:此時(shí)parent等于2,subR等于1。
具體左旋的步驟:
subRL成為parent的右子樹:注意subL和parent
的關(guān)系,調(diào)整parent的右以及subRL的父(subRL可能為空)
parent成為subR的左子樹:調(diào)整parent的父與subR的左
subR成為相對(duì)的根節(jié)點(diǎn):調(diào)整subR與ppNode:注意parent是不是整棵樹的root,如果是,則讓subR為_root,同時(shí)讓_root->_parent置為空
更新平衡因子
左旋調(diào)整:subR的左子樹值(subRL)本身就比parent的值要大,所以可以作為parent的右子樹;而parent及其左子樹當(dāng)中結(jié)點(diǎn)的值本身就比subR的值小,所以可以作為subR的左子樹。
**更新平衡因子bf:**subR與parent的bf都更新為0
代碼實(shí)現(xiàn)左旋轉(zhuǎn):
//左單旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (ppNode == nullptr) { _root = subR; _root->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } parent->_bf = subR->_bf = 0; }
新節(jié)點(diǎn)插入較高左子樹的左側(cè)—左左:右單旋
有了前面左旋的基礎(chǔ),我們?cè)趤砜从倚蜎]有那么費(fèi)勁了:
a/b/c是高度為h的AVL樹,右旋旋轉(zhuǎn)動(dòng)作:b變成60的左邊,60變成30的右邊,30變成子樹的根。
30比60小,b值是處于30和60之間,此時(shí)作為60的左邊是沒有問題的。
有了這個(gè)圖,在結(jié)合前面左單旋的基礎(chǔ),我們就能很快實(shí)現(xiàn)我們的右單旋代碼:
//右單旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* ppNode = parent->_parent; parent->_parent = subL; subL->_right = parent; //if(_root==parent) if (ppNode == nullptr) { _root = subL; _root->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } subL->_bf = parent->_bf = 0; }
新節(jié)點(diǎn)插入較高左子樹的右側(cè)—左右:先左單旋再右單旋
a/d是高度為h的AVL樹,b/c是高度為h-1的AVL樹。
以30為軸點(diǎn)進(jìn)行左單旋:b變成30的右邊,30變成60的左邊,60變成子樹根
以90為軸點(diǎn)進(jìn)行右單旋:c變成90的左邊,90變成60的右邊,60變成子樹的根
左右雙旋:以subL為軸點(diǎn)左旋,以parent為軸點(diǎn)進(jìn)行右旋,在進(jìn)行平衡因子的更新(最大的問題)
我們從總體的角度來看,左右雙旋的結(jié)果就是:就是把subLR的左子樹和右子樹,分別作為subL和parent的右子樹和左子樹,同時(shí)subL和parent分別作為subLR的左右子樹,最后讓subLR作為整個(gè)子樹的根
subLR的左子樹作為subL的右子樹:因?yàn)閟ubLR的左子樹結(jié)點(diǎn)比subL的大
subLR的右子樹作為parent的左子樹:因?yàn)閟ubLR的右子樹結(jié)點(diǎn)比parent的小
平衡因子的更新:重新判斷(識(shí)別插入節(jié)點(diǎn)是在b還是在c)根據(jù)subLR平衡因子的初始情況進(jìn)行分類:
如果subLR初始平衡因子是-1時(shí),左右雙旋后parent、subL、subLR的平衡因子分別更新為1、0、0(插入在b)
如果subLR的初始平衡因子是1時(shí),左右雙旋后parent、subL、subLR的平衡因子分別更新為0、-1、0(插入在c)
如果subLR初始平衡因子是0時(shí),左右雙旋后parent、subL、subLR的平衡因子分別更新為0、0、0(subLR自己新增)
代碼實(shí)現(xiàn):
//左右雙旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR ->_bf; RotateL(parent->_left); RotateR(parent); //更新平衡因子 if (bf == -1)//b插入,subLR左子樹新增 { subL->_bf = 0; parent->_bf = 1; subLR->_bf = 0; } else if (bf == 1)//c插入,subLR右子樹新增 { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == 0)//subLR自己新增加 { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } }
新節(jié)點(diǎn)插入較高右子樹的左側(cè)—右左:先右單旋再左單旋
插入
subR為軸點(diǎn)進(jìn)行右單旋:
parent為軸進(jìn)行左單旋:
既右左雙旋:
右左雙旋后,根據(jù)subRL 初始平衡因子的不同分為三種情況分別對(duì)應(yīng)subRL
= 0、1、-1情況,與左右雙旋情況類似。
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); 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); } }
AVL樹是在二叉搜索樹的基礎(chǔ)上加入了平衡性的限制,因此要驗(yàn)證AVL樹,可以分兩步:
驗(yàn)證其為二叉搜索樹
如果中序遍歷可得到一個(gè)有序的序列,就說明為二叉搜索樹
void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); }
驗(yàn)證其為平衡樹
每個(gè)節(jié)點(diǎn)子樹高度差的絕對(duì)值不超過1(注意節(jié)點(diǎn)中如果沒有平衡因子)節(jié)點(diǎn)的平衡因子是否計(jì)算正確
如果是空樹,是AVL樹;高度差不大于2,并且遞歸左右子樹的高度差都不大于2,也是AVL樹;判斷平衡因子和該點(diǎn)的高度差是否相等
//求高度 int Height(Node* root) { if (root == nullptr) return 0; int lh = Height(root->_left); int rh = Height(root->_right); return lh > rh ? lh + 1 : rh + 1; } //判斷平衡 bool IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子異常" << endl; return false; } return abs(rightHeight - leftHeight) < 2 && IsBalance(root->_left) && IsBalance(root->_right); }
AVL樹是一棵絕對(duì)平衡的二叉搜索樹,其要求每個(gè)節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值都不超過1,這樣可以保證查詢時(shí)高效的時(shí)間復(fù)雜度即log2( N) 。但是如果要對(duì)AVL樹做一些結(jié)構(gòu)修改的操作,性能非常低下,比如:插入時(shí)要維護(hù)其絕對(duì)平衡,旋轉(zhuǎn)的次數(shù)比較多,更差的是在刪除時(shí),有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。
因此:如果需要一種查詢高效且有序的數(shù)據(jù)結(jié)構(gòu),而且數(shù)據(jù)的個(gè)數(shù)為靜態(tài)的(即不會(huì)改變),可以考慮AVL樹,但一個(gè)結(jié)構(gòu)經(jīng)常修改,就不太適合.
送上源碼:
#pragma once #include <iostream> #include <assert.h> #include <time.h> using namespace std; template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf;//balance factor AVLTreeNode(const pair<K,V>&kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} }; template <class K,class V> struct AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; 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->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } //更新平衡因子 while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } else if(parent->_bf==2||parent->_bf==-2) { //左旋轉(zhuǎn) 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) { RotateLR(parent); } //右左雙旋 else if (parent->_bf ==2&&cur->_bf ==-1) { RotateRL(parent); } else { assert(false); } break; } else { assert(false); } } return true; } //左單旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (ppNode == nullptr) { _root = subR; _root->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } parent->_bf = subR->_bf = 0; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* ppNode = parent->_parent; parent->_parent = subL; subL->_right = parent; //if(_root==parent) if (ppNode == nullptr) { _root = subL; _root->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } subL->_bf = parent->_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 == -1)//b插入,subLR左子樹新增 { subL->_bf = 0; parent->_bf = 1; subLR->_bf = 0; } else if (bf == 1)//c插入,subLR右子樹新增 { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == 0)//subLR自己新增加 { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } } //右左雙旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); 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 InOrder() { _InOrder(_root); } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } int Height(Node* root) { if (root == nullptr) return 0; int lh = Height(root->_left); int rh = Height(root->_right); return lh > rh ? lh + 1 : rh + 1; } bool IsBalance() { return IsBalance(_root); } bool IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子異常" << endl; return false; } return abs(rightHeight - leftHeight) < 2 && IsBalance(root->_left) && IsBalance(root->_right); } private: Node* _root = nullptr; }; //測試 void TestAVLTree() { //int a[] = { 8,3,1,10,6,4,7,14,13 }; //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; int a[] = { 4,2,6,1,3,5,15,7,16,14 }; AVLTree<int, int> t; for (auto e : a) { t.Insert(make_pair(e,e)); } t.InOrder(); cout << t.IsBalance() << endl; } void TestAVLTree2() { srand(time(0)); const size_t N = 100000; AVLTree<int, int> t; for (size_t i = 0; i < N; i++) { size_t x = rand(); t.Insert(make_pair(x, x)); } //t.InOrder(); cout << t.IsBalance() << endl; }
以上就是關(guān)于“C++ AVLTree高度平衡的二叉搜索樹怎么實(shí)現(xiàn)”這篇文章的內(nèi)容,相信大家都有了一定的了解,希望小編分享的內(nèi)容對(duì)大家有幫助,若想了解更多相關(guān)的知識(shí)內(nèi)容,請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。