數(shù)據(jù)結(jié)構(gòu)與算法系列(AVL樹)

AVL樹

AVL樹,也稱平衡二叉搜索樹狸窘,AVL是其發(fā)明者姓名簡寫耳标。AVL樹屬于樹的一種岂嗓,而且它也是一棵二叉搜索樹狰右,不同的是他通過一定機(jī)制能保證二叉搜索樹的平衡恃轩,平衡的二叉搜索樹的查詢效率更高篙程。

AVL樹特點(diǎn)

  • AVL樹是一棵二叉搜索樹藏畅。
  • AVL樹的左右子節(jié)點(diǎn)也是AVL樹怔蚌。
  • AVL樹擁有二叉搜索樹的所有基本特點(diǎn)巩步。
  • 每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)的高度之差的絕對值最多為1,即平衡因子為范圍為[-1,1]桦踊。
image.png

圖中紅色數(shù)字表示對應(yīng)節(jié)點(diǎn)的高度椅野,可以看到同一層的節(jié)點(diǎn)高度差都沒有超過1。

二叉搜索樹的平衡

基礎(chǔ)的二叉搜索樹構(gòu)建出來可能會(huì)存在不平衡的現(xiàn)象籍胯,比如極端情況下竟闪,按照A B C D E F G H順序插入樹中,結(jié)果為杖狼,

image.png

但實(shí)際上我們更想要平衡一點(diǎn)的二叉搜索樹炼蛤,因?yàn)槠胶獾亩嫠阉鳂淠苡行岣卟樵冃剩热缟厦娴囊樵儭癏”節(jié)點(diǎn)則需要比較8個(gè)節(jié)點(diǎn)才找到蝶涩,而平衡的二叉搜索樹只需要比較3個(gè)節(jié)點(diǎn)理朋。

所以AVL樹的出現(xiàn)就是為了解決平衡性問題絮识,它的核心內(nèi)容就是平衡處理機(jī)制,即所謂的旋轉(zhuǎn)嗽上,一共有四種形式的旋轉(zhuǎn):右單旋次舌、左單旋、左右雙旋和右左雙旋兽愤。

為什么要旋轉(zhuǎn)

不管是什么方式的旋轉(zhuǎn)彼念,旋轉(zhuǎn)的目的是為了降低樹的高度,使其平衡烹看,假如樹結(jié)構(gòu)如下圖国拇,

image.png

將“A”節(jié)點(diǎn)添加到樹中,變成如下結(jié)構(gòu)惯殊,樹產(chǎn)生了不平衡酱吝,于是檢查哪里不平衡,當(dāng)?shù)健癈”節(jié)點(diǎn)時(shí)發(fā)現(xiàn)高度差超過1土思,

image

所以需要對“C”節(jié)點(diǎn)進(jìn)行右單旋操作將高度降到2务热,達(dá)到平衡。

image.png

插入方式

AVL樹一共有四種插入方式己儒,根據(jù)插入方式不同需要做不同的旋轉(zhuǎn)操作崎岂,現(xiàn)在往下看四種插入方式,設(shè)受插入節(jié)點(diǎn)影響而失去平衡的節(jié)點(diǎn)的父節(jié)點(diǎn)為Z闪湾,

  • LL插入方式冲甘,插入的節(jié)點(diǎn)在Z節(jié)點(diǎn)的左子樹的左子樹上,如下圖途样,“A”節(jié)點(diǎn)插入影響“C”節(jié)點(diǎn)的平衡江醇,“C”的父節(jié)點(diǎn)為“E”,插入節(jié)點(diǎn)“A”在“E”節(jié)點(diǎn)的左子樹的左子樹上何暇。即“B”節(jié)點(diǎn)的左右子節(jié)點(diǎn)都算LL插入陶夜。


    image.png
  • RR插入方式,插入的節(jié)點(diǎn)在Z節(jié)點(diǎn)的右子樹的右子樹上裆站,如下圖条辟,“I”節(jié)點(diǎn)插入影響“G”節(jié)點(diǎn)的平衡,“G”的父節(jié)點(diǎn)為“E”宏胯,插入節(jié)點(diǎn)“I”在“E”節(jié)點(diǎn)的右子樹的右子樹上羽嫡。即“H”節(jié)點(diǎn)的左右子節(jié)點(diǎn)都算RR插入。
image.png
  • LR插入方式肩袍,插入的節(jié)點(diǎn)在Z節(jié)點(diǎn)的左子樹的右子樹上杭棵,如下圖,“C”節(jié)點(diǎn)插入影響“B”節(jié)點(diǎn)的平衡了牛,“B”的父節(jié)點(diǎn)為“E”颜屠,插入節(jié)點(diǎn)“C”在“E”節(jié)點(diǎn)的左子樹的右子樹上。即“D”節(jié)點(diǎn)的左右子節(jié)點(diǎn)都算LR插入鹰祸。


    image.png
  • RL插入方式甫窟,插入的節(jié)點(diǎn)在Z節(jié)點(diǎn)的右子樹的左子樹上,如下圖蛙婴,“G”節(jié)點(diǎn)插入影響“H”節(jié)點(diǎn)的平衡粗井,“H”的父節(jié)點(diǎn)為“E”,插入節(jié)點(diǎn)“G”在“E”節(jié)點(diǎn)的右子樹的左子樹上街图。即“F”節(jié)點(diǎn)的左右子節(jié)點(diǎn)都算RL插入浇衬。


    image.png

右單旋

右單旋用于處理LL插入方式,假設(shè)存在一棵樹餐济,如下耘擂,

image.png

現(xiàn)插入“A”節(jié)點(diǎn),假如不進(jìn)行旋轉(zhuǎn)的話絮姆,樹結(jié)構(gòu)為下圖醉冤,所以遍歷過程也會(huì)檢查哪里不平衡,檢查到“C”節(jié)點(diǎn)和“G”節(jié)點(diǎn)的高度差大于1篙悯,而且插入節(jié)點(diǎn)“A”屬于“E”節(jié)點(diǎn)左子樹的左子樹蚁阳,于是進(jìn)行右單旋,

image.png

“C”節(jié)點(diǎn)右單旋即將“C”節(jié)點(diǎn)提高鸽照,原本它的父節(jié)點(diǎn)“E”則變?yōu)槠溆易庸?jié)點(diǎn)螺捐,“C”節(jié)點(diǎn)原來的右子節(jié)點(diǎn)則變?yōu)槠涓腹?jié)點(diǎn)“E”的左子節(jié)點(diǎn)。右單旋后的結(jié)果如下矮燎,重新達(dá)到了平衡定血。

image.png

左單旋

左單旋用于處理RR插入方式,假設(shè)存在一棵樹漏峰,如下糠悼,


image.png

現(xiàn)插入“I”節(jié)點(diǎn),假如不進(jìn)行旋轉(zhuǎn)的話浅乔,樹結(jié)構(gòu)為下圖倔喂,所以遍歷過程也會(huì)檢查哪里不平衡,檢查到“C”節(jié)點(diǎn)和“G”節(jié)點(diǎn)的高度差大于1靖苇,而且插入節(jié)點(diǎn)“I”屬于“E”節(jié)點(diǎn)的右子樹的右子樹席噩,于是進(jìn)行左單旋,


image.png

“G”節(jié)點(diǎn)左單旋即將“G”節(jié)點(diǎn)提高贤壁,原本它的父節(jié)點(diǎn)“E”則變?yōu)槠渥笞庸?jié)點(diǎn)悼枢,“G”節(jié)點(diǎn)原來的左子節(jié)點(diǎn)則變?yōu)槠涓腹?jié)點(diǎn)“E”的右子節(jié)點(diǎn)。左單旋后的結(jié)果如下脾拆,重新達(dá)到了平衡馒索。


image.png

左右雙旋

左右雙旋用于處理LR插入方式莹妒,假設(shè)存在一棵樹,如下绰上,

image.png

