二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：


（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）任意节点的左、右子树也分别为二叉查找树。

（4）没有键值相等的节点（no duplicate nodes）。 


因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。