当前位置：网站首页>Basic operation details of binary search tree (BST) (complete code, including test cases)

public class Node {
    public Integer key;
    public Node left;
    public Node right;

    public Node(Integer key) {
        this.key = key;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                '}';
    }
}

Binary search tree class ：

public class BST {
    private Node root;
}

（1）. lookup

1. Method body analysis ：

2. Ideas ：

When searching , If it is smaller than the current node, go to the left , If it is larger than the current node, go to the right , Exit if equal , find null And quit , The specific code is as follows ：

public boolean search(Integer key){
    Node current = this.root;
    while (current != null){
        int cmp = key.compareTo(current.key);
        if (cmp == 0){
            return true;
        }else if (cmp < 0){
            current = current.left;
        }else {
            current = current.right;
        }
    }
    return false;
}

（2）. Insert

If an object is needed in a method , Then this method must be non static .

1. Method body analysis ：

2. Code thinking ：

Similar to finding , Set a parent node , Maintaining it has always been cur The parent node of , then cur Look down , If we find equal nodes , Throw an exception ; Empty found , You can insert （ According to cmp Decide whether to insert it to the left or the right ）, The specific code is as follows ：

public void insert(Integer key) {
    if (root == null) {
        root = new Node(key);
        return;
    }

    //  Always keep  parent  Namely  current  The parent node of 
    Node parent = null;
    Node current = root;

    int cmp = 0;
    while (current != null) {
        cmp = key.compareTo(current.key);
        if (cmp == 0) {
            throw new RuntimeException("BST  The same... Is not allowed in  key");
        } else if (cmp < 0) {
            parent = current;
            current = current.left;
        } else {
            parent = current;
            current = current.right;
        }
    }

    // current  A certain  null.
    // parent  Is the parent node to insert the new node 
    Node node = new Node(key);
    if (cmp < 0) {
        parent.left = node;
    } else {
        parent.right = node;
    }
}

（3）. Delete

1. analysis

2. Code thinking

1）. Find contains key The node of , Write it down as node.node The parent node of is marked as parent

2）. Judge

Situation 1 ：node.left == null && node.right == null

Situation two ：node.left != null && node.right == null

Situation three ： Similar to case 2

Situation four ： Substitution method （ Select the largest node in the left subtree （ Node right == null, Write it down as ghost））

node Is the node to be deleted ,ghost Is the largest node in the left subtree

The specific code is as follows ：

public boolean remove(Integer key) {
    // 1.  Find the to delete  key  The node , Write it down as  node.node  The parent node of , Write it down as  parent
    Node parent = null;
    Node current = root;

    while (current != null) {
        int cmp = key.compareTo(current.key);
        if (cmp == 0) {
            removeInternal(current, parent);
            return true;
        } else if (cmp < 0) {
            parent = current;
            current = current.left;
        } else {
            parent = current;
            current = current.right;
        }
    }

    return false;
}

private void removeInternal(Node node, Node parent) {
    if (node.left == null && node.right == null) {
        if (node == root) {
            root = null;
        } else if (node == parent.left) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    } else if (node.left != null && node.right == null) {
        if (node == root) {
            root = node.left;
        } else if (node == parent.left) {
            parent.left = node.left;
        } else {
            parent.right = node.left;
        }
    } else if (node.left == null && node.right != null) {
        if (node == root) {
            root = node.right;
        } else if (node == parent.left) {
            parent.left = node.right;
        } else {
            parent.right = node.right;
        }
    } else {
        //  Use the substitution method to delete , Use  node  The node where the maximum value is located in the left subtree of , Write it down as  ghost.ghost  My parents wrote  ghostParent
        Node ghostParent = node;
        Node ghost = node.left;
        //  Look all the way to the right , until  ghost.right == null
        while (ghost.right != null) {
            ghostParent = ghost;
            ghost = ghost.right;
        }

        // there ghost There must be no right subtree 
        // 1.  Replace 
        node.key = ghost.key;
        // 2.  Delete  ghost  node （ The right child must be  null)
        if (node == ghostParent) {
            // The deleted point is the parent of the largest point of the left subtree , This is the only case ,ghost It is possible to ghostParent The left subtree 
            // This situation is node My left child has no right child 
            ghostParent.left = ghost.left;
        } else {
            // otherwise ,ghost It must be ghostParent Right subtree 
            // This situation is node My right child has no left child 
            ghostParent.right = ghost.left;
        }
    }
}