樹的高度和深度
From CSDN 暴走抹茶MOUKOY
1.高度
對于高度的理解，我們不管他數(shù)據(jù)結(jié)構(gòu)什么什么知識冈绊，就拿樓房來說吆倦，假如一個人提問：樓房的高度有好高佳晶？我們會下意識的從底層開始往上數(shù)，假如樓有6層截型，則我們會說趴荸，這個樓有6層樓那么高，則提問者就會大概知道樓有多高了宦焦。所以高度就是從下往上對比发钝，這是我們的習(xí)慣。而在樹中波闹，樹的高度也是從下往上數(shù)酝豪，如圖所示
K節(jié)點(diǎn)在樹的底層，是一個葉子節(jié)點(diǎn)精堕，則一般定義為K的高度在最低為1孵淘，以此類推，O的高度也是為1锄码，P的節(jié)點(diǎn)也是為1夺英。M節(jié)點(diǎn)是葉子節(jié)點(diǎn)O的父節(jié)點(diǎn)晌涕，從下往上數(shù)滋捶，M節(jié)點(diǎn)高度為2。那么G節(jié)點(diǎn)的高度是多少呢余黎？從G-L的高度為2重窟，從G-M-O節(jié)點(diǎn)高度為3，到底G節(jié)點(diǎn)高度為多少呢惧财，正確答案是3巡扇，請看定義：
高度的定義為：從結(jié)點(diǎn)x向下到某個葉結(jié)點(diǎn)最長簡單路徑中邊的條數(shù)
注意：對于是否是邊的條數(shù)這個不清楚，待我后來查證垮衷，這個主要是由于其初值是1還是0來確定的厅翔，一般都是以1開始
2.深度
理解了高度，則深度的理解就很容易了搀突，深度是從根節(jié)點(diǎn)往下刀闷，列如上圖中：B的深度為2。
3.總結(jié)
對于整棵樹來說仰迁，最深的葉結(jié)點(diǎn)的深度就是樹的深度甸昏；樹根的高度就是樹的高度。這樣樹的高度和深度是相等的徐许。
對于樹中相同深度的每個結(jié)點(diǎn)來說施蜜，它們的高度不一定相同，這取決于每個結(jié)點(diǎn)下面的葉結(jié)點(diǎn)的深度雌隅。
AVL Tree
From CSDN PlusPlus1 / 董的博客
一翻默、概述
AVL樹是最先發(fā)明的自平衡二叉查找樹缸沃。AVL樹以其發(fā)明者前蘇聯(lián)學(xué)者 G.M. Adelson-Velsky 和 E.M. Landis 名字而命名，他們在1962年的論文《An algorithm for the organization of information》中發(fā)表了它修械。
AVL樹中和泌，一個非常重要的概念為平衡因子（Balance factor），對于任意節(jié)點(diǎn) x 祠肥，其平衡因子定義為該節(jié)點(diǎn)右子樹和左子樹高度差武氓，即 bf（x）=h（x-right）-h（x-left）。
帶有平衡因子1仇箱、0或 -1的節(jié)點(diǎn)被認(rèn)為是平衡的县恕。帶有平衡因子 -2或2的節(jié)點(diǎn)被認(rèn)為是不平衡的，并需要重新平衡這個樹剂桥。平衡因子可以直接存儲在每個節(jié)點(diǎn)中忠烛，或從可能存儲在節(jié)點(diǎn)中的子樹高度計(jì)算出來。
二权逗、基本術(shù)語
有四種種情況可能導(dǎo)致二叉查找樹不平衡美尸，分別為：
（1）LL：插入一個新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹（Left）的左子樹（Left），導(dǎo)致根節(jié)點(diǎn)的平衡因子由1變?yōu)?
（2）RR：插入一個新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹（Right）的右子樹（Right）斟薇，導(dǎo)致根節(jié)點(diǎn)的平衡因子由-1變?yōu)?2
（3）LR：插入一個新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹（Left）的右子樹（Right）师坎，導(dǎo)致根節(jié)點(diǎn)的平衡因子由1變?yōu)?
（4）RL：插入一個新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹（Right）的左子樹（Left），導(dǎo)致根節(jié)點(diǎn)的平衡因子由-1變?yōu)?2
針對四種種情況可能導(dǎo)致的不平衡堪滨，可以通過旋轉(zhuǎn)使之變平衡胯陋。有兩種基本的旋轉(zhuǎn)：
（1）左旋轉(zhuǎn)：將根節(jié)點(diǎn)旋轉(zhuǎn)到（根節(jié)點(diǎn)的）右孩子的左孩子位置
（2）右旋轉(zhuǎn)：將根節(jié)點(diǎn)旋轉(zhuǎn)到（根節(jié)點(diǎn)的）左孩子的右孩子位置
三、AVL樹的旋轉(zhuǎn)操作
AVL樹的基本操作是旋轉(zhuǎn)袱箱，有四種旋轉(zhuǎn)方式遏乔，分別為：左旋轉(zhuǎn)，右旋轉(zhuǎn)发笔，左右旋轉(zhuǎn)（先左后右）盟萨，右左旋轉(zhuǎn)（先右后左），實(shí)際上了讨，這四種旋轉(zhuǎn)操作兩兩對稱捻激，因而也可以說成兩類旋轉(zhuǎn)操作。
3.1 LL
下圖所示為LL構(gòu)型量蕊，在B節(jié)點(diǎn)的左子樹上插入節(jié)點(diǎn)導(dǎo)致A節(jié)點(diǎn)失衡铺罢，調(diào)整過程為：以B節(jié)點(diǎn)為軸心，A節(jié)點(diǎn)順時(shí)針旋轉(zhuǎn)至B的右子樹残炮，A的右子樹用B的右子樹代替韭赘。通過右旋操作，返回以B為Root的平衡子樹势就。
3.2 RR
RR情況需要左旋解決泉瞻，如下圖所示：
3.3 LR
下圖所示為LR構(gòu)型脉漏，在B節(jié)點(diǎn)的右子樹上插入新節(jié)點(diǎn)導(dǎo)致A節(jié)點(diǎn)失衡，調(diào)整過程分兩個步驟：首先以C為軸心袖牙，B繞C逆時(shí)針旋轉(zhuǎn)侧巨，生成的子樹作為A的左子樹；這樣就變化成了LL型鞭达，然后用上圖所示的方法調(diào)整即可司忱。通過先左旋后右旋，返回以C為Root的平衡子樹畴蹭。
3.4 RL
RL情況需要右左旋解決（先B右旋轉(zhuǎn)坦仍，后A左旋轉(zhuǎn)），如下圖所示：
四叨襟、AVL數(shù)的插入和刪除操作
(1) 插入操作：實(shí)際上就是在不同情況下采用不同的旋轉(zhuǎn)方式調(diào)整整棵樹,向AVL樹中插入節(jié)點(diǎn)后繁扎，要判斷是否引起失衡，如果失衡則需要進(jìn)一步確定構(gòu)型糊闽，選擇合適的基本旋轉(zhuǎn)操作來調(diào)整梳玫。
(2) 刪除操作：首先定位要刪除的節(jié)點(diǎn)，然后用該節(jié)點(diǎn)的右孩子的最左孩子替換該節(jié)點(diǎn)右犹，并重新調(diào)整以該節(jié)點(diǎn)為根的子樹為AVL樹提澎，具體調(diào)整方法跟插入數(shù)據(jù)類似。刪除操作對應(yīng)為插入操作的逆向操作傀履，調(diào)整平衡的時(shí)候也需要確定被刪除節(jié)點(diǎn)的分支構(gòu)型來選擇合適的旋轉(zhuǎn)方法虱朵。