現(xiàn)插入“C”節(jié)點(diǎn)旨怠,假如不進(jìn)行旋轉(zhuǎn)的話,樹結(jié)構(gòu)為下圖蜈块,遍歷過程會(huì)檢查哪里不平衡鉴腻,檢查到“B”節(jié)點(diǎn)和“G”節(jié)點(diǎn)的高度差大于1,而且插入節(jié)點(diǎn)“C”屬于“E”節(jié)點(diǎn)的左子樹的右子樹百揭,于是進(jìn)行左右雙旋爽哎,


image.png

先以“D”節(jié)點(diǎn)為軸進(jìn)行左單旋,結(jié)果為器一,

image.png

再以“D”節(jié)點(diǎn)為軸進(jìn)行右單旋课锌,得到最終結(jié)果,


image.png

右左雙旋

右左雙旋用于處理RL插入方式盹舞,假設(shè)存在一棵樹产镐,如下,

[圖片上傳中...(image.png-b8005a-1545466304454-0)]

現(xiàn)插入“G”節(jié)點(diǎn)踢步,假如不進(jìn)行旋轉(zhuǎn)的話癣亚,樹結(jié)構(gòu)為下圖,遍歷過程會(huì)檢查哪里不平衡获印,檢查到“C”節(jié)點(diǎn)和“H”節(jié)點(diǎn)的高度差大于1述雾,而且插入節(jié)點(diǎn)“G”屬于“E”節(jié)點(diǎn)的右子樹的左子樹,于是進(jìn)行右左雙旋兼丰,


image.png

先以“F”節(jié)點(diǎn)為軸進(jìn)行右單旋玻孟,結(jié)果為,


image.png

再以“F”節(jié)點(diǎn)為軸進(jìn)行左單旋鳍征,得到最終結(jié)果黍翎,

image.png

插入

空樹時(shí)插入節(jié)點(diǎn)“E”直接作為根節(jié)點(diǎn),“E”節(jié)點(diǎn)高度設(shè)為1艳丛,


image.png

繼續(xù)插入“B”節(jié)點(diǎn)匣掸,小于“E”節(jié)點(diǎn)則添加到左邊,且“E”節(jié)點(diǎn)高度加1氮双,

image.png

繼續(xù)插入“G”節(jié)點(diǎn)碰酝,大于“E”節(jié)點(diǎn)則添加到右邊,此時(shí)“E”節(jié)點(diǎn)高度不變戴差,


image.png

繼續(xù)插入“D”節(jié)點(diǎn)送爸,最終到“B”節(jié)點(diǎn)的右子節(jié)點(diǎn),此時(shí)“B”節(jié)點(diǎn)高度加1,“E”節(jié)點(diǎn)高度也加1袭厂,


image.png

繼續(xù)插入“C”節(jié)點(diǎn)墨吓,最終到“D”節(jié)點(diǎn)的左子節(jié)點(diǎn),此時(shí)“D”纹磺、“B”肛真、“E”節(jié)點(diǎn)高度都分別加1,并且先發(fā)現(xiàn)節(jié)點(diǎn)“D”與它同級節(jié)點(diǎn)(不存在即高度為0)高度差大于1爽航,并且屬于RL插入方式,使用右左雙旋處理乾忱,

image.png

以“C”節(jié)點(diǎn)為軸進(jìn)行右單旋讥珍,結(jié)果為,

image.png

再以“C”節(jié)點(diǎn)為軸進(jìn)行左單旋窄瘟,結(jié)果如下衷佃,可以看到進(jìn)過右左雙旋操作后二叉樹已經(jīng)達(dá)到平衡了。

image.png

總結(jié)蹄葱,插入時(shí)可能會(huì)遇到四種不同的插入方式氏义,分別是:LL插入方式、RR插入方式图云、LR和RL插入方式惯悠。根據(jù)不同的插入方式對應(yīng)做旋轉(zhuǎn)操作即能使樹達(dá)到平衡狀態(tài)。

查找

AVL樹因?yàn)閷儆诙嫠阉鳂淇⒖觯圆檎視r(shí)與BST樹完全一樣克婶,比如下面這棵樹,查找“D”節(jié)點(diǎn)丹泉,

