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]桦踊。
圖中紅色數(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é)果為杖狼,
但實(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)如下圖国拇,
將“A”節(jié)點(diǎn)添加到樹中,變成如下結(jié)構(gòu)惯殊,樹產(chǎn)生了不平衡酱吝,于是檢查哪里不平衡,當(dāng)?shù)健癈”節(jié)點(diǎn)時(shí)發(fā)現(xiàn)高度差超過1土思,
所以需要對“C”節(jié)點(diǎn)進(jìn)行右單旋操作將高度降到2务热,達(dá)到平衡。
插入方式
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插入。
-
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è)存在一棵樹餐济,如下耘擂,
現(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)行右單旋,
“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á)到了平衡定血。
左單旋
左單旋用于處理RR插入方式,假設(shè)存在一棵樹漏峰,如下糠悼,
現(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)行左單旋,
“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á)到了平衡馒索。
左右雙旋
左右雙旋用于處理LR插入方式莹妒,假設(shè)存在一棵樹,如下绰上,
現(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)行左右雙旋爽哎,
先以“D”節(jié)點(diǎn)為軸進(jìn)行左單旋,結(jié)果為器一,
再以“D”節(jié)點(diǎn)為軸進(jìn)行右單旋课锌,得到最終結(jié)果,
右左雙旋
右左雙旋用于處理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)行右左雙旋兼丰,
先以“F”節(jié)點(diǎn)為軸進(jìn)行右單旋玻孟,結(jié)果為,
再以“F”節(jié)點(diǎn)為軸進(jìn)行左單旋鳍征,得到最終結(jié)果黍翎,
插入
空樹時(shí)插入節(jié)點(diǎn)“E”直接作為根節(jié)點(diǎn),“E”節(jié)點(diǎn)高度設(shè)為1艳丛,
繼續(xù)插入“B”節(jié)點(diǎn)匣掸,小于“E”節(jié)點(diǎn)則添加到左邊,且“E”節(jié)點(diǎn)高度加1氮双,
繼續(xù)插入“G”節(jié)點(diǎn)碰酝,大于“E”節(jié)點(diǎn)則添加到右邊,此時(shí)“E”節(jié)點(diǎn)高度不變戴差,
繼續(xù)插入“D”節(jié)點(diǎn)送爸,最終到“B”節(jié)點(diǎn)的右子節(jié)點(diǎn),此時(shí)“B”節(jié)點(diǎn)高度加1,“E”節(jié)點(diǎn)高度也加1袭厂,
繼續(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插入方式,使用右左雙旋處理乾忱,
以“C”節(jié)點(diǎn)為軸進(jìn)行右單旋讥珍,結(jié)果為,
再以“C”節(jié)點(diǎn)為軸進(jìn)行左單旋窄瘟,結(jié)果如下衷佃,可以看到進(jìn)過右左雙旋操作后二叉樹已經(jīng)達(dá)到平衡了。
總結(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)丹泉,
從根節(jié)點(diǎn)“C”開始情萤,
“D”大于“C”,所以往右繼續(xù)查找摹恨,
“D”小于“E”筋岛,所以往左查找,找到晒哄。
刪除
刪除操作主要分兩種情況睁宰,一種是刪除后不會(huì)影響平衡,那么直接按照BST樹規(guī)則刪除揩晴。另外一種是刪除后會(huì)影響樹的平衡勋陪,那么則需要再做旋轉(zhuǎn)處理。
情況一
如樹的結(jié)構(gòu)硫兰,要?jiǎng)h除“B”節(jié)點(diǎn)诅愚,
直接找到“B”節(jié)點(diǎn),且因?yàn)槭侨~子節(jié)點(diǎn),直接刪掉即可违孝。
最終為刹前,
但如果刪除的不是“B”節(jié)點(diǎn),而是“C”節(jié)點(diǎn)雌桑,則不能直接刪除“C”節(jié)點(diǎn)喇喉,
應(yīng)該先找到“C”節(jié)點(diǎn)的前驅(qū),它的前驅(qū)為“B”節(jié)點(diǎn)校坑,使用“B”替換“C”節(jié)點(diǎn)拣技,
最后將原來的“B”節(jié)點(diǎn)刪除。
情況二
如樹的結(jié)構(gòu)耍目,要?jiǎng)h除“F”節(jié)點(diǎn)膏斤,
先找到“F”節(jié)點(diǎn),
然后將“F”節(jié)點(diǎn)刪除邪驮,此時(shí)導(dǎo)致了“C”節(jié)點(diǎn)和“G”節(jié)點(diǎn)的高度差超過1莫辨,需要做旋轉(zhuǎn)操作,
而且因?yàn)镃節(jié)點(diǎn)的左子節(jié)點(diǎn)高度比右子節(jié)點(diǎn)高度大毅访,所以執(zhí)行右單旋操作沮榜,旋轉(zhuǎn)后為,
轉(zhuǎn)自:https://blog.csdn.net/wangyangzhizhou/article/details/81529872