廊坊網(wǎng)站建設(shè)公司企業(yè)文化ppt
前言
學(xué)習(xí)了普通二叉樹,發(fā)現(xiàn)普通二叉樹作用不大,于是我們學(xué)習(xí)了搜索二叉樹,給二叉樹新增了搜索、排序、去重等特性,
但是,在極端情況下搜索二叉樹會退化成單邊樹,搜索的時間復(fù)雜度達(dá)到了O(N),這是十分不利的,
所以,牛人們又提出了新的數(shù)據(jù)結(jié)構(gòu):AVL樹(平衡搜索二叉樹),給搜索二叉樹新增了平衡的特性,控制左右子樹的高度,是搜索二叉樹處于平衡的狀態(tài),避免出現(xiàn)極端情況。
AVL樹的發(fā)明者是兩位俄羅斯數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis,為了幾年他們在1962年提出該數(shù)據(jù)結(jié)構(gòu),就命名為AVL樹。
AVL樹的特性
AVL樹要求任意節(jié)點(diǎn)的左右子樹的高度差的絕對值不超過1.
為什么擁有該特性AVL樹就可以保持平衡呢?這里需要數(shù)學(xué)證明,就不解釋了,理解原理后,就很容易理解。
一棵AVL樹是具有以下性質(zhì)的二叉搜索樹:
- 它的左右子樹都是AVL樹
- 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
注意:在這里,我們引入一個變量,平衡因子(balance factor),用來記錄左右子樹的高度差,
這里我們記錄右子樹的高度減左子樹的高度。
當(dāng)然,也可以有其他的思路來替代平衡因子。
AVL樹節(jié)點(diǎn)的定義(以KV型為例)
template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K,V>* _left = nullptr;//左子節(jié)點(diǎn)AVLTreeNode<K, V>* _right = nullptr;//右子節(jié)點(diǎn)AVLTreeNode<K, V>* _parent = nullptr;//父親節(jié)點(diǎn)pair<K, V> _kv;//數(shù)據(jù)int _bf = 0;//平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv){}
};
注意:AVL樹使用三叉鏈實(shí)現(xiàn),多了一個parent指針,用來記錄父親節(jié)點(diǎn),方便使用。
AVL樹的插入(核心)
AVL樹是在搜索二叉樹上面進(jìn)行升級,所以查找的方法和搜索二叉樹類似,大了就向右子樹走,小了就往左子樹走。
因?yàn)檫@里多了parent指針和bf,在插入之后都需要進(jìn)行維護(hù)。(天下沒有白吃的午餐,使用的時候方便,維護(hù)起來就麻煩了QAQ)
parent指針處理起來很簡單,我們這里主要講bf如何控制。
bf有三種取值 0 , - 1 , 1
當(dāng)我們在節(jié)點(diǎn)的右側(cè)插入的時候,節(jié)點(diǎn)的bf++,在節(jié)點(diǎn)的左側(cè)插入的時候,節(jié)點(diǎn)的bf–。
在右邊插入,右子樹的高度增加,bf++,在左邊插入的時候,左子樹的高度增加,bf–
這是毫無疑問的,以下都基于此。
OK,更新完當(dāng)前節(jié)點(diǎn)之后,bf就維護(hù)好了嗎?
哪有這么簡單QAQ
在插入后cur的bf更新為1,僅僅如此嗎?
看這張圖,parent的bf也要從1變成2了。
所以,在更新完cur節(jié)點(diǎn)的bf后,還需要根據(jù)情況確定是否要繼續(xù)向上更新
具體是否要更新,主要是看子樹的高度有沒有發(fā)生變化
有哪些情況呢?
- cur插入后更新為0
說明原來是1 或者 -1,在較短的那一條邊上新增了新節(jié)點(diǎn),將cur節(jié)點(diǎn)變平衡了,
這樣的話,那高度就沒有增加,不會影響到子樹的高度,就不需要向上更新bf了。- cur插入后更新為 1,-1
說明原來是0,原來是平衡的,插入新節(jié)點(diǎn)后破壞了平衡,子樹高度發(fā)生了變化,
所以需要向上更新bf。- cur插入后更新為 2,-2
當(dāng)更新為2,-2后,發(fā)現(xiàn)違反了AVL樹的規(guī)則,不再是一顆AVL樹,我們就需要進(jìn)
行特殊操作來維護(hù)AVL樹的性質(zhì)了。(這里,我們采用旋轉(zhuǎn))
AVL樹的旋轉(zhuǎn)(最難的部分)
AVL樹的旋轉(zhuǎn)是AVL樹這個數(shù)據(jù)結(jié)構(gòu)的亮點(diǎn),掌握了這一點(diǎn)之后,才會理解這種數(shù)據(jù)結(jié)構(gòu)有多么精妙。
從深層上看,AVL樹的旋轉(zhuǎn)分為四種情況,我們畫圖來分析。(由于實(shí)際情況太多太多,我們這里畫抽象圖)
左單旋
這里h >= 0
我們在最右邊插入一個節(jié)點(diǎn),使AVL樹的右側(cè)完全傾斜,那么我們就需要向左側(cè)旋轉(zhuǎn)了。
如何向左旋轉(zhuǎn)呢?
我們將三個需要用到的節(jié)點(diǎn)命名一下,分別為parent,subR,以及subRL
根據(jù)搜索二叉樹的性質(zhì),我們知道subRL > parent ,但是小于subR,所以就可以進(jìn)行左單旋而不會破壞搜索的性質(zhì)
左單旋就是
先將subRL插入到parent的右邊
接著將parent插入到subR的左邊
成功旋轉(zhuǎn)之后圖形變成下面的樣子
這樣左右子樹的高度就一樣了,重新將AVL樹調(diào)整平衡了
這里還有非常多的代碼細(xì)節(jié),例如空指針,parent指針的維護(hù)等等需要處理,這里大家可以先嘗試根據(jù)思路寫出代碼,再跟后面的代碼進(jìn)行比較,看看是否寫對了。
這里只簡單講一下平衡因子的維護(hù)。
可以看到,在左單旋只會影響parent和subR兩個節(jié)點(diǎn)的bf,且旋轉(zhuǎn)后皆為0,故不用向上繼續(xù)調(diào)整。
右單旋
右單旋和左單旋類似,是對稱的,這里只簡單畫出抽象圖,相信讀者能夠自己理解。
右單旋就是處理左邊完全傾斜的情況,向右邊旋轉(zhuǎn),進(jìn)而調(diào)整平衡。
代碼依舊在文末尾給出。
右左雙旋
顧名思義,先右單旋后左單旋構(gòu)成右左雙旋。
相信聰明的小伙伴,在看到左單旋和右單旋的時候,就會發(fā)現(xiàn)這兩種情況都是插入在最右邊和最左邊造成完全傾斜。
而插入在右子樹的左邊和左子樹的右邊都沒有列舉出來。
這里右左雙旋就是應(yīng)對插入在右子樹的左邊這種情況的,顯然,左右雙旋就是應(yīng)對插入在左子樹的右邊那種情況的,這里講右左雙旋,左右雙旋留給大家自己思考。
左單旋和右單旋都不適合這種情況,根本原因在于,這種情況并不是完全傾斜,很簡單嘛,
你不是完全傾斜,我強(qiáng)行讓你變成完全傾斜,不就可以使用左單旋或者右單旋了嘛。
對于這種情況,我們可以看到是subRL太高了,導(dǎo)致的不平衡,我們將subRL旋轉(zhuǎn)到subR的位置豈不是可以造成完全傾斜了嗎?
這右單旋不就來了嘛,使用右單旋就將subRL的右插入到subR的左,再將subR插入到subRL的右即可。
右單旋完了之后,就是下面的圖形
映入眼簾的就是右邊太高了,出現(xiàn)了完全傾斜,直接左單旋調(diào)整平衡即可。
這里同樣有很多代碼細(xì)節(jié),要維護(hù)好parent和bf,以及處理好空指針的特殊情況。
這里還是只簡單講一下bf的維護(hù)
我們以終為始,只看旋轉(zhuǎn)前和旋轉(zhuǎn)后的兩幅圖。
我們可以看到只有三個節(jié)點(diǎn)60 30 90的bf發(fā)生了變化。
也就是只有parent,subR,subRL三個節(jié)點(diǎn)的bf發(fā)生了變化。
這里最后subRL和subR的bf 變成了0,parent的bf變成了-1。
但是,一定是這樣嗎?
這中情況是在c子樹上插入新節(jié)點(diǎn),如果在b上插入新節(jié)點(diǎn)。
a和b的高度都是h,parent的bf就是0,c的高度是h-1,d的高度是h,subR的bf就是1
問題就在于是在subRL的左子樹插入還是右子樹插入新節(jié)點(diǎn)。
如何分辨?
很簡單,去觀察subRL的旋轉(zhuǎn)前的bf
如果是1,就是在右子樹插入,如果是-1,就是在左子樹插入
左右雙旋
大體和右左雙旋類似,所以這里簡單畫個抽象圖,相信讀者能夠自行理解。
這里就是新節(jié)點(diǎn)插入在了左子樹的右邊,導(dǎo)致不平衡,先左單旋調(diào)整成完全傾斜,在右單旋調(diào)整至平衡。
代碼
#include <assert.h>
#include <iostream>using namespace std;namespace Avltree//命名空間名不能和類名相同,不然會發(fā)生命名沖突
{template<class K, class V>struct AVLTreeNode{AVLTreeNode<K,V>* _left = nullptr;AVLTreeNode<K, V>* _right = nullptr;AVLTreeNode<K, V>* _parent = nullptr;pair<K, V> _kv;int _bf = 0;//平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv){}};template<class K,class V>class AVLTree{typedef AVLTreeNode<K, V> Node;private:Node* _root = nullptr;//開始的時候要給空,不然就是野指針了void RotateL(Node* parent)//左單旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;if (pparent == nullptr){subR->_parent = nullptr;_root = subR;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent)//右單旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;if (pparent == nullptr){subL->_parent = nullptr;_root = subL;}else{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}parent->_bf = 0;subL->_bf = 0;}void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}void InOrder(Node* root){if (root == nullptr)return;InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;InOrder(root->_right);}public:void inorder(){InOrder(_root);}bool find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first){cur = cur->_right;}else if (key < cur->_kv.first){cur = cur->_left;}else{return true;}}return false;}bool insert(const pair<K, V>& kv){if (_root == nullptr)//插入的時候要特殊處理空樹{_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;//如果已經(jīng)在,那就插入失敗,返回false}}//找到了,開始插入;cur = new Node(kv);cur->_parent = parent;if (kv.first > parent->_kv.first)//插入的節(jié)點(diǎn)很大,插在右邊{parent->_bf++;parent->_right = cur;}else{parent->_bf--;parent->_left = cur;}//插入完成,調(diào)整平衡因子;while (parent){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)//右邊高,但是偏了{(lán)Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateRL(parent);if (bf == 0){parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){subRL->_bf = subR->_bf = 0;parent->_bf = -1;}else if(bf == -1){subRL->_bf = parent->_bf = 0;subR->_bf = 1;}else{assert(false);}}else if (parent->_bf == -2 && cur->_bf == 1)//左邊高但是偏向右邊{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateLR(parent);if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = subLR->_bf = 0;}else if(bf == -1){subLR->_bf = subL->_bf = 0;parent->_bf = 1;}else{assert(false);}}}else{assert(false);//走到這里來就出現(xiàn)錯誤了}}return true;}};
}
對于AVL樹的刪除,和插入類似,但是更加復(fù)雜些,限于篇幅,就暫且不講AVL樹的刪除了,感興趣的讀者可以參考《算法導(dǎo)論》和《數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++語言描述)》(殷人昆版)。