image.png

從根節(jié)點(diǎn)“C”開始情萤,

image.png

“D”大于“C”,所以往右繼續(xù)查找摹恨,

image.png

“D”小于“E”筋岛,所以往左查找,找到晒哄。


image.png

刪除

刪除操作主要分兩種情況睁宰,一種是刪除后不會(huì)影響平衡,那么直接按照BST樹規(guī)則刪除揩晴。另外一種是刪除后會(huì)影響樹的平衡勋陪,那么則需要再做旋轉(zhuǎn)處理。

情況一

如樹的結(jié)構(gòu)硫兰,要?jiǎng)h除“B”節(jié)點(diǎn)诅愚,

image.png

直接找到“B”節(jié)點(diǎn),且因?yàn)槭侨~子節(jié)點(diǎn),直接刪掉即可违孝。


image.png

最終為刹前,

image.png

但如果刪除的不是“B”節(jié)點(diǎn),而是“C”節(jié)點(diǎn)雌桑,則不能直接刪除“C”節(jié)點(diǎn)喇喉,

image.png

應(yīng)該先找到“C”節(jié)點(diǎn)的前驅(qū),它的前驅(qū)為“B”節(jié)點(diǎn)校坑,使用“B”替換“C”節(jié)點(diǎn)拣技,


image.png

最后將原來的“B”節(jié)點(diǎn)刪除。

image.png

情況二

如樹的結(jié)構(gòu)耍目,要?jiǎng)h除“F”節(jié)點(diǎn)膏斤,

image.png

先找到“F”節(jié)點(diǎn),

image.png

然后將“F”節(jié)點(diǎn)刪除邪驮,此時(shí)導(dǎo)致了“C”節(jié)點(diǎn)和“G”節(jié)點(diǎn)的高度差超過1莫辨,需要做旋轉(zhuǎn)操作,


image.png

而且因?yàn)镃節(jié)點(diǎn)的左子節(jié)點(diǎn)高度比右子節(jié)點(diǎn)高度大毅访,所以執(zhí)行右單旋操作沮榜,旋轉(zhuǎn)后為,


image.png

轉(zhuǎn)自:https://blog.csdn.net/wangyangzhizhou/article/details/81529872

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末喻粹,一起剝皮案震驚了整個(gè)濱河市蟆融,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌守呜,老刑警劉巖振愿,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異弛饭,居然都是意外死亡冕末,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門侣颂,熙熙樓的掌柜王于貴愁眉苦臉地迎上來档桃,“玉大人,你說我怎么就攤上這事憔晒≡逡蓿” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵拒担,是天一觀的道長嘹屯。 經(jīng)常有香客問我,道長从撼,這世上最難降的妖魔是什么州弟? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮,結(jié)果婚禮上婆翔,老公的妹妹穿的比我還像新娘拯杠。我一直安慰自己,他們只是感情好啃奴,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布潭陪。 她就那樣靜靜地躺著,像睡著了一般最蕾。 火紅的嫁衣襯著肌膚如雪依溯。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天瘟则,我揣著相機(jī)與錄音誓沸,去河邊找鬼。 笑死壹粟,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的宿百。 我是一名探鬼主播趁仙,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼垦页!你這毒婦竟也來了雀费?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤痊焊,失蹤者是張志新(化名)和其女友劉穎盏袄,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體薄啥,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡辕羽,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了垄惧。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片刁愿。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖到逊,靈堂內(nèi)的尸體忽然破棺而出铣口,到底是詐尸還是另有隱情,我是刑警寧澤觉壶,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布脑题,位于F島的核電站,受9級特大地震影響铜靶,放射性物質(zhì)發(fā)生泄漏叔遂。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望掏熬。 院中可真熱鬧佑稠,春花似錦、人聲如沸旗芬。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽疮丛。三九已至幔嫂,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間誊薄,已是汗流浹背履恩。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留呢蔫,地道東北人切心。 一個(gè)月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像片吊,于是被迫代替她去往敵國和親绽昏。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容