二叉排序树

二叉排序树：BST，也称二叉查找树

二叉排序树或者为空树，或者为非空树，当为非空树时有如下特点：
1）若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字
2）若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字
3）左、右子树本身也分别是一棵二叉排序树

二叉排序树的查找：二叉树非空时，查找根结点，若相等则查找成功；若不等，则当小于根结点值时查找左子树，当大于根结点的值时，查找右子树，当查找到叶结点仍没查找到相应的值，则查找失败

二叉排序树的插入：若二叉排序树为空，则直接插入结点；若二叉排序树非空，当值小于根结点时，插入左子树；当值大于根结点时，插入右子树；当值等于根结点时不进行插入

构造二叉排序树：读入一个元素并建立结点，若二叉树为空将其作为根结点；若二叉排序树非空，当值小于根结点时，插入左子树；当值大于根结点时，插入右子树；当值等于根结点时不进行插入

二叉排序树的删除：
1）若被删除结点z是叶子结点，则直接删除
2）若被删除结点z只有一棵子树，则让z的子树成为z父结点的子树，代替z结点
3）若被删除结点z有两棵子树，则让z的‘中序序列直接后继’代替z，并删去直接后继结点

在二叉排序树中删除并插入某结点，得到的二叉排序树与原来不一定相同

二叉排序树的查找效率：