【我是一棵樹】二叉排序樹、平衡二叉樹（AVL）

二叉排序樹

又稱為二叉查找樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：

• 若他的左子樹不空，則左子樹上所有節點的值均小于它根節點的值
• 若他的右子樹不空，則右子樹上所有節點的值均大于根節點的值
• 它的左、右子樹也分别為二叉排序樹

二叉排序樹特點

是以連結的方式存儲，保持了連結存儲結構在執行插入或删除操作室，不用一棟元素的優點，隻要找到合适的插入和删除位置後，僅需修改連結指針即可。插入、删除時間性能比較好。而對于二叉排序樹的查找，走的就是從根節點到需要查找的節點的路徑，其比較次數等于給定值的節點在二叉樹的層數。極端情況下，最少為1次，即根節點就是要找的點。最多也不會超過樹的深度。可問題就在于，二叉排序樹的形狀是不确定的= = #

平衡二叉樹

是一種排序二叉樹，其中每個節點的左子樹和右子樹高度差之多等于1，也稱AVL樹。

從名字上也能看出來，這是一種高度平衡的二叉排序樹。什麼叫高度平衡，就是要麼是一棵空樹，要麼它的左、右子樹都是平衡二叉樹。且左、右子樹深度差絕對值不超過1.我們将二叉樹上節點左子樹深度減去右子樹深度的值稱為平衡因子BF（Balance Factory）。

距離插入節點最近的，且平衡因子絕對值大于1的節點為根的數，我們稱為最小不平衡子樹。