定義
二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
查找
二叉樹步驟：若根結點的關鍵字值等於查找的關鍵字，成功。
否則，若小於根結點的關鍵字值，遞歸查左子樹。
若大於根結點的關鍵字值，遞歸查右子樹。
若子樹為空，查找不成功。
平均情況分析（在成功查找兩種的情況下）：
在一般情況下，設 P（n，i）為它的左子樹的結點個數為 i 時的平均查找長度。如圖的結點個數為 n = 6 且 i = 3; 則 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：這裡 P(3)、P(2) 是具有 3 個結點、2 個結點的二叉分類樹的平均查找長度。 在一般情況，P（i）為具有 i 個結點二叉分類樹的平均查找長度。平均查找長度= 每個結點的深度的總和 / 總結點數
（上圖應為左子樹P(3)，右子樹P(2)）
P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
二叉排序樹∴ P（n）= P（n,i）/ n <= 2(1+I/n)lnn
因為 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)
插入刪除
二叉樹與次優二叉樹相對，二叉排序樹是一種動態樹表。其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等於給定值的結點時再進行插入。新插入的結點一定是一個新添加的葉子結點，並且是查找不成功時查找路徑上訪問的最後一個結點的左孩子或右孩子結點。
插入算法
首先執行查找算法，找出被插結點的父親結點。
判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。
若二叉樹為空。則首先單獨生成根結點。
注意：新插入的結點總是葉子結點。
刪除結點
在二叉排序樹刪去一個結點，分三種情況討論：
若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構，則可以直接刪除此子結點。
若*p結點只有左子樹PL或右子樹PR，此時只要令PL或PR直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。
若*p結點的左子樹和右子樹均不空。在刪去*p之後，為保持其它元素之間的相對位置不變，可按中序遍歷保持有序進行調整，可以有兩種做法：
其一是令*p的左子樹為*f的左/右(依*p是*f的左子樹還是右子樹而定)子樹，*s為*p左子樹的最右下的結點，而*p的右子樹為*s的右子樹；
其二是令*p的直接前驅（或直接後繼）替代*p，然後再從二叉排序樹中刪去它的直接前驅（或直接後繼）－即讓*f的左子樹(如果有的話)成為*p左子樹的最左下結點(如果有的話)，再讓*f成為*p的左右結點的父結點。
在二叉排序樹上刪除一個結點的算法如下：
1.若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構，則可以直接刪除此子結點。
2.若*p結點只有左子樹PL或右子樹PR，此時只要令PL或PR直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。
3.若*p結點的左子樹和右子樹均不空。在刪去*p之後，為保持其它元素之間的相對位置不變，可按中序遍歷保持有序進行調整，可以有兩種做法：
其一是令*p的左子樹為*f的左/右(依*p是*f的左子樹還是右子樹而定)子樹，*s為*p左子樹的最右下的結點，而*p的右子樹為*s的右子樹；
其二是令*p的直接前驅（或直接後繼）替代*p，然後再從二叉排序樹中刪去它的直接前驅（或直接後繼）－即讓*f的左子樹(如果有的話)成為*p左子樹的最左下結點(如果有的話)，再讓*f成為*p的左右結點的父結點。
在二叉排序樹上刪除一個結點的算法如下：
C++代碼
性能分析
二叉排序樹每個結點的C(i)為該結點的層次數。最壞情況下，當先後插入的關鍵字有序時，構成的二叉排序樹蛻變為單支樹，樹的深度為其平均查找長度(n+1)/2(和順序查找相同），最好的情況是二叉排序樹的形態和折半查找的判定樹相同，其平均查找長度和log 2 (n)成正比。
最佳化
Size Balanced Tree(SBT)
AVL樹
紅黑樹
Treap(Tree+Heap)
這些均可以使查找樹的高度為O(log(n))
