二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高（也称作对半查找法）。

一棵空树，或者是具有下列性质的二叉树：

每个结点的C(i)为该结点的层次数。

最坏情况，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度(n+1)/2(和顺序查找相同）。

最好的情况，二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比。

也就是说，最好情况下的算法时间复杂度为O(1)，最坏情况下的算法时间复杂度为O(n)。

为了防止二叉排序树的最坏的情况，需要对二叉排序树进行优化。

比如

平衡二叉树（AVL树）

红黑树

堆树（Treap）

这些均可以使查找树的高度为O(log(n))