Java-Binary Search Tree (BST) algorithm sample code sharing

Binary Search Tree (Binary Search Tree) is an algorithm that combines the flexibility of linked list insertion with the efficiency of ordered array search. The following is the pure code for implementing various methods of BST.

Binary search tree (BST) definition

Binary sorting tree is either an empty tree, or It is a binary tree with the following properties:

1. If the left subtree is not empty, then the values ​​of all nodes on the left subtree are Less than or equal to The value of its root node

2. If the right subtree is not empty, then right subtree The values ​​of all nodes on are greater than or equal to the value of its root node

3. The left and right subtrees are also Respectively for the binary sorting tree

basic node implementation

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

    private Node root;

    private class Node {

        private K key;
        private V value;
        private Node left;
        private Node right;
        private int N;

        public Node(K key, V 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;
    }
}

find the key to get the value—— get

public V get(K key) {
    return get(root, key);
}

private V get(Node root, K key) {

    if (root == null)
        return null;

    int comp = key.compareTo(root.key);

    if (comp == 0)
        return root.value;
    else if (comp < 0)
        return get(root.left, key);
    else
        return get(root.right, key);

}

Modify value/insert new value——put

  public void put(K key, V value) {
        root = put(root, key, value);
    }

    private Node put(Node root, K key, V value) {

        if (root == null)
            return new Node(key, value, 1);

        int comp = key.compareTo(root.key);
        if (comp == 0)
            root.value = value;
        else if (comp < 0)
            root.left = put(root.left, key, value);
        else
            root.right = put(root.right, key, value);

        root.N = size(root.left) + size(root.right) + 1;

        return root;
    }

Maximum value/Minimum value——min/max

  public K min() {
        return min(root).key;
    }

    private Node min(Node root) {

        if (root.left == null)
            return root;

        return min(root.left);

    }

    public K max() {
        return max(root).key;
    }

    private Node max(Node root2) {

        if (root.right == null)
            return root;

        return max(root.right);

    }

Round up/down——floor/ceiling

  public K floor(K key) {
        Node x = floor(root, key);
        if (x == null)
            return null;
        return x.key;
    }

    private Node floor(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp < 0)
            return floor(root.left, key);
        else if (comp > 0 && root.right != null
                && key.compareTo(min(root.right).key) >= 0)
            return floor(root.right, key);
        else
            return root;

    }

    public K ceiling(K key) {
        Node x = ceiling(root, key);
        if (x == null)
            return null;
        return x.key;
    }

    private Node ceiling(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp > 0)
            return ceiling(root.right, key);
        else if (comp < 0 && root.left != null
                && key.compareTo(max(root.left).key) >= 0)
            return ceiling(root.left, key);
        else
            return root;

    }

Select——select

  public K select(int k) {
        //找出BST中序号为k的键
        return select(root, k);
    }

    private K select(Node root, int k) {

        if (root == null)
            return null;

        int comp = k - size(root.left);

        if (comp < 0)
            return select(root.left, k);
        else if (comp > 0)
            return select(root.right, k - (size(root.left) + 1));
        else
            return root.key;

    }

Rank——rank

  public int rank(K key) {
        //找出BST中键为key的序号是多少
        return rank(root, key);
    }

    private int rank(Node root, K key) {

        if (root == null)
            return 0;

        int comp = key.compareTo(root.key);

        if (comp == 0)
            return size(root.left);
        else if (comp < 0)
            return rank(root.left, key);
        else
            return 1 + size(root.left) + rank(root.right, key);

    }

Delete minimum/maximum key——deleteMin/deleteMax

  public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node root) {

        if (root.left == null)
            return root.right;

        root.left = deleteMin(root.left);
        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

    public void deleteMax() {
        root = deleteMax(root);
    }

    private Node deleteMax(Node root) {

        if (root.right == null)
            return root.left;

        root.right = deleteMax(root.right);
        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

Delete any key——delete

  public void delete(K key) {
        root = delete(root, key);
    }

    private Node delete(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp == 0) {

            if (root.right == null)
                return root = root.left;
            if (root.left == null)
                return root = root.right;

            Node t = root;
            root = min(t.right);

            root.left = t.left;
            root.right = deleteMin(t.right);

        } else if (comp < 0)
            root.left = delete(root.left, key);
        else
            root.right = delete(root.right, key);

        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

In-order print tree——print

  public void print() {
        print(root);
    }

    private void print(Node root) {

        if (root == null)
            return;
        print(root.left);
        System.out.println(root.key);
        print(root.right);

    }

The above is the detailed content of Java-Binary Search Tree (BST) algorithm sample code sharing. For more information, please follow other related articles on the PHP Chinese website!