Binary Search Tree

Definition: any left node < root; Any right node > root

 public class Node {
    public E e;
    public Node left;
    public Node right;

    public Node(E e){
        this.e = e;
        left = null;
        right = null; }}Copy the code

Add new elements – recursion

// Insert element e into the binary search tree with node as the root, recursive algorithm
private void add(Node node, E e){
    if(e.equals(node.e))
        return;
    else if(e.compareTo(node.e) < 0 && node.left == null){
        node.left = new Node(e);
        size ++;
        return;
    }
    else if(e.compareTo(node.e) > 0 && node.right == null){
        node.right = new Node(e);
        size ++;
        return;
    }

    if(e.compareTo(node.e) < 0)
        add(node.left, e);
    else //e.compareTo(node.e) > 0
        add(node.right, e);
}

Copy the code

Third, improve

Problems with the above code: e and Node. e have two rounds of comparison and the terminating condition is too bloated

// Insert element e into the binary search tree with node as the root, recursive algorithm
// Returns the root of the binary search tree after inserting the new node
private Node add(Node node, E e){
    if(node == null){
        size ++;
        return new Node(e);
    }

    if(e.compareTo(node.e) < 0)
        node.left = add(node.left, e);
    else if(e.compareTo(node.e) > 0)
        node.right = add(node.right, e);

    return node;
}

Copy the code

Four, binary search tree traversal

The former sequence traversal

First root node, then left node, then right node

private void preOrder(Node node){
    if(node == null)
        return;

    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}

Copy the code
In the sequence traversal
  1. First the left node, then the root node, then the right node
  1. The middle-order traversal of a binary search tree is sequential
private void preOrder(Node node){
    if(node == null)
        return;
    preOrder(node.left);
    System.out.println(node.e);
    preOrder(node.right);
}

Copy the code
Subsequent traversal

First the left node, then the right node, then the root node

private void preOrder(Node node){
    if(node == null)
        return;
    preOrder(node.left);
    preOrder(node.right);
    System.out.println(node.e);
}

Copy the code

Delete any node

  1. Minimum (node.right) = minimum(node.right)
  2. D. light = removeMin(d. light), that is, s and D switch places
  3. S.ft = d.ft -> complement s left
// Returns the node with the minimum value of the binary search tree root node
    private Node minimum(Node node){
        if(node.left == null)
            return node;
        return minimum(node.left);
    }
Copy the code
// Delete the binary search tree root node e node, recursive algorithm
    // Returns the root of the new binary search tree after the node is deleted
    private Node remove(Node node, E e){

        if( node == null )
            return null;

        if( e.compareTo(node.e) < 0 ){
            node.left = remove(node.left , e);
            return node;
        }
        else if(e.compareTo(node.e) > 0 ){
            node.right = remove(node.right, e);
            return node;
        }
        else{   // e.compareTo(node.e) == 0

            // The left subtree of the node to be deleted is empty
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            // The right subtree of the node to be deleted is empty
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            // The left and right subtrees of the node to be deleted are not empty

            // Find the smallest node larger than the node to be deleted, that is, the smallest node in the right subtree of the node to be deleted
            // Replace the node to be deleted with this node
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            returnsuccessor; }}Copy the code