BST --- Java版

一. 简介

二叉查找树（BST）是二叉树的一个重要的应用，它在二叉树的基础上加上了这样的一个性质：对于树中的每一个节点来说，如果有左儿子的话，它的左儿子的值一定小于它本身的值，如果有右儿子的话，它的右儿子的值一定大于它本身的值。
  我用一句话概括：左 < 中 < 右。 根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。

二. 数据结构

public class BST<T extends Comparable<T>> {
    class Node {
        private T data;
        private Node left;
        private Node right;
        private int N;

        public Node(T data, int N) {
            this.data = data;
            this.N = N;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;

    public int size() {
        return size(root);
    }

    private int size(Node n) {
        if (n == null) return 0;
        else return n.N;
    }

    public void put(T x) {
        root = put(root, x);
    }

    public Node min() {
        return min(root);
    }

    private Node min(Node n) {
        if (n == null)
            return null;
        while (n.left != null) {
            n = n.left;
        }
        return n;
    }

    private Node put(Node n, T x) {
        if (n == null) return new Node(x, 1);  //树为空
        int cmp = x.compareTo(n.data);
        if (cmp < 0) {
            n.left = put(n.left, x);
        } else if (cmp > 0) {
            n.right = put(n.right, x);
        } else n.data = x;
        n.N = 1 + size(n.left) + size(n.right);
        return n;
    }

    public void delete(T x) {
        if (x == null) throw new IllegalArgumentException("called delete() with a null key");
        root = delete(root, x);
    }

    private Node delete(Node n, T x) {
        if (n == null) return null;
        int cmp = x.compareTo(n.data);
        if (cmp < 0) {
            n.left = delete(n.left, x);
        } else if (cmp > 0) {

        } else {  //如果相等,此节点就是要删除的节点
            if (n.left == null)
                return n.right;     // 这里return，相当于把当前节点的直接右节点连到当前节点的父节点
            if (n.right == null)
                return n.left;      // 这里return，相当于把当前节点的直接左节点连到当前节点的父节点
            // 有2个孩子
            Node t = n;
            n = min(t.right);       // t的右子树最小的节点替换这个被删除的节点
            n.right = deleteMin(t.right);
            n.left = t.left;
        }
        n.N = size(n.left) + size(n.right) + 1;
        return n;
    }

    private Node deleteMin(Node n) {
        if (n.left == null) return n.right;
        n.left = deleteMin(n.left);
        n.N = size(n.left) + size(n.right) + 1;
        return n;
    }
}

1. 插入:
     根据二叉查找树的性质，插入一个节点的时候，如果根节点为空，就此节点作为根节点，如果根节点不为空，就要先和根节点比较，如果比根节点的值小，就插入到根节点的左子树中，如果比根节点的值大就插入到根节点的右子树中，如此递归下去，找到插入的位置。重复节点用新值更新。如图1是一个插入的过程。

2. 查找:
     查找的功能和插入差不多一样，按照插入那样的方式递归下去，如果找到了，就返回这个节点的地址，如果没有找到，就返回null。

3.删除:
  1⃣️ 首先先实现删除这个树中最小的元素: Node deleteMin(Node n){}函数.
思路是:

• 一直找节点Node的左子树，直到找到当前节点的左儿子为空(n.left == null,)
• 用找到的这个节点n的右儿子来替代它自己，这个节点n会没有引用被gc掉
• 更新节点数目

2⃣️ 然后删除某个节点:
  如果是叶子节点的话，直接删除就可以了。比如图3，要删除的是C节点，它是叶子节点，那么很简单把它父节点的引用置为null。

  如果只有一个孩子的话，就让它的父亲指向它的儿子，然后删除这个节点。如下图:

删除有两个儿子的节点会比较复杂一些。一般的删除策略是用其右子树最小的数据代替该节点的数据并递归的删除掉右子树中最小数据的节点。因为右子树中数据最小的节点肯定没有左儿子，所以删除的时候容易一些。(比如删除下图的E节点，那么会找到E节点右子树中最小的节点来替代节点E，如图是H节点, 当H代替完E节点，接下来调用deleteMin(E节点)删除H节点)

三. 复杂度

平均复杂度 最坏情况复杂度

• 插入操作 O(logN)   O(N)

• 查询操作 O(logN)   O(N)

• 删除操作 O(logN)   O(N)

如果BST不是平衡的树，如下图退化成list，那么最大复杂度O(N)。如插入有序序列(1, 2, 3, 4, 5)，插入操作完成后的BST如下图：