平衡二叉樹

定義

縮寫記一下 AVL

還有下面這些，can you try？

平衡二叉樹的插入

LL平衡旋轉（右單旋轉）

怎么理解？

首先我們可以看見啊，b圖A左邊和右邊的不平衡的，非常的難受

于是我們可以這么做，因為A的左邊比右邊多，所以B和A交換位置，這樣就會出現一個問題，B的左邊繼續寫BL沒問題，A的右邊繼續寫AR沒問題，那BR放哪里呢，BR放在A的左邊我的朋友，因為A的左邊本來就是有東西的

然后BR仍然是大于B小于A的

RR平衡旋轉（左單旋轉）

一樣，就是哪邊多，你就往相反的方向旋，這里右邊多，就往左旋，

LR平衡旋轉（先左后右雙旋轉）

這里直接看b圖是怎么直接到c圖的?

這里LR的意思是先左 到B 再右道 BR，這里會多一個

哪邊多，你就往相反的方向旋，這里右邊多，左旋

然后這里除了CLANNAD照搬不了，其他的都照搬

然后B的右邊原來就是有東西的，所以再放一下CL

然后再把沒用到的A先畫出來

然后就左邊多，就往右旋，C上去，A到右邊下來

最后照搬變成書上的c圖，A的右邊照搬是AR，C的右邊照搬是B的全部,然后原本C的CR無法照搬，而A的左邊原本就應該有東西，所以CR放A左邊

RL平衡旋轉（先右后左雙旋轉）

這個也是不多說了，原理一樣

最小不平衡子樹

這里的意思是這里有2個節點不平衡了，也就是27和75，然后只要把最下面的調好，27這個也就自動調好了

逗你一笑小例子

然后112會插在

然后發現120和100不平衡了，然后你只要處理最下面的120就行了

然后開始做

繼續

好了，就這樣

最后，其他的不用變

然后就有人說了，主播有沒有更簡單的方法，有的兄弟有的

先往你插入的地方從上往下數3個

然后把大小是中間的數寫在中間，這里就是115，然后左邊是110，右邊的120

然后剩下的按大小來寫

然后再也不用旋了，一步到位

做題

1

?

c

2

d?

3

題目意思是 每次加一個，不平衡的話就旋轉

?

d

4

這個是二叉排序樹，注意

c

平衡二叉樹的刪除

過程

這里刪的是32，刪了之后就不平衡了，然后之前我們是往插入的地方走，現在就是看哪邊地方大往哪邊走，然后開旋

做題

1

?

a

平衡二叉樹的查找

?

這個圖看T3，T3左邊是T1，右邊是T2，所以可以看見，如果下面本就是平衡的，那只用加一個節點就可以即加深度又是平衡的，這里T4就是T2+T3+1的節點和他的四層深度

所以這個公式就不用記了，可以直接推出來

注意這里是要求最大深度，比如7個節點既可以是4層也可以是3層

做題

1

1? 2? 4? 7? 12? 20?

b

2

11題 c秒，最大深度注意

12題 b秒，至少注意