Java 数据结构篇-实现二叉搜索树的核心方法

public class BST<Key extends Comparable<Key>, Value> {
 
    private Node root; // 根节点
 
    private class Node {
        private Key key; // 键
        private Value value; // 值
        private Node left, right; // 左右子节点
        private int N; // 以此节点为根的子树中的节点总数
 
        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }
 
    // 获取二叉搜索树中的节点个数
    public int size() {
        return size(root);
    }
 
    // 递归方式获取节点个数
    private int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.N;
        }
    }
 
    // 二叉搜索树的最小键值
    public Key min() {
        return min(root).key;
    }
 
    // 递归方式获取最小键值
    private Node min(Node x) {
        if (x.left == null) {
            return x;
        }
        return min(x.left);
    }
 
    // 二叉搜索树的最大键值
    public Key max() {
        return max(root).key;
    }
 
    // 递归方式获取最大键值
    private Node max(Node x) {
        if (x.right == null) {
            return x;
        }
        return max(x.right);
    }
 
    // 向二叉搜索树中插入键值对
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }
 
    // 递归方式向二叉搜索树中插入键值对
    private Node put(Node x, Key key, Value value) {
        if (x == null) {
            return new Node(key, value, 1);
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else if (cmp > 0) {
            x.right = put(x.right, key, value);
        } else {
            x.value = value;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
 
    // 从二叉搜索树中删除键值
    public void delete(Key key) {
        root = delete(root, key);
    }
 
    // 递归方式从二叉搜索树中删除键值
    private Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = delete(x.left, key);
        } else if (cmp > 0) {
            x.right = delete(x.right, key);
        } else {
            if (x.right == null) {
                return x.left;
            }
            if (x.left == null) {
                return x.right;
            }
            Node t = x;
            x = min(t.right);
            x.rig