二叉搜索树(Binary Search Tree)（Java实现）

@

目录

• • 1.2、树的节点（binarynode）
  • 1.6、findmin
  • 1.7、findmax
• 二、完整代码实现（java）

1、二叉搜索树

1.1、 基本概念

二叉树的一个性质是一棵平均二叉树的深度要比节点个数n小得多。分析表明其平均深度为\(\mathcal{o}(\sqrt{n})\),而对于特殊类型的二叉树，即二叉查找树(binary search tree),其深度的平均值为\(\mathcal{o}(log n)\)。

二叉查找树的性质： 对于树中的每个节点x，它的左子树中所有项的值小于x中的项，而它的右子树中所有项的值大于x中的项。

由于树的递归定义，通常是递归地编写那些操作的例程。因为二叉查找树的平均深度为\(\mathcal{o}(log n)\)，所以一般不必担心栈空间被用尽。

1.2、树的节点（binarynode）

二叉查找树要求所有的项都能够排序，有两种实现方式；

1. 对象实现接口 comparable, 树中的两项使用compareto方法进行比较；
2. 使用一个函数对象，在构造器中传入一个比较器；

本篇文章采用了构造器重载，并定义了mycompare方法，使用了泛型，因此两种方式都支持，在后续的代码实现中可以看到。

节点定义：

    /**
     * 节点
     *
     * @param <anytype>
     */
    private static class binarynode<anytype> {
        binarynode(anytype theelement) {
            this(theelement, null, null);
        }

        binarynode(anytype theelement, binarynode<anytype> left, binarynode<anytype> right) {
            element = theelement;
            left = left;
            right = right;
        }

        anytype element; // the data in the node
        binarynode<anytype> left; // left child
        binarynode<anytype> right; // right child
    }

1.3、构造器和成员变量

    private binarynode<anytype> root;
    private comparator<? super anytype> cmp;

    /**
     * 无参构造器
     */
    public binarysearchtree() {
        this(null);
    }

    /**
     * 带参构造器，比较器
     *
     * @param c 比较器
     */
    public binarysearchtree(comparator<? super anytype> c) {
        root = null;
        cmp = c;
    }

关于比较器的知识可以参考下面这篇文章：
java中comparator的使用
关于泛型的知识可以参考下面这篇文章：
如何理解 java 中的 <t extends comparable<? super t>>

1.3、公共方法（public method）

主要包括插入，删除，找到最大值、最小值，清空树，查看元素是否包含；

    /**
     * 清空树
     */
    public void makeempty() {
        root = null;
    }

    public boolean isempty() {
        return root == null;
    }

    public boolean contains(anytype x){
        return contains(x,root);
    }

    public anytype findmin(){
        if (isempty()) throw new bufferunderflowexception();
        return findmin(root).element;
    }

    public anytype findmax(){
        if (isempty()) throw new bufferunderflowexception();
        return findmax(root).element;
    }

    public void insert(anytype x){
        root = insert(x, root);
    }

    public void remove(anytype x){
        root = remove(x,root);
    }

1.4、比较函数

如果有比较器，就使用比较器，否则要求对象实现了comparable接口；

    private int mycompare(anytype lhs, anytype rhs) {
        if (cmp != null) {
            return cmp.compare(lhs, rhs);
        } else {
            return lhs.compareto(rhs);
        }
    }

1.5、contains 函数

