定义

二叉搜索树，也被称为二叉查找树、二叉排序树，对于基础二叉树来说，数据查找、数据变动的效率都是非常低效的。因此才产生了二叉搜索树。

其定义规则如下：

• 若左子树不为空，则左子树上的各个节点值，均小于它的父节点的值
• 若右子树不为空，则右子树上的各个节点值，均大于它的父节点的值
• 没有值相等的节点
• 左右子树也分别为二叉搜索树
• 不一定是一颗完全二叉树，因此二叉搜索树不能用数组来存储

查找

流程：

1. 如果树是空的，则查找结束，无匹配
2. 如果被查找的值和节点的值相等，查找成功
3. 如果被查找的值小于节点的值，递归查找左子树
4. 如果被查找的值大于节点的值，递归查找右子树

插入

流程：

1. 先检测该元素是否在树中已经存在。如果已经存在，则不进行插入
2. 若元素不存在，则进行查找过程，并将元素插入在查找结束的位置

图解：

删除

删除节点为叶子节点

该方式最简单，只需要找到对应节点，直接删除即可。

删除的节点只有左子树

需要将节点的左子树替代被删除节点的位置

删除的节点只有右子树

需要将右子树替代被删除节点的位置，与左子树思想一致

删除的节点拥有左右子树

此情况操作起来最为复杂。操作流程如下：

1. 遍历待删除节点的左子树，找到其左子树中的最大节点
2. 将最大节点代替被删除节点
3. 删除左子树中的最大节点

同理，也可以选取右子树中的最小值取代它并删除原节点