第十二章 二叉搜索树
对于一棵“完全”二叉树来说，最坏操作时间为 Θ(lgn)。然而，如果这棵树是一个 n 个结点组成的线性链，操作时间为 Θ(n)。在12.4节中，我们将看到一棵随机构造的二叉搜索树的期望高度为O(lgn)，因此这样一棵树上的动态集合的基本操作的平均运行的时间是 Θ(lgn)。

实际上，我们并不能总是保证随机地构造二叉搜索树，然而可以设计二叉搜索树的变体，来保证基本操作具有好的最坏情况

12.1 什么是二叉搜索树
二叉搜索树是一种满足下面规则的二叉树：

设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key<=x.key。如果y是x右子树中的一个结点，那么y.key >= x.key

简单说，就是一个结点的左子树必须小于等于该结点，一个结点的右子树要大于等于该结点。
二叉搜索树和堆有什么不同呢？
堆只保证上双亲结点比都子节点 大/小，不保证两个子节点中，大/小的一定在左/右。而二叉搜索树的左孩子结点 <= 右孩子结点。

二叉搜索树的遍历
二叉树的主要遍历有 3 种：前序遍历、中序遍历、后序遍历
前中后，是如何定义的呢？是根据一个子树的根结点的输出位置定义的，是先输出根结点还是后输出根结点。但左子树永远都是在右子树之前输出。

前序遍历：根结点 —> 左子树 —> 右子树 （根结点最先输出）
中序遍历：左子树—> 根结点 —> 右子树 （根结点在中间输出）
后序遍历：左子树 —> 右子树 —> 根结点 （根结点最后输出）

这三种遍历的主要思想是：

要理解：每次第 n 层的递归，都是第 n + 1 层递归的根节点。例如：上图(a)中的根结点下面的 5 所在的结点，是第 1 层递归；这个结点下面的 2 和 5 结点，是第 2(1+1) 层递归。所以，想要前序输出的话，在 “n 层递归”调用“n -1层递归”之前输出，否则，只能先输出左孩子结点或右孩子结点了。

遍历的时间复杂度为：Θ(n)
12.2 查询二叉搜索树

最小元素
因为二叉搜索树的性质：就是一个结点的左子树必须小于等于该结点，一个结点的右子树要大于等于该结点

后继结点和前驱结点
什么是后续结点？
一个结点 x 的后继结点是大于 x.key 的最小关键字的结点。

什么是前驱结点？
一个结点 x 的前驱结点是小于 x.key 的最大关键字的结点。

如何找到后继结点呢？

首先如果 x 结点有右子树的话，右孩子结点就是后继结点
如果没有右子树的话，就要向上去找。如果 x 结点的父结点不是 NIL 并且 x 结点是父结点的右孩子 的话，就一起向上找。因为如果父结点是 NIL 的话，证明到根点；如果 x 不是它的父结点的右孩子，说明 x 是它的父结点的左孩子，左孩子 <= 父结点，所以父结点就是后继结点。
（如果 x 是最大结点的话，返回是 NIL。因为最后 y 的值是根结点的父结点的引用 NIL）
12.3 插入和删除
关于插入
插入就是使用不断和父结点比（最初的父结点就是根结点），如果小于父结点，就去左子树再进行比较；如果大于，就去右子树进行比较。直到可以比较的结点为 NIL（说明它无左/右子结点了），再用 x 结点和当前的结点比较，如果小于当前结点就放到当前结点的左孩子上，如果大于等于当前结点，就放到右孩子上。

时间复杂度为：O(h)，h为树高度
关于删除
时间复杂度为：O(h)，h为树高度

12.4 随机构建二叉搜索树
随机构建二叉搜索树，就是把 n 个关键字按“随机次序”插入到一棵初始为空的树。
这样的话，期望高度为 O(lgn)。