二叉排序樹（Binary Sort Tree）又稱二叉查找(搜尋)樹（Binary Search Tree）。其定義為二叉排序樹或者是空樹，或者是滿足如性質的二叉樹：
1)若它的左子樹非空，則左子樹上所有結點的值均小於根結點的值
2)若它的右子樹非空、則右子樹上所有結點的值均大於根結點的值
3)左、右子樹本身又各是一棵二叉排序樹。
二叉排序樹的查找算法
當用線性表作為表的組織形式時，可以有3種查找算法，其中以二分查找效率最高，但由於二分查找要求表中結點按關鍵字有序，且不能用鍊表作存儲結構，因此當表的插入或刪除操作頻繁時，為維護表的有序性，勢必要移動表中很多結點。這種由移動結點引起的額外時間開銷、就會抵消二分查找的優點。也就是說，二分查找只適用於靜態查找表。若要對動態查找表進行高效率的查找，可採用下面介紹的幾種特殊的二叉樹或樹作為表的組織形式。不妨將它們統稱為樹表。下面將分別講解在這些樹表上進行查找和修改操作的方法。
