當查找表以順序存儲結構存儲且需要保持有序時，若對查找表進行插入、刪除或排序操作，就必須移動大量的記錄，當記錄數很多時，這種移動的代價很大。
若查找表無序，則插入刪除可無需移動大量記錄，但於查找不利。
利用樹的形式組織查找表，可以對查找表進行動態高效的查找。
二叉排序樹(Binary Sort Tree或Binary Search Tree) 的定義為：二叉排序樹或者是空樹，或者是滿足下列性質的二叉樹。
(1) ：若左子樹不為空，則左子樹上所有結點的值(關鍵字)都小於根結點的值；
(2) ：若右子樹不為空，則右子樹上所有結點的值(關鍵字)都大於根結點的值；
(3) ：左、右子樹都分別是二叉排序樹。
結論：若按中序遍歷一棵二叉排序樹，所得到的結點序列是一個遞增序列。
1 查找思想
①若根結點為空，則表示查找失敗；
②根節點非空，將給定的K值與二叉排序樹的根結點的關鍵字進行比較
若相等： 則查找成功；
③ 給定的K值小於BST的根結點的關鍵字：繼續在該結點的左子樹上進行查找；
④ 給定的K值大於BST的根結點的關鍵字：繼續在該結點的右子樹上進行查找。
2 算法實現
BSTNode *BST_Serach(BSTNode *T , KeyType key)
{ if (T==NULL) return(NULL) ;
else
{ if (T->key==key) ) return(T) ;
else if (key< T->key) )
return(BST_Serach(T->Lchild, key)) ;
else return(BST_Serach(T->Rchild, key)) ;
}
}
插入的過程與查找類似，只是當查找不成功時，根據關鍵字與根結點的大小，將新結點（關鍵字的值）插入根結點的相應孩子的位置（左或者右）. 在BST樹中插入一個新結點，要保證插入後仍滿足BST的性質。
1 插入思想
在BST樹中插入一個新結點x時，若BST樹為空，則令新結點x為插入後BST樹的根結點；否則，將結點x的關鍵字與根結點T的關鍵字進行比較：
① 若相等： 不需要插入；
② 若x.keykey：結點x插入到T的左子樹中；
③ 若x.key>T->key：結點x插入到T的右子樹中。
算法實現
⑴ 遞歸算法
⑵ 非遞歸算法
void Insert_BST (BSTNode *T , KeyType key)
{ BSTNode *x, *p , *q ;
x=(BSTNode *)malloc(sizeof(BSTNode)) ;
X->key=key; x->Lchild=x->Rchild=NULL ;
if (T==NULL) T=x ;
else
{ p=T ;
while (p!=NULL)
{ if (p->key==x->key ) return ;
q=p ; /*q作為p的父結點 */
if (x->key< p->key) ) p=p->Lchild ;
else p=p->Rchild ;
}
if (x->key<q->key ) q->Lchild=x ;
else q->Rchild=x ;
}
}
對於一個無序序列可以通過構造一棵BST樹而變成一個有序序列。
由算法知，每次插入的新結點都是BST樹的葉子結點，即在插入時不必移動其它結點，僅需修改某個結點的指針。
利用BST樹的插入操作，可以從空樹開始逐個插入每個結點，從而建立一棵BST樹
二叉排序樹查找關鍵字的比較次數，等於該結點所在的層次數（查找成功）； 若查找不成功，其比較次數最多為樹的深度。
對於一棵具有n個結點的樹來說，其深度介於㏒2n+1與n之間。
二叉排序樹的形態對於查找效率至關重要，或者說，一棵二叉排序樹不一定就能提高查找的速度，而是要看這棵樹的形態。
如果能構造出一棵左右子樹相對“均衡”的樹，則樹的深度就會比較小，就能體現出二叉排序樹的良好性質，查找時能得到最好的效率，這就是平衡二叉排序樹。
平衡二叉排序樹(Balanced Binary Tree或Height-Balanced Tree)是在1962年由俄羅斯數學家Adelson-Velskii和Landis提出的，又稱AVL樹。
平衡二叉樹或者是空樹，或者是滿足下列性質的二叉樹。
⑴ 左子樹和右子樹深度之差的絕對值不大於1；
⑵ 左子樹和右子樹也都是平衡二叉樹。
平衡因子(Balance Factor) ：二叉樹上結點的左子樹的深度減去其右子樹深度。
平衡二叉樹上每個結點的平衡因子只可能是-1、0和1，如果有一個結點的平衡因子的絕對值大於1， 該二叉樹就不是平衡二叉樹。
如果一棵二叉樹既是二叉排序樹又是平衡二叉樹，稱為平衡二叉排序樹(Balanced Binary Sort Tree) 。
結點類型定義如下：
typedef struct BNode
{ KeyType key ; /* 關鍵字域 */
int Bfactor ; /* 平衡因子域 */
… /* 其它數據域 */
struct BNode *Lchild , *Rchild ;
}BSTNode ; 在平衡二叉排序樹上執行查找的過程與二叉排序樹上的查找過程完全一樣，即在AVL樹上執行查找時，和給定的K值比較的次數不超過樹的深度。
具有n個結點的AVL樹，最大深度是多少？
含義n個結點的平衡二叉樹的最大深度是O(㏒2n)
在平衡二叉排序樹上進行查找的平均查找長度和
㏒2n同一個數量級，平均時間復雜度為O(㏒2n)。
基本思想
在構建二叉排序樹的過程中，每當插入（刪除）一個結點時，
先檢查是否因插入而破壞了平衡，
若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。
