二叉排序树定义
二叉排序树，英文名Binary Sort Tree，是一种特殊的二叉树，极大的改善了二叉树节点查找的效率，又称为二叉查找树。
二叉排序树特点
下图就是一棵二叉排序树：
二叉排序树具体如下3大特征：
1.它要求节点的左子树小于该节点本身， 右子树大于该节点，每个节点都符合这样的规则；
2.若左子树不为空，左子树上节点值均小于或等于根节点的值；
3.若右子树不为空，右子树上节点值均大于或等于根节点的值；
二叉排序树构建
为了让大家更加直观的了解二叉排序树，我会手把手构建一棵二叉树排序树。
假设我们有以下数据，我们按从左到右的顺序来构建二叉排序树。
1.首先将7作为根节点
2.构造左节点
此时取出第二个节点3，由于3比7小，并且7的左子节点为空，所以把3放在7的左子节点位置，如下图所示：
3.构造右节点
接着取出第三个节点10，由于10比7大，并且7的右子节点为空，所以把10放在7的右子节点位置，如下图所示：
4.继续构造下一排的子节点
接着取出第四个节点1，由于1比7小，进入左子树3继续比较，由于1比3小，则1为3的左子树。
如下图所示：
5.依然类推
直到所有节点都放置完毕，最终构造完成二叉排序树，如下图所示：
二叉排序树查找
二叉排序树的查找，与二叉排序树构建过程类似。
下面我以刚才我们构建好的完整二叉排序树为例，准备查找节点9，如下图所示：
整个过程，大致分为如下3步：
第一步：将9与根节点进行比较，由于9大于7，因为7的右子节点不为空，所以向右子树进行查找；
第二步：接着在右子树进行比较，由于9小于10，因为10的左子节点不为空，所以向左子树进行查找；
第三步：将9与9进行比较，发现两者相等，则查找成功，结束整个查找过程。
二叉排序树删除
二叉排序树的删除情况比较复杂，有以下三种情况需要考虑：
1.删除叶子节点
直接从二叉排序中删除即可不会影响到其他结点。
直接删除1这个节点，不会有啥影响，删除后如下图所示：
2.删除只有一个子树的节点
比如：我要删除以14这个节点，由于没有右孩子，只有左孩子。
删除过程：先把10指向14的右指针移动，去指向13，然后再删除14。
如下图所示：
3.删除有两个子树的节点
比如要删除7、3、10，这些都是都有两个子树。
大致思路：
找到待删除节点targetNode及其父节点parentNode； 从targetNode的右子树中找到最小的节点righMintNode； 用一个临时遍历temp来保存righMintNode的值； righMintNode= null； targetNode.value=temp；
二叉排序树平衡
二叉排序树虽然比普通树查找更快，但是也要一个致命的缺点：就是会出现平衡问题。
比如：二叉排序树在经过多次插入与删除后，有可能导致如下右图的结构：
搜索性能已经是线性的了，所以，使用二叉搜索树还要考虑尽可能保持上面左图的结构，和避免上面右图的结构，也就是所谓的“平衡”问题 。
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》