二叉搜索树

二叉搜索树 (Binary search tree) 是一种二叉树的树形数据结构，其定义如下：

1. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

2. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

3. 二叉搜索树的左右子树均为二叉搜索树。

空树是二叉搜索树

时间复杂度

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 $n$ 个结点的二叉搜索树中，这些操作的

• 最优时间复杂度为 $O(\log n)$， 此时二叉搜索树完全平衡， 近似于

• 最坏时间复杂度为 $O(n)$ ， 此时二叉搜索树退化为了单链表的形式， 退化为顺序查找

随机构 造这样一棵二叉搜索树的期望高度为 $O(\log n)。