07_二叉搜索树

二叉搜索树，又称二叉查找树、二叉排序树，是二叉树的一种，是应用非常广泛的一种二叉树英文简称BST。

二叉搜索树的性质：

• 任意一个节点的值都大于其左子树所有节点的值
• 任意一个节点的值都小于其右子树所有节点的值
• 它的左右子树也是一棵二叉搜索树
• 二叉搜索树可以大大提高搜索数据的效率
• 二叉搜索树存储的元素必须具备可比较性，比如int、double等，如果是自定义类型，需要指定比较方式，不允许为null

二叉搜索树的接口设计

• int size() // 元素的数量
• boolean isEmpty() // 是否为空
• void clear() // 清空所有元素
• void add(E element) // 添加元素
• void remove(E element) // 删除元素
• boolean contains(E element) // 是否包含某元素

package BST;

import BinaryTree.printer.BinaryTreeInfo;

import java.util.Comparator;

public class LZBinarySearchTree<E> implements BinaryTreeInfo {

    private int size;
    private Node<E> root;
    private Comparator<E> comparator;

    public LZBinarySearchTree(){
        this(null);
    }

    public LZBinarySearchTree(Comparator<E> comparator){
        this.comparator = comparator;
    }

    /**
     * 树节点的个数
     * @return size
     */
    public int size(){
        return size;
    }

    /**
     * 是否是空树
     * @return boolean
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空
     * @return boolean
     */
    public void clear(){
        root = null;
        size = 0;
    }

    /**
     * 添加元素
     * @param element
     */
    public void add(E element){
        elementNotNullCheck(element);
        //添加的是第一个节点
        if (root == null){
            root = new Node<>(element,null);
            size++;
            return;
        }
        //添加的不是第一个节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null){
            cmp = (compare(element,node.element));
            parent = node;
            if (cmp<0){
                node = node.left;
            }else if(cmp>0){
                node = node.right;
            }else {
                node.element = element;
                return;
            }
        }

        Node<E> newNode = new Node<>(element,parent);
        if (cmp>0){
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;
    }

    /**
     * 移除某个元素
     */
    public void remove(E element){
        Node<E> node = node(element);
        if (node == null) return;
        size--;

        if (node.left != null && node.right != null){  //度为2的节点
            Node<E> s = successor(node); //找到后继节点
            node.element = s.element; //用后继节点的值覆盖度为2的节点的值
            node = s; //删除后继节点
        }

        //删除node节点，node节点的度必然是1或者0
        //删除叶子节点
        if (node.left == null && node.right == null){
            if (node.parent == null){
                root = null;
            }else if(node == node.parent.left){
                node.parent.left = null;
            }else {
                node.parent.right = null;
            }
        }else { //删除度为1的节点
            Node<E> replacement = node.left != null?node.left:node.right;
            replacement.parent = node.parent;
            if (node.parent == null){
                root = replacement;
            }else if (node == node.parent.left){
                node.parent.left = replacement;
            }else {
                node.parent.right = replacement;
            }
        }

    }

    /**
     * 找到后继节点
     */
    public Node<E> successor(Node<E> node){
        if(node == null) return null;
        if (node.right != null){
            Node<E> rightNode = node.right;
            while (rightNode.left != null){
                rightNode = rightNode.left;
            }
            return rightNode;
        }

        while (node.parent != null && node == node.parent.right){
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 是否包含某个元素
     */
    public boolean contains(E element){
        return node(element) != null;
    }

    /**
     * 根据element找到对应节点
     */
    private Node<E> node(E element){
        Node<E> node = root;
        while (node != null){
            int cmp = compare(node.element, element);
            if (cmp<0){
                node = node.right;
            }else if(cmp>0){
                node = node.left;
            }else {
                return node;
            }
        }
        return null;
    }

    private void elementNotNullCheck(E element){
        if (element == null){
            throw new IllegalArgumentException("element must not be null");
        }
    }

    private int compare(E e1,E e2){
        if (comparator != null) return comparator.compare(e1,e2);
        return ((Comparable<E>)e1).compareTo(e2);
    }

    protected static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element,Node<E> parent){
            this.element = element;
            this.parent = parent;
        }
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
//        String parentString = "null";
//        if (myNode.parent != null) {
//            parentString = myNode.parent.element.toString();
//        }
        return myNode.element;// + "_p(" + parentString + ")";
    }
}

打印二叉树工具：https://github.com/CoderMJLee/BinaryTrees

使用步骤：

1. 实现BinaryTreeInfo接口
2. 调用打印API：BinaryTrees.println(bst);

二叉搜索树复杂度分析

二叉搜索树的添加、删除、搜索的时间复杂度和树的高度有关，也就是O(h)

1. 最好情况：二叉搜索树的添加、删除、搜索的时间复杂度都为O(logn)

如果按照7、4、9、2、5、8、11的顺序添加节点，会得到一棵满二叉搜索树，已知满二叉树的h = log2(n+1)，所以当二叉搜索树是一棵满二叉树的时候，二叉搜索树的添加、删除、搜索的时间复杂度都为O(logn)

2. 最坏情况：二叉搜索树退化成链表，添加、删除、搜索的时间复杂度都为O(n)

如果按照从小到大添加节点，二叉搜索树退化成了链表，h = n，二叉搜索树的添加、删除、搜索的时间复杂度都为O(n)