一、二叉查找樹

1眼姐、定義：二叉查找樹诅迷，也稱二叉搜索樹，或二叉排序樹众旗。其定義也比較簡單罢杉，要么是一顆空樹，要么就是具有如下性質(zhì)的二叉樹贡歧。

2滩租、性質(zhì)：

（1） 若任意節(jié)點(diǎn)的左子樹不空拱镐，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

（2） 若任意節(jié)點(diǎn)的右子樹不空持际，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

（3） 任意節(jié)點(diǎn)的左哗咆、右子樹也分別為二叉查找樹蜘欲；

（4） 沒有鍵值相等的節(jié)點(diǎn)。

（5） 對(duì)二叉查找樹進(jìn)行中序遍歷晌柬，即可得到有序的數(shù)列姥份。

圖a

????????如上圖所示，是不同形態(tài)的二叉查找樹年碘。二叉查找樹是對(duì)要查找的數(shù)據(jù)進(jìn)行生成樹澈歉，左支的值小于右支的值。在查找的時(shí)候也是一樣的思路屿衅，從根節(jié)點(diǎn)開始埃难，比節(jié)點(diǎn)大進(jìn)入右支，比節(jié)點(diǎn)小進(jìn)入左支涤久，直到查找到目標(biāo)值涡尘。? ?

3、操作：查詢响迂、插入考抄、刪除

查詢：類似二分查找

插入：二叉查找樹的插入算法比較簡單：空樹，就首先生成根節(jié)點(diǎn)蔗彤；不是空樹就按照查找的算法川梅，找到父節(jié)點(diǎn)，然后作為葉子節(jié)點(diǎn)插入然遏，如果值已經(jīng)存在就插入失敗贫途。

刪除：刪除操作稍微復(fù)雜一點(diǎn)，有如下幾種情況：

? （1）如果刪除的是葉節(jié)點(diǎn)啦鸣，可以直接刪除潮饱；

? （2）如果被刪除的元素有一個(gè)子節(jié)點(diǎn)，可以將子節(jié)點(diǎn)直接移到被刪除元素的位置诫给；

? （3）如果有兩個(gè)子節(jié)點(diǎn)香拉，這時(shí)候就采用中序遍歷，找到待刪除的節(jié)點(diǎn)的后繼節(jié)點(diǎn)中狂，將其與待刪除的節(jié)點(diǎn)互換凫碌，此時(shí)待刪除節(jié)點(diǎn)的位置已經(jīng)是葉子節(jié)點(diǎn)，可以直接刪除

如下圖：

圖b

將待刪除節(jié)點(diǎn)與后繼節(jié)點(diǎn)互換胃榕，變成如下圖所示：

圖c

將待刪除元素刪除盛险，如下圖所示：

圖d

【注】 1瞄摊、二叉查找樹還有一個(gè)性質(zhì)，即對(duì)二叉查找樹進(jìn)行中序遍歷苦掘，即可得到有序的數(shù)列换帜。

????????????2、二叉查找樹的查詢復(fù)雜度鹤啡，和二分查找一樣惯驼，插入和查找的時(shí)間復(fù)雜度均為 O(logn) ，但是在最壞的情況下仍然會(huì)有 O(n) 的時(shí)間復(fù)雜度递瑰。原因在于插入和刪除元素的時(shí)候祟牲，樹沒有保持平衡。

一抖部、二叉平衡樹

1说贝、定義：平衡二叉樹，又稱為AVL樹慎颗。平衡二叉樹有很多種最著名的是由前蘇聯(lián)數(shù)學(xué)家Adelse—Velskil和Landis在1962年提出的乡恕，稱為AVL樹。

2俯萎、性質(zhì)：

它是一棵空樹或且具有以下性質(zhì)：

（1）左右子樹深度之差的絕對(duì)值不超過1;

（2）左右子樹仍然為平衡二叉樹几颜。

平衡因子BF=左子樹深度－右子樹深度，平衡二叉樹每個(gè)結(jié)點(diǎn)的平衡因子只能是1讯屈，0蛋哭，-1。

【說明】由于普通的二叉查找樹會(huì)容易失去”平衡“涮母，極端情況下谆趾，二叉查找樹會(huì)退化成線性的鏈表，導(dǎo)致插入和查找的復(fù)雜度下降到 O(n) 叛本，所以沪蓬，這也是平衡二叉樹設(shè)計(jì)的初衷。那么平衡二叉樹如何保持”平衡“呢来候？根據(jù)定義跷叉，有兩個(gè)重點(diǎn)，一是左右兩子樹的高度差的絕對(duì)值不能超過1营搅，二是左右兩子樹也是一顆平衡二叉樹云挟。

