二叉搜索树

关于二叉树搜索树种，最难的部分是二叉搜索树的删除。

一、二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

二、二叉搜索树的操作

2.1查找

 public boolean search(int val){
           TreeNode cur = root;
           while (cur != null){
               if (cur.val < val){
                   cur = cur.right;
               }else if (cur.val > val){
                   cur = cur.left;
               }else {
                   return true;
               }
           }
           return false;
    }

2.2插入

二叉搜索树中不能插入val相同的结点

  public void insert(int val){
        if (root == null){
            root = new TreeNode(val);
            return;
        }
        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 {
                //相等时退出，因为搜索二叉树不允许有相等的值
                return;
            }
        }
        TreeNode node = new TreeNode(val);
        if (parent.val < val){
            parent.right = node;
        }else {
            parent.left = node;
        }
    }

2.3删除

我们设待删除的结点为cur，待删除结点的双亲结点为parent。

当cur.left == null.
1.若cur是root，则root = cur.right
2.cur不是root，cur是parent.left，则parent.left = cur. right
3.cur不是root，cur是parent.right，则parent.right = cur.right

  if (cur.left == null){
                //左边为空的情况
                if (cur == root){
                   root = cur.right;
                }else if (cur == parent.left){
                    parent.left = cur.right;
                }else {
                    parent.right = cur.right;
                }
            }

右边为空

当cur.right == null.
1.若cur是root，则root = cur.left
2.cur不是root，cur是parent.left，则parent.left = cur. left
3.cur不是root，cur是parent.right，则parent.right = cur.left

                  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;//tp是t的父亲结点
                 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;
                 }

完整代码

 public void revome(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 {
                revomeNode(parent,cur);
                return;
            }
        }
    }
    public void revomeNode(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;
                 }
            }
    }

三、二叉搜索树性能

删除和插入都需要查找，也就是说二叉搜索树的性能取决于查找的效率

最好的情况：完全二叉树，平均比较次数log₂N。
最坏的情况：单支树，平均比较次数N/2。

以上就是本文所有内容，如果对你有帮助的话，点赞收藏支持一下吧！