Binary search tree node insertion

First, define a binary search tree, represented in Java code as follows:

public class BST<Key extends Comparable<Key>, Value> {

    // The nodes in the tree are a private class; the outside world does not need to know the specific implementation of the binary search tree nodes
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
    // Root node
    private Node root;
    // Number of nodes in the tree
    private int count;
    // Constructor, constructs an empty binary search tree by default
    public BST() {
        root = null;
        count = 0;
    }
    // Return the number of nodes in the binary search tree
    public int size() {
        return count;
    }
    // Return whether the binary search tree is empty
    public boolean isEmpty() {
        return count == 0;
    }
}

Node represents a node, and count represents the number of nodes.

The following example shows the steps for inserting element 61 into the binary search tree below:

(1) The element to be inserted, 61, is greater than 42; compare the root node of 42's right subtree.

(2) 61 is greater than 59, so 61 needs to be moved to the corresponding position in 59's right subtree. Since it is empty here, insert it directly as 59's right child node.

The insertion operation is also a recursive process, covering three cases: equal, greater than, and less than.

Java example code

Source code package download:Download

src/example/binary/BinarySearchTreeInsert.java file code:

package example.binary;

/**
* Insert a new element into the binary search tree
 */

public class BinarySearchTreeInsert<Key extends Comparable<Key>, Value> {

    // The nodes in the tree are a private class; the outside world does not need to know the specific implementation of the binary search tree nodes
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // Root node
    private int count;  // Number of nodes in the tree

    // Constructor, constructs an empty binary search tree by default
    public BinarySearchTreeInsert() {
        root = null;
        count = 0;
    }

    // Return the number of nodes in the binary search tree
    public int size() {
        return count;
    }

    // Return whether the binary search tree is empty
    public boolean isEmpty() {
        return count == 0;
    }

    // Insert a new (key, value) data pair into the binary search tree
    public void insert(Key key, Value value) {
        root = insert(root, key, value);
    }

    // Core code --- start
    // Insert node (key, value) into the binary search tree rooted at node, using recursive algorithm
    // Return the root of the binary search tree after inserting the new node
    private Node insert(Node node, Key key, Value value) {
        if (node == null) {
            count++;
            return new Node(key, value);
        }
        if (key.compareTo(node.key) == 0)
            node.value = value;
        else if (key.compareTo(node.key) < 0)
            node.left = insert(node.left, key, value);
        else    // key > node->key
            node.right = insert(node.right, key, value);

        return node;
    }
    // Core code --- end
}
other extensions