中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

廊坊網(wǎng)站建設(shè)公司企業(yè)文化ppt

廊坊網(wǎng)站建設(shè)公司,企業(yè)文化ppt,網(wǎng)站設(shè)計(jì)需要的元素,做網(wǎng)站能用思源黑體嗎前言 學(xué)習(xí)了普通二叉樹,發(fā)現(xiàn)普通二叉樹作用不大,于是我們學(xué)習(xí)了搜索二叉樹,給二叉樹新增了搜索、排序、去重等特性, 但是,在極端情況下搜索二叉樹會退化成單邊樹,搜索的時間復(fù)雜度達(dá)到了O(N),這…

前言

學(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ì)的二叉搜索樹:

  1. 它的左右子樹都是AVL樹
  2. 左右子樹高度之差(簡稱平衡因子)的絕對值不超過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ā)生變化

有哪些情況呢?

  1. cur插入后更新為0
    說明原來是1 或者 -1,在較短的那一條邊上新增了新節(jié)點(diǎn),將cur節(jié)點(diǎn)變平衡了,
    這樣的話,那高度就沒有增加,不會影響到子樹的高度,就不需要向上更新bf了。
  2. cur插入后更新為 1,-1
    說明原來是0,原來是平衡的,插入新節(jié)點(diǎn)后破壞了平衡,子樹高度發(fā)生了變化,
    所以需要向上更新bf。
  3. 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++語言描述)》(殷人昆版)。


http://www.risenshineclean.com/news/53177.html

相關(guān)文章:

  • php做的大型網(wǎng)站有哪些網(wǎng)站搭建費(fèi)用
  • 有了域名之后怎么做網(wǎng)站網(wǎng)頁設(shè)計(jì)與制作代碼成品
  • 個人網(wǎng)站名稱 備案短視頻seo公司
  • 企業(yè)手機(jī)網(wǎng)站建設(shè)策劃怎么在網(wǎng)上做廣告宣傳
  • 武漢住建局官方網(wǎng)站使用最佳搜索引擎優(yōu)化工具
  • 電影題材網(wǎng)頁設(shè)計(jì)欣賞seo報名在線咨詢
  • 外匯申報在哪個網(wǎng)站上做如何做網(wǎng)站seo
  • 主機(jī)屋做淘寶客網(wǎng)站網(wǎng)絡(luò)服務(wù)包括哪些內(nèi)容
  • 做自己的網(wǎng)站的好處windows優(yōu)化大師和360哪個好
  • 新鄉(xiāng)商城網(wǎng)站建設(shè)哪家專業(yè)自己手機(jī)怎么免費(fèi)做網(wǎng)站
  • ip地址進(jìn)入網(wǎng)站怎么做的seo站內(nèi)優(yōu)化和站外優(yōu)化
  • wordpress點(diǎn)擊閱讀全文seo怎么優(yōu)化效果更好
  • 做微信網(wǎng)站公司哪家好太原關(guān)鍵詞排名提升
  • 武漢建網(wǎng)公司網(wǎng)站建設(shè)一個新手怎么做推廣
  • 廣州微信網(wǎng)站建設(shè)咨詢網(wǎng)站建設(shè)關(guān)鍵詞排名
  • 昆明做網(wǎng)站哪家好佛山市人民政府門戶網(wǎng)站
  • 武漢品牌網(wǎng)站建設(shè)公司哪家好在哪里可以免費(fèi)自學(xué)seo課程
  • 山東省疫情防控最新政策seo外包收費(fèi)
  • 外貿(mào)工廠 網(wǎng)站建設(shè)百度關(guān)鍵詞規(guī)劃師入口
  • 企業(yè)如何創(chuàng)建網(wǎng)站邢臺網(wǎng)站公司
  • 有沒有網(wǎng)站可以學(xué)做床上用品系統(tǒng)優(yōu)化大師下載
  • 河南seo網(wǎng)站策劃上海站優(yōu)云網(wǎng)絡(luò)科技有限公司
  • 百度官網(wǎng)認(rèn)證網(wǎng)站關(guān)鍵詞歌曲歌詞
  • asp網(wǎng)站編輯教程汕頭seo優(yōu)化項(xiàng)目
  • wordpress 標(biāo)簽手冊關(guān)鍵詞優(yōu)化包年推廣
  • 好看的 網(wǎng)站正在建設(shè)中源碼福州短視頻seo網(wǎng)站
  • 建站排名教育培訓(xùn)網(wǎng)站
  • 網(wǎng)頁網(wǎng)站免費(fèi)佛山快速排名seo
  • 白城網(wǎng)站建設(shè)網(wǎng)站制作公司高端
  • 美武漢有什么網(wǎng)站建設(shè)公司好磁力鏈