二叉排序树
二叉排序树（Binary Search Tree, BST），又称二叉搜索树，是一种重要的动态查找表结构。
定义
一种二叉树，对于每个结点：
- 左子树非空时，左子树所有结点关键字都小于该结点关键字
- 右子树非空时，右子树所有结点关键字都大于该结点关键字
- 中序遍历二叉排序树可得到有序序列
查找
可类比二分法查找，查找过程产生一条从根节点到目标结点（或空结点）的路径。
由于二叉排序树本身不是唯一的，树的形态会影响查找效率，但平均查找长度仍然为 O(log n)。
插入
若二叉树为空，则待插入结点为根结点。二叉树非空时，若待插入结点与根结点相同则无需插入，大于根结点则插入到右子树，小于根结点则插入到左子树。插入的结点一定是叶子结点。
可以通过循环调用插入函数来生成二叉排序树。
删除
删除一个节点需要保持二叉排序树的特性。
四种情况：
- 叶子结点：直接释放，修改双亲指针
- 只有左子树：用左子树根节点顶替原结点
- 只有右子树：用右子树根节点顶替原结点
- 左右子树都存在：将左子树作为右子树中最小结点（最左侧结点）的左子树；或将左子树中最大结点或右子树中最小结点来替换该结点
