1 the concept

  1. A binary search tree is a binary tree where any node whose value is greater than the left subtree and all nodes whose value is less than the right subtree are binary search trees
  2. Binary search tree can greatly improve the efficiency of data retrieval

The method of designing binary search trees is inherited from binary tree classes

public class BST<E> extends BinaryTree<E> {

    // The first is the new node method
    // This is a comparator. This is how you determine the position of a node in the tree
    private Comparator<E> comparator;
	
	public BST() {
		this(null);
	}
	
	public BST(Comparator<E> comparator) {
		this.comparator = comparator;
	}
            
        // Start from the root node to find the node location
	public void add(E element) {
		elementNotNullCheck(element);
		
		// Add the first node
		if (root == null) {
			root = createNode(element, null);
			size++;

			// Processing after the new node is added
			afterAdd(root);
			return;
		}
		
		// Add not the first node
		// Find the parent node
		Node<E> parent = root;
		Node<E> node = root;
		int cmp = 0;
		do {
			cmp = compare(element, node.element);
			parent = node;
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {
				node = node.left;
			} else { / / equal
				node.element = element;
				return; }}while(node ! =null);

		// see where the parent node is inserted
		Node<E> newNode = createNode(element, parent);
		if (cmp > 0) {
			parent.right = newNode;
		} else {
			parent.left = newNode;
		}
		size++;
		
		// Processing after the new node is added
		afterAdd(newNode);
	}
        
        /** * Adjustments after adding Node *@param Node newly added nodes are implemented by subclasses */
	protected void afterAdd(Node<E> node){}/** * Adjustments after node removal *@param Node The deleted node or the child node that replaces the deleted node (when the degree of the deleted node is 1) */
	protected void afterRemove(Node<E> node) { }
        
        private Node<E> node(E element) {
		Node<E> node = root;
		while(node ! =null) {
			int cmp = compare(element, node.element);
			if (cmp == 0) return node;
			if (cmp > 0) {
				node = node.right;
			} else { // cmp < 0node = node.left; }}return null;
	}

	public void remove(E element) {
		remove(node(element));
	}

	public boolean contains(E element) {
		returnnode(element) ! =null;
	}
	//
        // There are three ways to delete a node whose degree is 2: delete the precursor or the successor
        // A node with a degree of 1 deletes its right or left node
        // Delete the node whose degree is 0 directly
	private void remove(Node<E> node) {
		if (node == null) return;
		
		size--;
		
		if (node.hasTwoChildren()) { // Node with degree 2
			// Find the successor node
			Node<E> s = successor(node);
			// Use the value of the node whose coverage is 2 as the value of the subsequent node
			node.element = s.element;
			// Delete subsequent nodes
			node = s;
		}
		
		// Delete node node (node degree must be 1 or 0)Node<E> replacement = node.left ! =null ? node.left : node.right;
		
		if(replacement ! =null) { // node is a node of degree 1
			/ / change the parent
			replacement.parent = node.parent;
			// Change the left and right directions of the parent
			if (node.parent == null) { // node is a node of degree 1 and is the root node
				root = replacement;
			} else if (node == node.parent.left) {
				node.parent.left = replacement;
			} else { // node == node.parent.right
				node.parent.right = replacement;
			}
			
			// Process after node deletion
			afterRemove(replacement);
		} else if (node.parent == null) { // Node is a leaf node and a root node
			root = null;
			
			// Process after node deletion
			afterRemove(node);
		} else { // Node is a leaf node, but not a root node
			if (node == node.parent.left) {
				node.parent.left = null;
			} else { // node == node.parent.right
				node.parent.right = null;
			}
			
			// Process after node deletionafterRemove(node); }}/ * * *@return The return value is 0, indicating that E1 and E2 are equal; If the return value is greater than 0, E1 is greater than E2. If the return value is less than 0, e1 is less than e2 */
	private int compare(E e1, E e2) {
		if(comparator ! =null) {
			return comparator.compare(e1, e2);
		}
		return ((Comparable<E>)e1).compareTo(e2);
	}
	
	private void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not be null"); }}}Copy the code