Binary search tree

A binary search tree is defined in such a way that, for any node, all the nodes of its left subtree are less than the value of this node, and all the nodes of its right subtree are greater than the value of this node;

BinarySearchTree full name BinarySearchTree, we referred to as BST in the implementation;

1. Binary search tree Node Node and basic attributes

The Node Node contains element E, and the left and right child nodes are different from the nodes in the list.

The root node attribute represents the root node of the binary search tree.

Size represents the number of binary search tree elements;

The size() function returns the number of binary search tree elements;

IsEmpty () returns whether the binary search tree isEmpty;

public class BST<E extends Comparable<E>> { private class Node{ public E e; public Node left, right; public Node(E e){ this.e = e; left = null; right = null; } } private Node root; private int size; public BST(){ root = null; size = 0; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; },,}Copy the code

2. Add elements to binary search tree

Due to the natural recursive structure of binary search tree nodes, we can use recursion to add elements;

Recursion is generally divided into two steps, recursive termination conditions and recursive procedures, and there are comments in the method;

Because of the nature of binary search tree, when adding an element, if the value of the element is higher than that of the current root node, it is added to the left subtree of the current root node; otherwise, it is added to the right subtree of the current root node.

E public void add(e e){root = add(root, e); } 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

3. Find elements from binary search tree

Again, recursion is used here, recursive termination conditions and recursive procedures;

Like adding elements, when the element is smaller than the current root node, the left subtree is searched. When the search element is larger than the current root node, the search goes to the right subtree; Returns true when the element being searched is equal to the value of the current root node; Return false if recursive terminations are not found;

E public Boolean contains(e e){return contains(root, e); } private Boolean contains(node node, e e){if(node == null) return false; If (e.compareTo(node.e) == 0) return true; else if(e.compareTo(node.e) < 0) return contains(node.left, e); else // e.compareTo(node.e) > 0 return contains(node.right, e); }Copy the code

4, binary search tree before, middle, after and order traversal

We just print the elements in the loop;

The recursive writing method of front, middle and rear order traversal is very simple, just need to operate elements in different positions of left and right subtree recursion;

The sequential traversal of the binary search tree is also very simple to implement with the help of the data structure Queue, as shown below.

Among them, the non-recursive writing method of pre-order traversal with the help of Stack Stack data structure is also very simple;

Public void preOrder(){preOrder(root); } private void preOrder(node node){if(node == null) return; System.out.println(node.e); preOrder(node.left); preOrder(node.right); } public void inOrder(){inOrder(root); } private void inOrder(node node){if(node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } public void postOrder(){postOrder(root); } private void postOrder(node node){if(node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); Public void levelOrder(){Queue<Node> q = new LinkedList<>(); q.add(root); while(! q.isEmpty()){ Node cur = q.remove(); System.out.println(cur.e); if(cur.left ! = null) q.add(cur.left); if(cur.right ! = null) q.add(cur.right); Public void preOrderNR(){Stack<Node> Stack = new Stack<>(); stack.push(root); while(! stack.isEmpty()){ Node cur = stack.pop(); System.out.println(cur.e); if(cur.right ! = null) stack.push(cur.right); if(cur.left ! = null) stack.push(cur.left); }}Copy the code

5. Return the largest and smallest elements in the binary search tree

By virtue of the property of binary search tree, we can find the nodes of the smallest and largest elements by recursion, and then return the smallest and largest elements by the nodes.

Public E minimum(){if(size == 0) throw new IllegalArgumentException("BST is empty!" ); return minimum(root).e; } private node minimum(node node){if(node. Left == null) return node; Return minimum(node.left); } public E maximum(){if(size == 0) throw new IllegalArgumentException("BST is empty"); return maximum(root).e; } private node maximum(node node){if(node.right == null) return node; // return maximum(node.right); }Copy the code

6. Delete nodes from binary search tree

Deleting a node is the most troublesome operation;

It is relatively easy to delete the smallest and largest nodes by recursion;

When a common node is deleted, the left subtree of the node to be deleted is empty, the right subtree of the node to be deleted is empty, and the left and right subtrees of the node to be deleted are not empty. As shown below, there are detailed comments in the code;

Public E removeMin(){E ret = minimum(); root = removeMin(root); return ret; Private node removeMin(node node){if(node. Left == null){node rightNode  = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } public E removeMax(){E ret = maximum(); root = removeMax(root); return ret; } private node removeMax(node node){if(node.right == null){node leftNode  = node.left; node.left = null; size --; return leftNode; } node.right = removeMax(node.right); return node; } public void remove(e e){root = remove(root, e); } // Remove the root of the binary search tree with the value of e. // Return the root of the binary search tree with the value of e. 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 // If (node.left == null){node rightNode = node.right; node.right = null; size --; return rightNode; } // If (node.right == null){node leftNode = node.left; node.left = null; size --; return leftNode; } // If the left and right subtrees of the Node to be deleted are not empty // Find the minimum Node that is bigger than the right subtree of the Node to be deleted // Use this Node to replace the location of the Node to be deleted. successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; }}Copy the code

7. Rewrite toString method to print binary search tree

Because binary search trees are trees, not linear like arrays or linked lists, we print with a little bit of strategy: the deeper the hierarchy, the more nodes in front of it;

@Override public String toString(){ StringBuilder res = new StringBuilder(); generateBSTString(root, 0, res); return res.toString(); } // generate root node, Private void generateBSTString(Node Node, int depth, StringBuilder res){ if(node == null){ res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + node.e +"\n"); generateBSTString(node.left, depth + 1, res); generateBSTString(node.right, depth + 1, res); } private String generateDepthString(int depth){ StringBuilder res = new StringBuilder(); for(int i = 0 ; i < depth ; i ++) res.append("--"); return res.toString(); }Copy the code