　　舉例：如下圖所示，左圖是一棵平衡二叉樹转质，根節(jié)點(diǎn)10园欣，左右兩子樹的高度差是1，而右圖休蟹，雖然根節(jié)點(diǎn)左右兩子樹高度差是0沸枯，但是右子樹15的左右子樹高度差為2日矫，不符合定義，所以右圖不是一棵平衡二叉樹绑榴。

圖e

?　　由此可以看出平衡二叉樹是一棵高度平衡的二叉查找樹哪轿。所以，要構(gòu)建跟維系一棵平衡二叉樹就比普通的二叉樹要復(fù)雜的多翔怎。在構(gòu)建一棵平衡二叉樹的過程中缔逛，當(dāng)有新的節(jié)點(diǎn)要插入時(shí)，檢查是否因插入后而破壞了樹的平衡姓惑，如果是，則需要做旋轉(zhuǎn)去改變樹的結(jié)構(gòu)按脚。

3于毙、預(yù)備知識(shí)：

左旋：

?右旋：

不同于順時(shí)針跟逆時(shí)針變換這種方式去記憶，上面兩個(gè)動(dòng)態(tài)圖特別方便記憶跟理解：

（1）左旋就是將節(jié)點(diǎn)的右支往左拉辅搬，右子節(jié)點(diǎn)變成父節(jié)點(diǎn)唯沮，并把晉升之后多余的左子節(jié)點(diǎn)出讓給降級(jí)節(jié)點(diǎn)的右子節(jié)點(diǎn)；

（2）而右旋就是反過來堪遂，將節(jié)點(diǎn)的左支往右拉介蛉，左子節(jié)點(diǎn)變成了父節(jié)點(diǎn)，并把晉升之后多余的右子節(jié)點(diǎn)出讓給降級(jí)節(jié)點(diǎn)的左子節(jié)點(diǎn)溶褪。

（3）即左旋就是往左變換币旧，右旋就是往右變換。不管是左旋還是右旋猿妈，旋轉(zhuǎn)的目的都是將節(jié)點(diǎn)多的一支出讓節(jié)點(diǎn)給另一個(gè)節(jié)點(diǎn)少的一支吹菱。

?　　舉個(gè)例子，像上圖是否平衡二叉樹的圖里面彭则，左圖在沒插入前”19“節(jié)點(diǎn)前鳍刷，該樹還是平衡二叉樹，但是在插入”19“后俯抖，導(dǎo)致了”15“的左右子樹失去了”平衡“输瓜，所以此時(shí)可以將”15“節(jié)點(diǎn)進(jìn)行左旋，讓”15“自身把節(jié)點(diǎn)出讓給”17“作為”17“的左樹芬萍，使得”17“節(jié)點(diǎn)左右子樹平衡尤揣，而”15“節(jié)點(diǎn)沒有子樹，左右也平衡了柬祠。如下圖：

圖f

4芹缔、操作：查詢、插入瓶盛、刪除

查詢：類似二分查找

插入：由于在構(gòu)建平衡二叉樹的時(shí)候最欠，當(dāng)有新節(jié)點(diǎn)插入時(shí)示罗，都會(huì)判斷插入后是否平衡，這說明了插入新節(jié)點(diǎn)前芝硬，都是平衡的蚜点，也即高度差絕對(duì)值不會(huì)超過1。當(dāng)新節(jié)點(diǎn)插入后拌阴，有可能會(huì)有導(dǎo)致樹不平衡绍绘，這時(shí)候就需要進(jìn)行調(diào)整，而可能出現(xiàn)的情況就有4種迟赃，分別稱作左左陪拘，左右，右左纤壁，右右左刽。

（1）左左即為在原來平衡的二叉樹上，在節(jié)點(diǎn)的左子樹的左子樹下酌媒，有新節(jié)點(diǎn)插入欠痴；

（2）左右即為在原來平衡的二叉樹上，在節(jié)點(diǎn)的左子樹的右子樹下秒咨，有新節(jié)點(diǎn)插入喇辽；

（3）右左即為在原來平衡的二叉樹上，在節(jié)點(diǎn)的右子樹的左子樹下雨席，有新節(jié)點(diǎn)插入菩咨；

