二叉搜尋樹的定義：
二叉搜尋樹或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于或等于它的根節點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
（3）左、右子樹也分别為二叉搜尋樹；
如圖（一顆長殘了的BST）：
二叉搜尋樹的查詢：
若根結點的關鍵字值等于查找的關鍵字，傳回根節點的值。
否則，若小于根結點的關鍵字值，遞歸查左子樹。
若大于根結點的關鍵字值，遞歸查右子樹。
若子樹為空，則查找不成功。
假如我們要查詢60
從根節點50開始，50 < 60 往右子樹裡找，到65，65 > 60 往右子樹裡找，找到60
二叉搜尋樹的插入：
與查詢類似，判斷在左子樹還是右子樹，走到葉節點後直接新加一個節點
如圖我們要插入48
48 < 50，去左子樹，到40
48 > 40，去右子樹，到45
48 > 45，45沒有子節點了，48成為45的右兒子
二叉搜尋樹的最值：
最小值：一直往左子樹裡找
最大值：一直往右子樹裡找
二叉搜尋樹的前驅/後繼：
前驅是第一個比這個數小的值，後繼是第一個比這個大的值
性質：
節點x的前驅一定沒有右兒子，可能有左兒子（若前驅y有右兒子z，z大于y小于x，那z就是x前驅）
節點x的後繼一定沒有左兒子，可能有右兒子（若前驅y有左兒子z，z小于y大于x，那z就是x前驅）
前驅：如果這個節點x有左子樹，就以左兒子為根，查詢左子樹的最大值
如果沒有左子樹（1）：如果x為右兒子，前驅就是x的父親
（2）：如果x為左兒子，前驅就是右父親的左父親（若沒有左父親，就一直往上找）
如圖：
50的前驅是45。（前驅是左子樹最大值）
45的前驅是40。（沒有左子樹且為右兒子，前驅是其父親）
60的前驅是50。（沒有左子樹且為左兒子，前驅是其右父親的左父親）
30沒有前驅。 【沒有左子樹且為左兒子，但在30的左父親（祖先）裡沒有有左父親的節點】
後繼：如果這個節點有右子樹，就以右兒子為根，查詢右子樹的最大值
如果沒有右子樹（1）：如果x為左兒子，後繼就是x的父親
（2）：如果x為右兒子，前驅就是左父親的右父親（若沒有右父親，就一直往上找）
同理如圖：
50的後繼是60。（前驅是右子樹裡最小的）
60的後繼是65。（沒有右子樹且為左兒子，前驅是其父親）
45的後繼是50。（沒有右子樹且為右兒子，前驅是其左父親的右父親）
80無後繼。 【沒有右子樹且為右兒子，但在80的左父親（祖先）裡沒有有右父親的節點】
二叉搜尋樹的删除：
删除有三種情況：
情況1：删除點為葉節點
直接删除
對于30，45，60，80這四個節點，即使删掉也不會改變原樹的平衡，故直接删掉
情況2：删除點右一個兒子
直接用兒子替換删除點的位置
如70，因為以70為根的子樹均大于65，是以删掉70後直接把70的兒子80接到70的位置并不會影響原樹的平衡
如果删除點隻有左兒子同理，是以删除點隻有一個兒子的話可以直接用兒子替換删除點
情況3：删除點右兩個兒子
找到删除點的後繼，用後繼代替删除點，然後讓後繼的兒子替換後繼的位置（情況2）
假設我們要删除65，那我們先找到65的後繼67，把67放到65的位置上（因為65的右子樹都大于65，是以67大于65的左子樹，又因為67在65的右右子樹裡最小，是以67小于處67外的65的右子樹，滿足平衡條件），變成了這樣