樹（中）
二叉搜索（排序/查找）樹
作用：為了進行二分查找求冷，將數(shù)據構建在查找樹中癌淮，相比與線性結構樹的插入刪除等動態(tài)操作更為方便肚菠。
定義
- 可以為空
- 若不為空健蕊，左子樹的鍵值都小于根節(jié)點菱阵，右子樹的鍵值都大于根節(jié)點。
- 左右子樹都是二叉搜索樹缩功。
操作
- 增加
- 刪除
刪除過程略復雜晴及，如果是葉子節(jié)點可以直接刪除，如果有一個孩子嫡锌，則直接讓孩子替代原來的位置虑稼；如果有兩個孩子，則選擇左子樹的最大值势木，或者右子樹的最小值蛛倦，來替代原來的位置
這是就轉化成了一個孩子（沒有孩子 ）的情況。
平衡二叉樹
作用：對于同一個序列啦桌，如果根節(jié)點確定下來那么溯壶，整個搜索樹也就去確定了，所以對于選定不同的根節(jié)點甫男，構造出來的樹的形狀是不一樣的茸塞，其查找效率也不同。
一種高效率的查找樹是查剖，左子樹和右子樹深度相近钾虐。
衡量指標：平衡因子。左右子樹的高度差笋庄。要求：小于1效扫；
平衡二叉樹的高度能達到log2(n)？
h層高度的平衡二叉樹直砂，最少需要hn個節(jié)點菌仁。可以推出：hn = h(n-1) + h(n-2) + 1;可以看出静暂，類似于斐期那比數(shù)列济丘。得出：hn = f(h+2) -1;
可以推出：節(jié)點數(shù)為n的平衡二叉樹，高度最大能達到log2(n)
平衡二叉樹的調整
為什么需要調整洽蛀？
當動態(tài)的刪除/增加一個序列摹迷，適合最根節(jié)點的鍵值，必然會改變郊供，所以會造成二叉樹由平衡變?yōu)椴黄胶狻?/p>
幾個概念：
被破壞者：由于插入/刪除一個節(jié)點峡碉，造成某個節(jié)點不在平衡（可能有多個節(jié)點被破壞，只考慮最底層的節(jié)點）驮审。
破壞者：插入/刪除的節(jié)點鲫寄。
- R旋：破壞者在被破者的右子樹的右子樹上吉执。
- L旋：破壞者在被破壞者的左子樹的左子樹上。
- LR旋：破壞者在被破壞者的左子樹的右子樹上地来。
- RL旋：破壞者在被破壞者的右子樹的左子樹上戳玫。