本质就是一个树的遍历；

    private boolean contains(anytype x, binarynode<anytype> t) {
        if (t == null) {
            return false;
        }

        int compareresult = mycompare(x, t.element);
        if (compareresult < 0) {
            return contains(x, t.left);
        } else if (compareresult > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }

1.6、findmin

因为二叉搜索树的性质，最小值一定是树的最左节点,要注意树为空的情况。

    /**
     * internal method to find the smallest item in a subtree
     * @param t the node that roots the subtree
     * @return node containing the smallest item
     */
    private binarynode<anytype> findmin(binarynode<anytype> t) {
        if (t == null) {
            return null;
        }
        if (t.left == null) {
            return t;
        }
        return findmin(t.left);
    }

1.7、findmax

最右节点；

    /**
     * internal method to find the largest item in a subtree
     * @param t the node that roots the subtree
     * @return the node containing the largest item
     */
    private binarynode<anytype> findmax(binarynode<anytype> t){
        if (t == null){
            return null;
        }
        if (t.right == null){
            return t;
        }
        return findmax(t.right);
    }

1.8、insert

这个主要是根据二叉搜索树的性质，注意当树为空的情况，就可以加入新的节点了，还有当该值已经存在时，默认不进行操作；

    /**
     * internal method to insert into a subtree
     * @param x the item to insert
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private binarynode<anytype> insert(anytype x, binarynode<anytype> t){
        if (t == null){
            return new binarynode<>(x,null,null);
        }
        int compareresult = mycompare(x,t.element);

        if (compareresult < 0){
            t.left = insert(x,t.left);
        }
        else if (compareresult > 0){
            t.right = insert(x,t.right);
        }
        else{
            //duplicate; do nothing
        }

        return t;
    }

1.9、remove

注意当空树时，返回null；
最后一个三元表达式，是在之前已经排除掉节点有两个儿子的情况下使用的。

    /**
     * internal method to remove from a subtree
     * @param x the item to remove
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private binarynode<anytype> remove(anytype x, binarynode<anytype> t){
        if (t == null){
            return t; // item not found ,do nothing
        }
        int compareresult = mycompare(x,t.element);

        if (compareresult < 0){
            t.left = remove(x,t.left);
        }
        else if (compareresult > 0){
            t.right = remove(x,t.right);
        }
        else if (t.left !=null && t.right!=null){
            //two children
            t.element = findmin(t.right).element;
            t.right = remove(t.element,t.right);
        }
        else
            t = (t.left !=null) ? t.left:t.right;
        return t;
    }

二、完整代码实现（java）

/**
 * @author longrookie
 * @description: 二叉搜索树
 * @date 2021/6/26 19:41
 */


import com.sun.source.tree.binarytree;

import java.nio.bufferunderflowexception;
import java.util.comparator;

/**
 * 二叉搜索树
 */
public class binarysearchtree<anytype extends comparable<? super anytype>> {

    /**
     * 节点
     *
     * @param <anytype>
     */
    private static class binarynode<anytype> {
        binarynode(anytype theelement) {
            this(theelement, null, null);
        }

        binarynode(anytype theelement, binarynode<anytype> left, binarynode<anytype> right) {
            element = theelement;
            left = left;
            right = right;
        }

        anytype element; // the data in the node
        binarynode<anytype> left; // left child
        binarynode<anytype> right; // right child
    }

    private binarynode<anytype> root;
    private comparator<? super anytype> cmp;

    /**
     * 无参构造器
     */
    public binarysearchtree() {
        this(null);
    }

    /**
     * 带参构造器，比较器
     *
     * @param c 比较器
     */
    public binarysearchtree(comparator<? super anytype> c) {
        root = null;
        cmp = c;
    }

    /**
     * 清空树
     */
    public void makeempty() {
        root = null;
    }

    public boolean isempty() {
        return root == null;
    }

    public boolean contains(anytype x){
        return contains(x,root);
    }

    public anytype findmin(){
        if (isempty()) throw new bufferunderflowexception();
        return findmin(root).element;
    }

    public anytype findmax(){
        if (isempty()) throw new bufferunderflowexception();
        return findmax(root).element;
    }

    public void insert(anytype x){
        root = insert(x, root);
    }

    public void remove(anytype x){
        root = remove(x,root);
    }




    private int mycompare(anytype lhs, anytype rhs) {
        if (cmp != null) {
            return cmp.compare(lhs, rhs);
        } else {
            return lhs.compareto(rhs);
        }
    }

    private boolean contains(anytype x, binarynode<anytype> t) {
        if (t == null) {
            return false;
        }

        int compareresult = mycompare(x, t.element);
        if (compareresult < 0) {
            return contains(x, t.left);
        } else if (compareresult > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }

    /**
     * internal method to find the smallest item in a subtree
     * @param t the node that roots the subtree
     * @return node containing the smallest item
     */
    private binarynode<anytype> findmin(binarynode<anytype> t) {
        if (t == null) {
            return null;
        }
        if (t.left == null) {
            return t;
        }
        return findmin(t.left);
    }

    /**
     * internal method to find the largest item in a subtree
     * @param t the node that roots the subtree
     * @return the node containing the largest item
     */
    private binarynode<anytype> findmax(binarynode<anytype> t){
        if (t == null){
            return null;
        }
        if (t.right == null){
            return t;
        }
        return findmax(t.right);
    }

    /**
     * internal method to remove from a subtree
     * @param x the item to remove
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private binarynode<anytype> remove(anytype x, binarynode<anytype> t){
        if (t == null){
            return t; // item not found ,do nothing
        }
        int compareresult = mycompare(x,t.element);

        if (compareresult < 0){
            t.left = remove(x,t.left);
        }
        else if (compareresult > 0){
            t.right = remove(x,t.right);
        }
        else if (t.left !=null && t.right!=null){
            //two children
            t.element = findmin(t.right).element;
            t.right = remove(t.element,t.right);
        }
        else
            t = (t.left !=null) ? t.left:t.right;
        return t;
    }

    /**
     * internal method to insert into a subtree
     * @param x the item to insert
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private binarynode<anytype> insert(anytype x, binarynode<anytype> t){
        if (t == null){
            return new binarynode<>(x,null,null);
        }
        int compareresult = mycompare(x,t.element);

        if (compareresult < 0){
            t.left = insert(x,t.left);
        }
        else if (compareresult > 0){
            t.right = insert(x,t.right);
        }
        else{
            //duplicate; do nothing
        }

        return t;
    }

}