一、定義
二叉排序樹（Binary Sort Tree）又稱二叉查找樹、二叉搜尋樹。 它或者是一棵空樹；或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3）左、右子樹也分别為二叉排序樹；
首先實作二叉排序樹的搜尋，因為後續無論對二叉排序樹進行增加、删除都要先進行查找。
def bst_search(btree,key):
bt=btree
while bt is not None:
if key==bt.value:
return True
elif key>bt.value:
bt=bt.right
else:
bt=bt.left
return False
如果二叉樹的結構良好，其高度與樹中結點個數n成對數關系，檢索的時間開銷為O(logn)，但是如果樹結構為畸形，檢索的最壞時間可能達到O(n),如下圖的樹：
但是如果是下面這樣的結構，則平均檢索時間就能達到O(logn)：
從上述兩棵樹而已看出，一組有序資料，是可以建構多種不同的二叉排序樹，但是哪種才是最優的二叉排序樹呢？從上可以看出第二顆樹明顯優于第一個，第二個樹正是平衡二叉排序樹，是以平衡二叉排序樹才是最優的。
二、平衡二叉排序樹(AVL樹)
平衡二叉排序樹，又叫AVL樹，是由它們的發明者蘇聯人的名字命名的，定義如下：
平衡二叉排序樹是一類特殊的二叉排序樹，它或者為空樹，或者其左右子樹都是平衡二叉排序樹，而且其左右的子數高度之差絕對值不超過1.
AVL樹的查找平均複雜度是O（log(n)）。
在每一次樹插入新元素後，樹的平衡都可能被破壞，需要旋轉調整樹的高度，以達到平衡樹結構，共分為以下四種情況：
- LL：對該結點的左兒子的左子樹進行了一次插入，需右旋轉
- LR：對該結點的左兒子的右子樹進行了一次插入，先左後右
- RL：對該結點的右兒子的左子樹進行了一次插入，先右後左
- RR：對該結點的右兒子的右子樹進行了一次插入，需左旋轉
旋轉原則：在旋轉的時候，都是要以離新插入節點最近的不平衡子樹進行旋轉，注意旋轉的這部分子樹一定是不平衡的子樹。
1）LL情況
2）RR情況
3）LR情況
4）RL情況
python代碼實作參考：https://www.cnblogs.com/linxiyue/p/3659448.html?utm_source=tuicool&utm_medium=referral