定義
二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3）左、右子樹也分别為二叉排序樹；
（4）沒有鍵值相等的節點。
查找
步驟：
若根結點的關鍵字值等于查找的關鍵字，成功。
否則，若小于根結點的關鍵字值，遞歸查左子樹。
若大于根結點的關鍵字值，遞歸查右子樹。
若子樹為空，查找不成功。
平均情況分析（在成功查找兩種的情況下）：
在一般情況下，設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)=（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)
步驟
若根結點的關鍵字值等于查找的關鍵字，成功。
否則，若小于根結點的關鍵字值，遞歸查左子樹。
若大于根結點的關鍵字值，遞歸查右子樹。
若子樹為空，查找不成功。
插入算法：
首先執行查找算法，找出被插結點的父親結點。
判斷被插結點是其父親結點的左、右兒子。将被插結點作為葉子結點插入。
若二叉樹為空。則首先單獨生成根結點。
注意：新插入的結點總是葉子結點。
voidInsertBST(t，key)
//在二叉排序樹中插入查找關鍵字key
{
if(t==NULL){
t=newBiTree;
t->lchild=t->rchild=NULL;
t->data=key;
return;}
if(keydata)InsertBST(t->lchild,key);
elseInsertBST(t->rchild,key);
}
voidCreateBiTree(tree,d【】,n）
//n個數據在數組d中，tree為二叉排序樹根
{tree=NULL;
for(i=0;iInsertBST(tree,d);}
删除結點
在二叉排序樹删去一個結點，分三種情況讨論：
若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由于删去葉子結點不破壞整棵樹的結構，則可以直接删除此子結點。
若*p結點隻有左子樹PL或右子樹PR，此時隻要令PL或PR直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。
若*p結點的左子樹和右子樹均不空。在删去*p之後，為保持其它元素之間的相對位置不變，可按中序遍曆保持有序進行調整，可以有兩種做法：
C代碼
性能分析
每個結點的C(i)為該結點的層次數。最壞情況下，當先後插入的關鍵字有序時，構成的二叉排序樹蛻變為單支樹，樹的深度為其平均查找長度(n+1)/2(和順序查找相同），最好的情況是二叉排序樹的形态和折半查找的判定樹相同，其平均查找長度和log2(n)成正比。
優化
SizeBalancedTree(SBT)
AVL樹
紅黑樹
Treap(Tree+Heap)
這些均可以使查找樹的高度為O(log(n))
