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
