二叉搜索树

如果说二叉树是对链表的扩充，那么二叉搜索树则可以看作是对有序顺序表的扩充。

在二叉搜索树中，数据项之间，依照各自的关键码（key）彼此区分。因此，这种访问方式不妨称之为寻关键码访问（call-by-key）。

二叉搜索树（Binary Search Tree，BST）相比二叉树拥有以下特性：

查找

二叉搜索树的查找运用了减治法的思想，即从根节点出发，逐步地缩小查找范围，直到发现目标（成功），或查找范围缩小至空树（失败）。

对照中序遍历序列可见，整个过程可视作是在仿效有序顺序表的二分查找。

最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度。

先借助查找算法确定插入位置及方向，再将新节点作为叶子插入。

其时间复杂度主要取决于查找算法，故最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度。

删除算法稍微复杂，因为这不是简单的删除，还要保证删除后仍然是一棵二叉搜索树，假设要删除的目标节点为 \(x\)，可分以下两种情况考虑：

若 \(x\) 的某一子树为空，则可将其替换为另一子树。
若 \(x\) 有两棵子树，则可化繁为简，令 \(x\) 和它的直接后继互换，此时 \(x\) 将至多有一个右孩子（因为此节点是直接后继，它必然是某条左侧分支的末端），此时可采用上一种情况的方法。

最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度。