文章目录
一、搜索树
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
仔细观察上图，可以发现二叉搜索树的一个特性：
中序遍历二叉搜索树是有序的，所以二叉搜索树也被称为二叉排序树
二、使用代码实现一棵二叉搜索树
1.查找
遍历这棵树，先从树的根节点开始查找，如果树的根节点是我们要查找的元素就返回根节点，如果要查找的元素比我们的根节点小，就去树的左边寻找，如果比我们的根节点大就去树的右边寻找，直到遍历完整棵树为止
代码如下：
public boolean search(int val) {
TreeNode cur = root;
while (cur != null) {
//左树中去找
if(cur.val > val) {
cur = cur.left;
//右树中去找
}else if(cur.val < val) {
cur = cur.right;
}else {
return true;
}
}
return false;
}
2.插入
往二叉搜索树插入一个元素的时候，我们要注意两点，首先如果二叉搜索树为空，则直接令 root 为当前插入的节点即可，如果不为空，则新的元素会依次与节点比较，如果比根节点大，则去根的右边，比根节点小，则去根的左边
首先定义一个 cur 引用，当 cur 等于 null 了，则表示是我要插入的位置，找到了要插入的位置，我们还得知道这个位置的父亲节点是谁，通过父亲节点将元素插入到该二叉树中
代码如下：
public void insert(int val) {
if(root == null) {
root = new TreeNode(val);
return;
}
TreeNode cur = root;
//记录cur的上一个节点
TreeNode parent = null;
while (cur != null) {
if(cur.val < val) {
parent = cur;
cur = cur.right;
}else if(cur.val > val) {
parent = cur;
cur = cur.left;
}else {
return;
}
}
//cur为空 将val插入到parent的左树或者右树
TreeNode node = new TreeNode(val);
if(parent.val > val) {
parent.left = node;
}else {
parent.right= node;
}
}
3.删除（重点）
二叉搜索树中删除一个元素是很麻烦的，我们要把每一种情况都列举出来，而且在删除完一个元素后还要满足二叉搜素树的性质
设 cur 为要删除的元素，parent为待删除结点的双亲结点为，首先我们要判断这个二叉搜索树中，是否存在要删除的节点，这个方法在上面已经写过了，找到要删除的节点后，再对每一种情况进行删除：
1.cur没有左子树
cur 是 root，则 root = cur.right
cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
图解如下：
2.cur没有右子树
cur 是 root，则 root = cur.left
cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
图解如下：
3.cur既有左子树又有右子树
使用替换法进行删除，即在 cur 的右子树中，一直往左寻找最小的元素，将这个最小值赋值给要删除节点的 val 值中，接着把这个最小元素的节点删除即可
图解如下：
代码如下：
public void remove(int val) {
TreeNode cur = root;
TreeNode parent = null;
while (cur != null) {
if(cur.val < val) {
parent = cur;
cur = cur.right;
}else if(cur.val > val) {
parent = cur;
cur = cur.left;
}else {
removeNode(parent,cur);
return;
}
}
}
private void removeNode(TreeNode parent,TreeNode cur) {
//左树为空
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(cur == parent.left) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
//右树为空
}else if(cur.right == null) {
if(cur == root) {
root = cur.left;
}else if(cur == parent.left) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
//两个都不为空 使用替换法的方式来删除节点
}else {
TreeNode t = cur.right;
TreeNode tp = cur;
while (t.left != null) {
tp = t;
t = t.left;
}
cur.val = t.val;
if(tp.left == t) {
tp.left = t.right;
}else {
tp.right = t.right;
}
}
}
总结
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多
二叉搜索树在最好的情况下为完全二叉树，查找的平均比较次数为：logn
二叉搜索树在最差的情况下退化成单分支，查找的平均比较次数为：n/2
注意：
二叉搜索树不要求是完全二叉树或满二叉树，甚至会出现单分支的二叉搜索树，所以针对这种特殊的情况进行了优化也就延申出了 AVL树，当发现二叉搜索树左右子树高度差太大，会自动旋转，以致平衡，避免旋转的次数太多，又引入了红黑树，给节点增加了颜色，细节部分后期讲解，这里有个概念即可