查找樹
平衡二叉樹先是一顆查找樹噪伊，所以先從查找樹的性質(zhì)講起簿煌。
查找樹的遞歸定義是氮唯，每個(gè)節(jié)點(diǎn)的左孩子值不大于它、右孩子不小于它姨伟，由此構(gòu)成的二叉樹即為查找樹惩琉。據(jù)此性質(zhì)，在插入或查找時(shí)夺荒，從根節(jié)點(diǎn)向下逐一比較瞒渠，即可找到相應(yīng)的插入或查找的位置。
在極端情況下技扼，比如連續(xù)插入依次遞增或遞減的節(jié)點(diǎn)伍玖，查找樹將退化成鏈表，復(fù)雜度從o(lgn)退化成o(n)剿吻，為避免這種情況窍箍，我們需要在查找樹的基礎(chǔ)上加上限制條件…
平衡二叉樹
平衡二叉樹有多種，只因各自的限制條件不盡相同丽旅，這里只講AVL樹椰棘。
對(duì)AVL樹而言，每個(gè)節(jié)點(diǎn)左右孩子的樹高差不超過1榄笙，否則需要旋轉(zhuǎn)樹達(dá)到平衡邪狞。
在假定除根節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)都達(dá)到平衡的情況下，該樹只有四種不平衡的狀態(tài):
i.左子樹比右子樹高（默認(rèn)都是高2個(gè)單位以上的办斑，下同）外恕，且左子樹的左樹高
ii.右子樹比左子樹高杆逗，且右子樹的右樹高
iii.左子樹比右子樹高乡翅，且左子樹的右樹高
iv.右子樹比左子樹高，且右子樹的左樹高
平衡操作
我們分情況討論运敢，并使樹重新達(dá)到平衡均抽。
i.右旋
對(duì)于情況1饼灿，我們僅僅需要一次右旋操作即可，大家可以把樹想得十分柔軟靶累，在重力的作用下自然下垂，然后我們把B節(jié)點(diǎn)用力提起癣疟，這棵樹就成了下圖的樣子…
ii.左旋
情況2與情況1是對(duì)稱的挣柬，進(jìn)行的操作也類似，只需一次左旋操作即可使樹重新達(dá)到平衡睛挚。
iii.左右雙旋
情況3比前面兩種略微復(fù)雜邪蛔，需要兩次旋轉(zhuǎn)操作才能使樹重新達(dá)到平衡。我們先將目光移到A節(jié)點(diǎn)的左樹扎狱，然后以該子樹為基礎(chǔ)做左旋操作侧到，如情況2所示勃教，于是我們得到下圖，
由于根節(jié)點(diǎn)左子樹本來就是平衡的匠抗，所以左旋之后依然平衡故源，不過此時(shí)左子樹的左樹已經(jīng)比右樹高了，于是我們將情況3轉(zhuǎn)化成了情況1汞贸，再對(duì)整顆樹做一次右旋操作即可绳军。
iv.右左雙旋
情況4與情況3對(duì)稱，也是先通過右旋將情況4轉(zhuǎn)換成情況2著蛙，再左旋重新達(dá)到平衡删铃，所以不再贅述。
插入
如果樹不存在節(jié)點(diǎn)踏堡，那么新節(jié)點(diǎn)為根節(jié)點(diǎn)猎唁，否則依照查找樹的性質(zhì)從根節(jié)點(diǎn)開始向下比較，直至到達(dá)末尾節(jié)點(diǎn)顷蟆，此時(shí)新節(jié)點(diǎn)作為樹的葉子節(jié)點(diǎn)诫隅，然后從新節(jié)點(diǎn)開始向上回溯，平衡每個(gè)回溯的節(jié)點(diǎn)帐偎，直到將整顆樹平衡逐纬。插入前的樹是平衡的，易證每個(gè)回溯節(jié)點(diǎn)的左右子樹都是平衡的削樊，參考上節(jié)平衡二叉樹的四種基本情況即可平衡回溯節(jié)點(diǎn)豁生，從而當(dāng)回溯到根節(jié)點(diǎn)時(shí)，我們即可平衡整顆二叉樹漫贞。
刪除
在刪除之前甸箱，我們需要依照查找樹的性質(zhì)定位到刪除節(jié)點(diǎn)，即查找操作迅脐，找到刪除節(jié)點(diǎn)后芍殖，如果為葉子節(jié)點(diǎn)，直接刪除谴蔑，否則從左子樹或者右子樹中選擇一個(gè)替換節(jié)點(diǎn)豌骏，替代刪除節(jié)點(diǎn)的位置，一般選擇樹高最大的那顆隐锭。如果是左子樹窃躲，那么尋找子樹值最大的節(jié)點(diǎn)，否則尋找右子樹最小的節(jié)點(diǎn)作為替換節(jié)點(diǎn)钦睡，這是為了避免破壞查找樹的性質(zhì)而做出的必然選擇蒂窒。值得一提的是，在取下替換節(jié)點(diǎn)時(shí)，如果替換節(jié)點(diǎn)存在子樹刘绣，這顆子樹的根節(jié)點(diǎn)應(yīng)當(dāng)替代替換節(jié)點(diǎn)的位置樱溉。
我們使用替換節(jié)點(diǎn)替換刪除節(jié)點(diǎn)的位置后，就應(yīng)該從替換節(jié)點(diǎn)（替換節(jié)點(diǎn)原來的父節(jié)點(diǎn)）的父節(jié)點(diǎn)開始平衡二叉樹了纬凤。與插入時(shí)平衡二叉樹類似福贞，由于刪除之前就是平衡的，所以向上回溯時(shí)節(jié)點(diǎn)的子樹都是平衡的停士，最后回溯至根節(jié)點(diǎn)挖帘，我們即可重新平衡整顆二叉樹。
參考資料
為了解平衡二叉樹恋技，我從網(wǎng)上參考了一些事例拇舀，感覺說的不是很清楚，幾乎都只是擺出了針對(duì)四種情況的旋轉(zhuǎn)操作蜻底，并沒有指出它們和插入刪除之間的聯(lián)系骄崩，讓人覺得很迷惑，最后在家翻看了之前的教材（清華大學(xué)出版的《數(shù)據(jù)結(jié)構(gòu)》）才明白了一點(diǎn)薄辅，那個(gè)將樹提起來的想法就是參考這本書的描述要拂，我覺得非常形象易懂…最后給出我實(shí)現(xiàn)此樹的源碼:
