高级算法设计与分析 学习笔记4 二叉查找树
左子树小于父节点小于右子树。
那么如何构建一个二叉查找树呢？
如何遍历一颗树？
这个其实就是中序遍历（在中间访问根节点）
如何查找一个元素？
可以看到后面这种方法更好，虽然都是递归，但后者不需要一直调用函数。
插入元素
这种算法的复杂度显然是等于树高。假如是平衡树就好了
寻找后继节点：
后继就是在这棵树中刚好比这个点大一位的节点。如果它有右子树就好办。没有的话，我们就要找让这个节点作为其左子树一部分的第一个节点
比如说13，它没有右子树，而且往上追溯一直都是右子树（都是比它小的）等到头一回发现是左子树的，那就是它的后继
找前驱也是类似意思。
删除节点
有两个子树的，那就要找其右子树中最小的数（也就是直接后继）来当新的父节点
可以注意到这棵树的性能和初始选择的值很有关系。似乎和快排有点关系啊。
随机建立的二叉查找树：
这样可以让树尽量平衡一点。