Data structure ~ basic 2 ~ tree [design of binary tree, binary search tree, AVL tree, B tree and red black tree] ~ binary search tree

 

1, Binary search tree:

❀ features of binary search tree: ● the whole binary search tree is very characteristic. The root is larger than the left subtree and smaller than the right subtree ● the middle order traversal of binary search number is orderly ~ ascending

 

■ it inherits the binary tree and has the function of adding and deleting on its basis:

❀ passing interface of binary search tree: general interface of binary tree + add and delete

 

  ■ addition and deletion of binary search tree:

□ it can be seen from the characteristics of binary search tree that it needs a comparison mechanism.

Design: internally, there is a comparator object attribute [used to receive the comparator object passed in by the user. When the user does not pass in the comparator, the forced conversion is used. Similarly, let the user implement the comparison interface]:

    //Comparison interface
    private int compare(E e1, E e2) {
        // If a comparator is passed in
        if (comparator != null) {
            // Use comparator
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }

//Binary search tree
public class BST<E> extends BT<E> {
    // Comparator object
    private Comparator<E> comparator = null;
    //Construction method
    public BST() {
    };

    public BST(Comparator<E> comparator) {
        this.comparator = comparator;
    }
}

  ■ add interface to binary search tree:

□   Insert (add) node logic: start from the root node, constantly compare [smaller than the root, consider the left subtree, larger than the root, and consider the right subtree until an empty position [for inserting nodes] is found

~~~When inserting, judge whether to add to the left node or the right node]

　　　　// Find the parent node first
        Node<E> parent = root;
        Node<E> node = root;
　　　　// Comparison
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.elmement);
            //Update the parent node of the node to be inserted
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // When it is equal, overwrite it (because if it is a class object for comparison, we generally compare it only with some of its attributes, such as the student class with the same age: the newly transmitted Xiaohong can overwrite Xiaoming)
                node.elmement = element;
                return;
            }
        }
        // node = new Node<E>(element, parent);
        Node<E> newNode = new Node<E>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }

 

  ■ binary search tree deletion interface:

□   Delete node logic: [delete essentially deletes leaf nodes]

● classification:

(1) Nodes with deletion degree of 2: in essence, it deletes its predecessor or follower [position is still on the leaf],

　　   The covering method directly overwrites the value of the precursor or the follower to the value of the node to be deleted, and then deletes the precursor or the follower

　   Precursor or slave node [possibility degree is 1, or possibility degree is 0] (leave it directly to the later case (2, 3) for unified processing).

(2) Delete node with degree 1: the left node or right node with degree 1 is a leaf node. Find the parent node of the deleted node,

Let the parent node point to the left node of the node to be deleted (when the node to be deleted owns the left node) or the right node (when the node to be deleted owns the right node).

(3) Delete leaf node with degree 0: directly make the parent node of the node to be deleted point to null.

　　　　if(node.hasTwoChildren()) {    //Degree 2
            Node<E> s = sucessor(node);
            node.elmement = s.elmement;
            node = s;
        }
        //Here is to start deleting nodes with a degree of 1 or 0
        //First consider when the degree is 1 (Remember to change the parent node)
        //The node to be replaced may be the left node or the right node of the node to be deleted
        Node<E> replaceNode = node.left != null ? node.left : node.right;
        if(replaceNode != null) {    //The degree is 1
            // (Remember to change the parent node)
            replaceNode.parent = node.parent;
            //Consider special cases (root case):
            if(replaceNode.parent == null) {
                root = replaceNode;
            }else if(node == node.parent.left) {    //A degree of 1 is its left child
                node.parent.left = replaceNode;
            }else {
                node.parent.right = replaceNode;
            }
            
        }else {    //The degree is 0
            //Consider special cases (root case):
            if(node.parent == null) {
                root = null;
            }else if(node.parent.left == node) {    //Is the leaf node (is the left leaf)
                node.parent.left = null;
            }else {
                node.parent.right = null;
            }
            
        }