樹(shù)的高度和深度
From CSDN 暴走抹茶MOUKOY
1.高度
對(duì)于高度的理解，我們不管他數(shù)據(jù)結(jié)構(gòu)什么什么知識(shí)，就拿樓房來(lái)說(shuō)，假如一個(gè)人提問(wèn)：樓房的高度有好高？我們會(huì)下意識(shí)的從底層開(kāi)始往上數(shù)，假如樓有6層，則我們會(huì)說(shuō)，這個(gè)樓有6層樓那么高，則提問(wèn)者就會(huì)大概知道樓有多高了。所以高度就是從下往上對(duì)比，這是我們的習(xí)慣。而在樹(shù)中，樹(shù)的高度也是從下往上數(shù)，如圖所示
K節(jié)點(diǎn)在樹(shù)的底層，是一個(gè)葉子節(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，請(qǐng)看定義：
高度的定義為：從結(jié)點(diǎn)x向下到某個(gè)葉結(jié)點(diǎn)最長(zhǎng)簡(jiǎn)單路徑中邊的條數(shù)
注意：對(duì)于是否是邊的條數(shù)這個(gè)不清楚，待我后來(lái)查證，這個(gè)主要是由于其初值是1還是0來(lái)確定的，一般都是以1開(kāi)始
2.深度
理解了高度，則深度的理解就很容易了，深度是從根節(jié)點(diǎn)往下，列如上圖中：B的深度為2。
3.總結(jié)
對(duì)于整棵樹(shù)來(lái)說(shuō)，最深的葉結(jié)點(diǎn)的深度就是樹(shù)的深度；樹(shù)根的高度就是樹(shù)的高度。這樣樹(shù)的高度和深度是相等的。
對(duì)于樹(shù)中相同深度的每個(gè)結(jié)點(diǎn)來(lái)說(shuō)，它們的高度不一定相同，這取決于每個(gè)結(jié)點(diǎn)下面的葉結(jié)點(diǎn)的深度。
AVL Tree
From CSDN PlusPlus1 / 董的博客
一、概述
AVL樹(shù)是最先發(fā)明的自平衡二叉查找樹(shù)。AVL樹(shù)以其發(fā)明者前蘇聯(lián)學(xué)者 G.M. Adelson-Velsky 和 E.M. Landis 名字而命名，他們?cè)?962年的論文《An algorithm for the organization of information》中發(fā)表了它。
AVL樹(shù)中，一個(gè)非常重要的概念為平衡因子（Balance factor），對(duì)于任意節(jié)點(diǎn) x ，其平衡因子定義為該節(jié)點(diǎn)右子樹(shù)和左子樹(shù)高度差，即 bf（x）=h（x-right）-h（x-left）。
帶有平衡因子1、0或 -1的節(jié)點(diǎn)被認(rèn)為是平衡的。帶有平衡因子 -2或2的節(jié)點(diǎn)被認(rèn)為是不平衡的，并需要重新平衡這個(gè)樹(shù)。平衡因子可以直接存儲(chǔ)在每個(gè)節(jié)點(diǎn)中，或從可能存儲(chǔ)在節(jié)點(diǎn)中的子樹(shù)高度計(jì)算出來(lái)。
二、基本術(shù)語(yǔ)
有四種種情況可能導(dǎo)致二叉查找樹(shù)不平衡，分別為：
（1）LL：插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹(shù)（Left）的左子樹(shù)（Left），導(dǎo)致根節(jié)點(diǎn)的平衡因子由1變?yōu)?
（2）RR：插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹(shù)（Right）的右子樹(shù)（Right），導(dǎo)致根節(jié)點(diǎn)的平衡因子由-1變?yōu)?2
（3）LR：插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹(shù)（Left）的右子樹(shù)（Right），導(dǎo)致根節(jié)點(diǎn)的平衡因子由1變?yōu)?
（4）RL：插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹(shù)（Right）的左子樹(shù)（Left），導(dǎo)致根節(jié)點(diǎn)的平衡因子由-1變?yōu)?2
針對(duì)四種種情況可能導(dǎo)致的不平衡，可以通過(guò)旋轉(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樹(shù)的旋轉(zhuǎn)操作
AVL樹(shù)的基本操作是旋轉(zhuǎn)，有四種旋轉(zhuǎn)方式，分別為：左旋轉(zhuǎn)，右旋轉(zhuǎn)，左右旋轉(zhuǎn)（先左后右），右左旋轉(zhuǎn)（先右后左），實(shí)際上，這四種旋轉(zhuǎn)操作兩兩對(duì)稱，因而也可以說(shuō)成兩類旋轉(zhuǎn)操作。
3.1 LL
下圖所示為L(zhǎng)L構(gòu)型，在B節(jié)點(diǎn)的左子樹(shù)上插入節(jié)點(diǎn)導(dǎo)致A節(jié)點(diǎn)失衡，調(diào)整過(guò)程為：以B節(jié)點(diǎn)為軸心，A節(jié)點(diǎn)順時(shí)針旋轉(zhuǎn)至B的右子樹(shù)，A的右子樹(shù)用B的右子樹(shù)代替。通過(guò)右旋操作，返回以B為Root的平衡子樹(shù)。
3.2 RR
RR情況需要左旋解決，如下圖所示：
3.3 LR
下圖所示為L(zhǎng)R構(gòu)型，在B節(jié)點(diǎn)的右子樹(shù)上插入新節(jié)點(diǎn)導(dǎo)致A節(jié)點(diǎn)失衡，調(diào)整過(guò)程分兩個(gè)步驟：首先以C為軸心，B繞C逆時(shí)針旋轉(zhuǎn)，生成的子樹(shù)作為A的左子樹(shù)；這樣就變化成了LL型，然后用上圖所示的方法調(diào)整即可。通過(guò)先左旋后右旋，返回以C為Root的平衡子樹(shù)。
3.4 RL
RL情況需要右左旋解決（先B右旋轉(zhuǎn)，后A左旋轉(zhuǎn)），如下圖所示：
四、AVL數(shù)的插入和刪除操作
(1) 插入操作：實(shí)際上就是在不同情況下采用不同的旋轉(zhuǎn)方式調(diào)整整棵樹(shù),向AVL樹(shù)中插入節(jié)點(diǎn)后，要判斷是否引起失衡，如果失衡則需要進(jìn)一步確定構(gòu)型，選擇合適的基本旋轉(zhuǎn)操作來(lái)調(diào)整。
(2) 刪除操作：首先定位要?jiǎng)h除的節(jié)點(diǎn)，然后用該節(jié)點(diǎn)的右孩子的最左孩子替換該節(jié)點(diǎn)，并重新調(diào)整以該節(jié)點(diǎn)為根的子樹(shù)為AVL樹(shù)，具體調(diào)整方法跟插入數(shù)據(jù)類似。刪除操作對(duì)應(yīng)為插入操作的逆向操作，調(diào)整平衡的時(shí)候也需要確定被刪除節(jié)點(diǎn)的分支構(gòu)型來(lái)選擇合適的旋轉(zhuǎn)方法。
