二分搜索树的增删改查

什么是二分搜索树

首先我们要先知道二叉树是什么，二叉树其实就是从一个根节点左右两端延伸出左右结点，延伸出的结点再次延伸出结点，然后一直延伸下去，所以树这种数据结构天生满足递归特性。

而二分搜索树就是对二叉树做了一个限制，首先二分搜索树中的元素必须是可比较的（对于Java来说就是必须继承Comparable接口）。为什么需要它可比较呢？就是因为，二分搜索树的排列需要根据数值来排列。

二分搜索树的某个结点的左孩子必须小于原来的节点且某个结点的左子树的所有结点必须比这个结点小。

右边同上。

什么是二分搜索树和二叉树

二分搜索树的基本定义

根据上面的定义，我们很容易就能写出代码

public class BinarySearchTree<E extends Comparable<E>> {
  private class Node{
    private E e;
    private Node left,right;
    private Node(E e){
      this.e=e;
      left=null;
      right=null;
    }
  }

  private Node root;
  private int size;

  public BinarySearchTree(){
    root=null;
    size=0;
  }
}

二分搜索树的一些方法

首先就是getSize()和isEmpty()方法，很容易，返回size和判断size是否为0就行了

public int size(){
  return size;
}

public boolean isEmpty(){
  return size==0;
}

添加元素

添加元素的时候我们只需要在树的叶子节点中添加就行了。

public void add(E e){
    //如果根节点为空，那么直接new
    if(root==null){
        root=new Node(e);
    }else{
        add(root,e);
    }
}
private void add(Node node,E e){
  //如果这个结点不等于这个时候才能添加元素
  if (!e.equals(node.e)){
    //如果插入元素小于该结点的元素且该结点的左孩子为空
    //那么直接插入左孩子
    if (e.compareTo(node.e)<0&&node.left==null){
      node.left=new Node(e);
      size++;
    }
    //这个同上
    else if (e.compareTo(node.e)>0&&node.right==null){
      node.right=new Node(e);
      size++;
    }
    //如果小于，那么就递归调用
    else if (e.compareTo(node.e)<0){
      add(node.left,e);
    }else if (e.compareTo(node.e)>0){
      //同上
      add(node.right,e);
    }
  }
}

当然添加方法还有优化的地方

public void add(E e){
  add(root,e);
}
private Node add(Node node,E e){
  if (node==null){
    //该结点为空，那么直接返回给上一级new出来的元素为e的节点，这里就是添加，只是现在遍历到最后了而已
    return new Node(e);
  }else if (e.compareTo(node.e)<0){
    //如果小于，那么该结点的左孩子就是下一层二分搜索树的添加元素后的二分搜索树
    node.left=add(node.left,e);
  }else if (e.compareTo(node.e)>0){
    //如果大于，那么该结点的右孩子就是下一层二分搜索树的添加元素后的二分搜索树
    node.right=add(node.right,e);
  }
  //最后return被添加过结点的根节点
  return node;
}

查询元素

这里就是判断二分搜索树是否包含某个元素

public boolean contains(E e){
    return contains(root,e);
}
private boolean contains(Node node,E e){
    //如果该树的根节点就是空，那么直接false
    if (root==null){
    return false;
    }
    //如果查询到了那么返回该结点
    if (e.equals(node.e)){
    return true;
    }else if (e.compareTo(node.e)<0){
    //小于的时候遍历左孩子树
    return contains(node.left,e);
    }else if (e.compareTo(node.e)>0){
    //大于的时候遍历右孩子树
    return contains(node.right,e);
    }
    return false;
}

获取最小元素和最大元素

public E minimum(){
    //当树的大小为0就不能删除
    if (size==0){
    throw new IllegalArgumentException("BST is empty");
    }
    return minimum(root).e;
}
private Node minimum(Node node) {
    //当遍历到最后的某个结点的左孩子为null，那么这个结点就是最小元素
    if (node.left==null){
    return node;
    }
    return minimum(node.left);
}
//同理
public E maximum(){
if (size==0){
  throw new IllegalArgumentException("BST is empty");
}
return maximum(root).e;
}
private Node maximum(Node node){
if (node.right==null){
  return node;
}
return maximum(node.right);
}

删除元素，其中删除元素是最复杂的，对于删除最小最大元素来说并不复杂，因为只需要往左往右遍历二分搜索树就行了，但是对于任意元素的删除就要考虑多种情况。

删除最小元素

public E removeMin(){
  if (size==0){
    throw new IllegalArgumentException("BST is empty");
  }
  return removeMin(root).e;
}

private Node removeMin(Node node){
  //如果左孩子为空，那么这个结点就是要删除的结点
  if (node.left==null){
    //将该结点的右子树放入临时变量
    Node rightNode=node.right;
    //将这个结点的右子树置为null，然后返回刚刚的临时变量rightNode
    node.right=null;
    size--;
    return rightNode;
  }
  //不然就一直向左遍历，并且将下一级删除后返回的二分搜索树赋值给上一级的结点
  node.left=removeMin(node.left);
  return node;
}

删除最大元素

public E removeMax(){
  if (size==0){
    throw  new IllegalArgumentException("BST is empty");
  }
  return removeMax(root).e;
}

private Node removeMax(Node node){
  if (node.right==null){
    Node leftNode=node.left;
    node.left=null;
    size--;
    return leftNode;
  }
  node.right=removeMax(node.right);
  return node;
}

删除某个结点

我们可以通过寻找需要被删除节点的后继或者前驱，并且把它从原来树中删除然后代替被删除节点的位置

通过后继删除元素

通过前驱删除元素

这里我只写了通过后继删除某个元素，当然前驱书写方式也是一样的

public void remove(E e){
  root=remove(root,e);
}

private Node remove(Node node,E e){
  if (node==null){
    return null;
  }
  if (e.compareTo(node.e)<0){
    node.left=remove(node.left,e);
    return node;
  } else if (e.compareTo(node.e)>0) {
    node.right=remove(node.right,e);
    return node;
  }
  //如果相等就要删除
  else {
    //首先判断这个树是不是只有一边的孩子
    //如果只有左边有孩子或者只有右边有孩子
    if (node.right==null){
      //如果只有左子树
      //那么我们将该结点的左子树返回给上一节点的左子树
      size--;
      return node.left;
    }else if (node.left==null){
      size--;
      return node.right;
    }
    //如果左右都有孩子
    //寻找该节点的后继节点
    //后继结点就是离该结点最近的节点（数值最近而且是大于该节点）
    //那么这个结点的后继结点就是该节点右孩子的最小结点
    Node successorNode=minimum(node.right);
    //我们需要删除该节点的后继结点并且将删除后的右孩子树赋值给我们获取到的successorNode的右孩子
    successorNode.right=removeMin(node.right);
    successorNode.left=node.left;
    node.left=node.right=null;
    return successorNode;
  }
}