二分搜索树的优势

高效
- 不仅可以查找数据;还可以高效地插入,删除数据-动态维护数据
可以方便的回答很多数据之间的关系问题
- min(最小值),max(最大值),floor(首次出现),ceil(最后一次出现),rank(排名),select(选择查询)

	查找元素	插入元素	删除元素
普通数组	O(n)	O(n)	O(n)
顺序数组	O(logn)	O(n)	O(n)
二分搜索树	O(logn)	O(logn)	O(logn)

特点

首先是一棵二叉树(不一定是完全二叉树)
每个节点的键值都大于左孩子(左子树的所有节点)
每个节点的键值都小于右孩子(右子树的所有节点)
以左右孩子为根的子树仍为二分搜索数

右孩子的值是不会超过父节点的父节点的值的,如果超过的话,应该是作为父节点的父节点的右子树

二分搜索树Binary Search Tree

代码实现

二叉搜索树基本结构

内部维护了一个内部类,用于维护各个节点之间的关系

public class BST<K,E extends Comparable<E>> {

    //二分搜索树内部的节点
    private class Node{
        E data;
        Node left,right;

        public Node(E data){
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    //二分搜索树的大小
    private int size;

    //根元素
    private Node root;

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

基本方法

获取二叉搜索树的大小
判断是否为空

/**
     * 获取二分搜索树的大小
     * @return 二分搜索树的大小
     */
    public int getSize(){
        return size;
    }

    /**
     * 判断树是否为空
     * @return true:树为空  false:树不为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

增加元素

通过递归的方式寻找到正确的位置,再进行添加

/**
     * 增加元素  调用的函数 
     * @param data 添加的数据
     */
public void add(E data) {
        root = add(root, data);
    }


/**
     * 通过递归寻找到合适的位置
     * @param root 节点
     * @param data 数据
     * @return 参数中的node
     */
    private Node add(Node root, E data){

        //根节点为空  直接在根节点进行添加
        if (root == null){
            size ++;
            return new Node(data);
        }

        //与根节点进行比较 调用递归直至放到正确的位置
        if (data.compareTo(root.data) < 0){
            root.left = add(root.left,data);
        }else {
            root.right = add(root.right,data);
        }

        return root;

    }

删除元素

删除任意元素

根据二叉树的特点递归(也可以采用循环的方式)查找,删除.这里要注意移除节点之后,其他节点的变换

删除最大值
删除最小元素

/**
     * 删除最小值
     * @return 删除的最小值
     */
    public E removeMin(){
        E minData = getMin();
        root = removeMin(root);
        return minData;
    }

    /**
     * 删除掉以node为根的二分搜索树中最小的节点
     * @param node 传入节点
     * @return 返回删除后新的二分搜索树的根
     */
    private Node removeMin(Node node){
        //递归的终止条件:找到了最小的节点
        if (node.left == null){
            //node.right为空也不影响
            Node rightNode = node.right;
            node.right = null;
            size--;
            //返回这一步,就将node.right的节点变成了父亲节点
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 删除最大值
     * @return 删除的最大值
     */
    public E removeMax(){
        E maxData = getMax();
        root = removeMax(root);
        return maxData;
    }

    /**
     * 删除掉以node为根的二分搜索树中最大的节点
     * @param node 传入节点
     * @return 返回删除后新的二分搜索树的根
     */
    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;
    }

查找元素

是否存在该元素

同样是通过递归的方式进行

获取最值


    /**
     * 查询二叉搜索树中是否存在该元素
     * @param data 查询的数据
     * @return false-不存在,true-存在
     */
    public boolean contains(E data){
        return contains(root,data);
    }

    private boolean contains(Node node,E data){
        //如果根节点为空时,结束递归
        if (node == null){
            return false;
        }

        //找到相等的值
        if (node.data.compareTo(data) == 0){
            return true;
        }
        //如果寻找的节点值比当前根节点大  向右继续寻找
        else if (node.data.compareTo(data) < 0){
            return contains(node.right,data);
        }
        //如果寻找的节点值比当前根节点小  向左继续寻找
        else {
            return contains(node.left,data);
        }
    }


/**
     * 获取最大值
     * @return 二叉搜索树中的最大值
     */
    public E getMax(){
        if (isEmpty()){
            throw new IllegalArgumentException("BinarySearchTree is empty");
        }
        return getMax(root).data;
    }

    /**
     * 通过递归获取最右边的节点,也就是值最大的节点
     * @param node 节点
     * @return 最右边的节点
     */
    private Node getMax(Node node){
        if (node.right == null){
            return node;
        }
        return getMax(node);
    }


/**
     * 获取最小值
     * @return 最小值
     */
    public E getMin(){
        if (isEmpty()){
            throw new IllegalArgumentException("BinarySearchTree is empty");
        }
        return getMin(root).data;
    }

    /**
     * 通过递归获取最左边的节点,也就是值最小的节点
     * @param node 节点
     * @return 最左边的节点
     */
    private Node getMin(Node node){
        if (node.left == null){
            return node;
        }
        return getMin(node);
    }