（4）右右即為在原來平衡的二叉樹上，在節(jié)點(diǎn)的右子樹的右子樹下陡厘，有新節(jié)點(diǎn)插入旦委。

插入后如何調(diào)整樹的平衡：

左左調(diào)整其實(shí)比較簡單，只需要對(duì)節(jié)點(diǎn)進(jìn)行右旋雏亚；

右右跟左左一樣缨硝，只需要旋轉(zhuǎn)一次就能把樹調(diào)整平衡，左旋罢低；

而左右跟右左也一樣查辩，都要進(jìn)行旋轉(zhuǎn)兩次才能把樹調(diào)整平衡。

左左：

圖g

左左：即為在原來平衡的二叉樹上网持，在節(jié)點(diǎn)的左子樹的左子樹下宜岛，有新節(jié)點(diǎn)插入，導(dǎo)致節(jié)點(diǎn)的左右子樹的高度差為2功舀，如上即為”10“節(jié)點(diǎn)的左子樹”7“萍倡，的左子樹”4“，插入了節(jié)點(diǎn)”5“或”3“導(dǎo)致失衡辟汰。

左左調(diào)整：其實(shí)比較簡單列敲，只需要對(duì)節(jié)點(diǎn)進(jìn)行右旋即可阱佛，如下圖，對(duì)節(jié)點(diǎn)”10“進(jìn)行右旋：

圖h

左右：

圖i

左右：即為在原來平衡的二叉樹上戴而，在節(jié)點(diǎn)的左子樹的右子樹下凑术，有新節(jié)點(diǎn)插入，導(dǎo)致節(jié)點(diǎn)的左右子樹的高度差為2所意，如上即為”11“節(jié)點(diǎn)的左子樹”7“淮逊，的右子樹”9“，插入了節(jié)點(diǎn)”10“或”8“導(dǎo)致失衡扶踊。

左右調(diào)整：就不能像左左一樣泄鹏，進(jìn)行一次旋轉(zhuǎn)就完成調(diào)整。我們不妨先試著讓左右像左左一樣對(duì)”11“節(jié)點(diǎn)進(jìn)行右旋秧耗，結(jié)果圖如下备籽，右圖的二叉樹依然不平衡，而右圖就是接下來要講的右左绣版，即左右跟右左互為鏡像，左左跟右右也互為鏡像歼疮。

圖j

右右跟左左一樣杂抽，只需要旋轉(zhuǎn)一次就能把樹調(diào)整平衡，而左右跟右左也一樣韩脏，都要進(jìn)行旋轉(zhuǎn)兩次才能把樹調(diào)整平衡缩麸，所以，首先上圖的這種調(diào)整是錯(cuò)誤的赡矢，正確的調(diào)整方式是杭朱，將左右進(jìn)行第一次旋轉(zhuǎn)，將左右先調(diào)整成左左吹散，然后再對(duì)左左進(jìn)行調(diào)整弧械，從而使得二叉樹平衡。

即先對(duì)上圖的節(jié)點(diǎn)”7“進(jìn)行左旋空民，使得二叉樹變成了左左刃唐，之后再對(duì)”11“節(jié)點(diǎn)進(jìn)行右旋，此時(shí)二叉樹就調(diào)整完成界轩，如下圖：

圖k

右左：

圖l

右左：即為在原來平衡的二叉樹上画饥，在節(jié)點(diǎn)的右子樹的左子樹下，有新節(jié)點(diǎn)插入浊猾，導(dǎo)致節(jié)點(diǎn)的左右子樹的高度差為2抖甘，如上即為”11“節(jié)點(diǎn)的右子樹”15“，的左子樹”13“葫慎，插入了節(jié)點(diǎn)”12“或”14“導(dǎo)致失衡衔彻。

右左調(diào)整：右左跟左右其實(shí)互為鏡像薇宠，所以調(diào)整過程就反過來，先對(duì)節(jié)點(diǎn)”15“進(jìn)行右旋米奸，使得二叉樹變成右右昼接，之后再對(duì)”11“節(jié)點(diǎn)進(jìn)行左旋，此時(shí)二叉樹就調(diào)整完成悴晰，如下圖:

圖m

右右：

圖n

右右：即為在原來平衡的二叉樹上慢睡，在節(jié)點(diǎn)的右子樹的右子樹下，有新節(jié)點(diǎn)插入铡溪，導(dǎo)致節(jié)點(diǎn)的左右子樹的高度差為2漂辐，如上即為”11“節(jié)點(diǎn)的右子樹”13“，的左子樹”15“棕硫，插入了節(jié)點(diǎn)”14“或”19“導(dǎo)致失衡髓涯。

右右調(diào)整：右右只需對(duì)節(jié)點(diǎn)進(jìn)行一次左旋即可調(diào)整平衡，如下圖哈扮，對(duì)”11“節(jié)點(diǎn)進(jìn)行左旋纬纪。

圖o

刪除：刪除二叉樹節(jié)點(diǎn)總結(jié)起來就兩個(gè)判斷：

①.刪除的是什么類型的節(jié)點(diǎn)？

②.刪除了節(jié)點(diǎn)之后是否導(dǎo)致失衡滑肉？

節(jié)點(diǎn)的類型有三種：

①.葉子節(jié)點(diǎn)包各；

②.只有左子樹或只有右子樹；

③.既有左子樹又有右子樹靶庙。

刪除后調(diào)整：

針對(duì)這三種節(jié)點(diǎn)類型问畅，再引入判斷2），所以處理思路分別是：

（1）當(dāng)刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)六荒，則將節(jié)點(diǎn)刪除护姆，然后從父節(jié)點(diǎn)開始，判斷是否失衡掏击，如果沒有失衡卵皂，則再判斷父節(jié)點(diǎn)的父節(jié)點(diǎn)是否失衡，直到根節(jié)點(diǎn)砚亭，此時(shí)到根節(jié)點(diǎn)還發(fā)現(xiàn)沒有失衡渐裂，則說此時(shí)樹是平衡的；如果中間過程發(fā)現(xiàn)失衡钠惩，則判斷屬于哪種類型? ? ? 的失衡（左左柒凉，左右，右左篓跛，右右）膝捞，然后進(jìn)行調(diào)整。

（2）刪除的節(jié)點(diǎn)只有左子樹或只有右子樹，這種情況其實(shí)就比刪除葉子節(jié)點(diǎn)的步驟多一步蔬咬，就是將節(jié)點(diǎn)刪除鲤遥，然后把僅有一支的左子樹或右子樹替代原有結(jié)點(diǎn)的位置，后面的步驟就一樣了林艘，從父節(jié)點(diǎn)開始盖奈，判斷是否失衡，如果沒有失衡狐援，則再判斷父節(jié)? ? ? 點(diǎn)的父節(jié)點(diǎn)是否失衡钢坦，直到根節(jié)點(diǎn)，如果中間過程發(fā)現(xiàn)失衡啥酱，則根據(jù)失衡的類型進(jìn)行調(diào)整爹凹。

（3）刪除的節(jié)點(diǎn)既有左子樹又有右子樹，這種情況又比上面這種多一步镶殷，就是中序遍歷禾酱，找到待刪除節(jié)點(diǎn)的前驅(qū)或者后驅(qū)都行，然后與待刪除節(jié)點(diǎn)互換位置绘趋，然后把待刪除的節(jié)點(diǎn)刪掉颤陶，后面的步驟也是一樣，判斷是否失衡陷遮，然后根據(jù)失衡類型進(jìn)行調(diào)整滓走。

【小結(jié)】 最后總結(jié)一下，平衡二叉樹是一棵高度平衡的二叉樹拷呆，所以查詢的時(shí)間復(fù)雜度是 O(logN) 闲坎。插入的話上面也說疫粥，失衡的情況有4種茬斧，左左，左右梗逮，右左项秉，右右，即一旦插入新節(jié)點(diǎn)導(dǎo)致失衡需要調(diào)整慷彤，最多也只要旋轉(zhuǎn)2次娄蔼，所以，插入復(fù)雜度是 O(1) 底哗，但是平衡二叉樹也不是完美的岁诉，也有缺點(diǎn)，從上面刪除處理思路中也可以看到跋选，就是刪除節(jié)點(diǎn)時(shí)有可能因?yàn)槭Ш馓檠ⅲ瑢?dǎo)致需要從刪除節(jié)點(diǎn)的父節(jié)點(diǎn)開始，不斷的回溯到根節(jié)點(diǎn)前标，如果這棵平衡二叉樹很高的話坠韩，那中間就要判斷很多個(gè)節(jié)點(diǎn)距潘。所以后來也出現(xiàn)了綜合性能比其更好的樹—-紅黑樹。