Binary tree and binary search tree

This paper will start with the definition and nature of binary tree and binary search tree, and realize deep understanding of binary search tree through code.

What is a binary tree?

In our real scene, such as the library, we can quickly find the books we want according to the classification. For example, if we want to find a book called “Java Programming Ideas”, we just need to partition science and engineering > Computers >Java language to quickly find the book we want. So we don’t have to do something like an array or a linked list, we have to go through it to find what we want. For example, we use the computer folder directory itself is a tree structure.

From the above description, we can see that the tree structure is naturally efficient and can skillfully avoid things we don’t care about, just need to follow our clues to quickly locate our target. So trees represent a kind of efficiency.

Binary tree definition

Binary tree is also a dynamic data structure. Each node has only two forks, or two children, called the left child and the right child, and a node without a child is called a leaf node. Each node can have up to one father node and up to two children (it can have no children nodes or only one child node).

Consists of a node, each node has a maximum of two child nodes (left and right child nodes have no size)
There is one and only one root node
Each subtree is also a binary tree

Basically, a binary tree looks like this:

Then each of these nodes, described in Java code, looks something like this:

class Node<E>{
  E e;
  Node left;
  Node right;
}
Copy the code

Where E is a generic type that represents the type of the element that our node stores; And then we use the field e to store the element. Where left and right are used to store our left and right child nodes.

Note:

A variable with a value of null can also be considered a binary tree.
A linked list is a special kind of binary tree.
A binary tree might be very “average”, with all the nodes to the left of each node as many as all the nodes to the right; It could be malformed, like a linked list.
Binary trees have natural recursive rows.

The type of the binary tree

According to the node distribution of binary tree, it can be roughly divided into the following three kinds of binary tree: complete binary tree, full binary tree and balanced binary tree.

Full binary tree: The same number of nodes passes from the root node to each leaf node.

Complete binomial tree: a complete binomial tree is a tree with the last layer of nodes removed, and the last layer of nodes can only be concentrated on the left.

Balanced binary tree: Balanced binary tree, also known as AVL tree (different from AVL algorithm), is a binary tree and a binary search tree. The absolute value of the height difference between the left and right subtrees of any node of a balanced binary tree is not more than 1, that is, both the left and right subtrees are a balanced binary tree.

What is a binary search tree?

First of all, it is a binary tree, which satisfies all the rules and properties of binary trees mentioned above.
For each node: its value is greater than the value of any node in the left subtree and less than the value of any node in the right subtree;
The stored elements must be comparable;

A binary search tree looks something like this:

Or it could be something like this:

In short, a binary tree that satisfies the above rule is a binary search tree.

Binary search tree implementation

In this paper, we focus on the implementation of a binary search tree, then we stipulate that the binary search tree should have the following functions: using a generic and requiring that the generic must achieve Comparable interface; Basic add, delete, modify and check operation.

The basic structure

From the above analysis, we know that if we want to implement a binary search tree, we need our node to have left and right child nodes.

/** * Binary search tree - The data stored must be Comparable, so generics must inherit the Comparable interface **/
public class BinarySearchTree<E extends Comparable<E>> {
	/** * Binary search tree node structure */
    private class Node {
        E e;
        Node left, right;

        public Node(a) {
            this(null.null.null);
        }

        public Node(E e) {
            this(e, null.null);
        }

        public Node(E e, Node left, Node right) {
            this.e = e;
            this.left = left;
            this.right = right; }}/** * Root node */
    private Node root;
    /** * indicates the number of elements stored in the tree */
    private int size;
    /** * Get the number of elements in the tree *@returnNumber of elements */
    public int size(a) {
        return size;
    }
    /** whether the tree is empty *@returnReturns true if empty, false otherwise */
    public boolean isEmpty(a) {
        return size == 0; }}Copy the code

Add elements

Before inserting elements, we need to make it clear whether we are allowed to have duplicate elements in the binary search tree (if there are duplicate elements, just change the definition to: the left subtree is less than or equal to the node; Or the right subtree is greater than or equal to the node). I’m just going to do it in the case of not allowing duplicate elements. If a duplicate element is found during the insert, we abandon the insert.

Based on the binary search tree below, suppose we want to insert the element 31 into the node. So we’re going to go through the root one layer at a time to 32. We find that 31 is less than 32, and the left subtree of 32 is null, so we should just insert 31 into the left node of 32.

A binary search tree is a non-recursive way of adding elements, much like a linked list, except you don’t have to compare them to the nodes in the list, whereas a tree has to compare them to decide whether to add them to the left subtree or the right subtree.

The specific implementation code is as follows:

/** add a new element e ** to the binary search tree@paramE new element */
public void add(E e) {
    if (root == null) {
        // The root node is empty
        root = new Node(e);
        size++;
    } else{ add(root, e); }}/** * insert element e into binary search tree with root node@param node
 * @param e
 */
private void add(Node node, E e) {
    // The terminating condition of recursion
    if (e.equals(node.e)) {
        // Do not store duplicate elements
        return;
    } else if (e.compareTo(node.e) < 0 && node.left == null) {
        // Element e is smaller than the element of node, and the left child of node is empty, so it becomes the left child of node
        node.left = new Node(e);
        size++;
        return;
    } else if (e.compareTo(node.e) > 0 && node.right == null) {
        // Element e is greater than the element of node, and the right child of node is null, so it becomes the right child of node
        node.right = new Node(e);
        size++;
        return;
    }

    if (e.compareTo(node.e) < 0) {
        // If e is smaller than node, go to the left subtree
        add(node.left, e);
    } else {
        // If e is greater than node, go to the right subtreeadd(node.right, e); }}Copy the code

Improved add operations: insight into recursive termination conditions

The above implementation of adding elements to binary trees is fine, but there is room for optimization. First, in the add(E E) method, the root node is nullated, which is not consistent with the latter method logically. In fact, it can be put in the latter method for unified processing. Second, the termination condition of recursion in add(Node Node, E E) method is bloated and can be simplified.

The optimized implementation code is as follows:

/** add a new element e ** to the binary search tree@paramE new element */
public void add2(E e) {
    root = add2(root, e);
}

/** * insert element e into binary search tree with node as root **@param node
 * @param e
 * @returnReturns the root node */ of the binary search tree after the new node is inserted
private Node add2(Node node, E e) {
    // The terminating condition of recursion
    if (node == null) {
        // If node is empty, you can insert a new node
        size++;
        return new Node(e);
    }

    if (e.compareTo(node.e) < 0) {
        // If e is smaller than node, go to the left subtree
        node.left = add2(node.left, e);
    } else if (e.compareTo(node.e) > 0) {
        // If e is greater than node, go to the right subtree
        node.right = add2(node.right, e);
    }
    
    // Equal to do nothing
    return node;
}
Copy the code

After modifying the termination condition of recursion, we only need to insert new nodes when the nodes are empty, and we do not need to determine whether the left and right child nodes are empty. By selecting the right termination condition, you have one more layer of recursion but less unnecessary code

Look for the element

The core competitiveness of binary search tree is to be able to use binary search to query elements. If we want to query the existence of a certain value in a binary search tree, we only need to start from the root node:

If the value of the root node is the value we are looking for, we simply return that node;
If the child of the root node is larger than the value of our target node, we recursively search the left subtree;
If the child of the root node is smaller than the value of our target node, we recursively search the right subtree;

Basic Query Operations

Suppose we want to find the existence of a node with a value of 32 in this binary search tree

First, we check the root node and find that the value of the root node is 41, which is greater than our target value. Then we can directly exclude all the nodes to the right of the root node according to the properties of the binary search tree, and the target value can only exist on the left of the root node.
And then we go to the left node of 41, which is the node 20. We find that the value of this node is less than 32, and all target values are only possible to the right of 20. So we’re at node 29.
We did the same thing with 29, and now we’re at 32.

/** * Check whether the binary search tree contains the element e */
public boolean contains(E e) {
    return contains(root, e);
}

/** * check whether the binary search tree with node as root contains element e, and recurse to */
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) {
	    // Find the left subtree
        return contains(node.left, e);
    }
    
    // Find the right subtree
    return contains(node.right, e);
}
Copy the code

What is a traversal operation?

The traversal operation is to access all nodes so that all node elements can be operated on. In a linear structure, traversal is extremely easy, and one loop is solved. But in a tree, it’s a little bit tricky, because in order to walk through the tree, you have to take care of both subtrees

Binomial tree traversal mainly has such a few kinds: preorder traversal, in order traversal, after order traversal and sequence traversal.

The former sequence traversal

Preorder traversal, so called preorder traversal first through the root node, then through the left subtree and the right subtree. Preorder traversal is the most natural and common traversal.

Preorder traversal is very simple to implement using recursion, as follows:

/** * Preorder traversal of binary search tree */
public void preOrder(a) {
    preOrder(root);
}

/** * Traverse the binary search tree with node as the root
private void preOrder(Node node) {
    if (node == null) {
        return;
    }

    // First traverse the root node
    System.out.println(node.e);

    // Then the left subtree and the right subtree are traversed
    preOrder(node.left);
    preOrder(node.right);
}
Copy the code

In the sequence traversal

In order traversal is first traversed the left subtree, then traversed the root node, and then traversed the right subtree.

The specific implementation code is as follows:

/** * Binary search tree in order traversal */
public void inOrder(a) {
    inOrder(root);
}

/** * in order to traverse the binary search tree root node, recursive implementation */
private void inOrder(Node node) {
    if (node == null) {
        return;
    }

    // First traverse the left subtree
    inOrder(node.left);
    // Then iterate over the root node
    System.out.println(node.e);
    // The right subtree is traversed last
    inOrder(node.right);
}
Copy the code

The in-order traversal feature of binary search tree is that nodes can be accessed in order from the smallest element to the largest element. When the traversal process is output, you can see that it is ordered.

After the sequence traversal

In the same way, the sequential traversal changes the order, first traversing the left subtree, then traversing the right subtree, then traversing the root node.

The specific implementation code is as follows:

/** * Binary search tree after order traversal */
public void postOrder(a) {
    postOrder(root);
}

/** * Traverse the binary search tree with node as the root. */
private void postOrder(Node node) {
    if (node == null) {
        return;
    }

    // First traverse the left subtree
    postOrder(node.left);
    // Then the right subtree is traversed
    postOrder(node.right);
    // Iterate over the root node last
    System.out.println(node.e);
}
Copy the code

Post-order traversal is usually used in scenarios where the left and right subtrees need to be processed first and the root node finally, such as freeing memory for a binary search tree (C++).

Sequential traversal of a binary search tree

Now that we know about sequential traversal, let’s look at sequential traversal of binary search trees. The so-called sequence traversal is in accordance with the tree hierarchy from the root node from the top down, usually the root node is called level 0 or level 1, I used to call the first level here. As shown in the figure below:

When traversing layer 1, the 28 root node is accessed; When traversing layer 2, nodes 16 and 30 are accessed. When traversing layer 3, nodes 13, 22, 29, and 42 are accessed.

As you can see, sequential traversal is not the same as sequential traversal, in which you walk through one of the subtrees first, and then come back and walk through the other subtree, which is called depth-first traversal, while sequential traversal is called breadth-first traversal.

Usually sequential traversal uses a non-recursive implementation and is assisted by a queue container, so the code is written very similar to the previous non-recursive implementation of sequential traversal, except that the container is a queue instead of a stack. Concrete code implementation is as follows:

/** * Binary search tree sequence traversal implementation */
public void levelOrder(a) {
    Queue<Node> queue = new LinkedList<>();
    // The root node joins the queue
    queue.add(root);
    while(! queue.isEmpty()) {// Dequeue the node currently to be accessed
        Node cur = queue.remove();
        System.out.println(cur.e);

        // The left and right nodes join the queue
        if(cur.left ! =null) {
            queue.add(cur.left);
        }
        if(cur.right ! =null) { queue.add(cur.right); }}}Copy the code

Using the tree above as an example, let’s also analyze the execution of the lower-order traversal code:

First squad of the root node Into the circulation, the first element of the team, the output of 28 out of favour with the current element left node is not null, 16 team will left node Out of favour with the current element node is empty, no right to 30 team right node This queue is empty, not continue to cycle, header element out of the team, 16 output (fifo) left out of favour with the current element node is not null, Put left node 13 in the queue and the right node of the current outgoing element is not empty, put right node 22 in the queue and continue the loop, the head element is out of the queue, output 30 The left node of the current outgoing element is not empty, put left node 29 in the queue and the right node of the current outgoing element is not empty, put right node 42 in the queue and continue the loop, the head element is out of the queue, Output 13 the left node of the current outgoing element is empty, do nothing. The right node of the current outgoing element is empty, do nothing to continue the loop, the head element out of the queue, output 22 repeat step 12 and 13 to continue the loop, the head element out of the queue, output 29 repeat step 12 and 13 to continue the loop, the head element out of the queue, Output 42 repeat step 12 and 13 when there are no more elements in the stack, empty, break out of the loop and the final output is: 28, 16, 30, 13, 22, 29, 42Copy the code

Significance of breadth-first traversal:

Find the solution to the problem faster
Often used in algorithm design: shortest path

Preorder traversal non-recursive implementation

Although using recursion to achieve the tree traversal is relatively simple, but usually in the actual development will not use recursion too much, one is afraid of the large amount of data recursion depth will lead to stack overflow, the other is to reduce the cost of recursive function call. In the non-recursive implementation of order traversal and post-order traversal, the practical application is not wide, so this section mainly implements the non-recursive implementation of order traversal.

Pre-order traversal of the non-recursive implementation of the train of thought there are several, here mainly introduces a recursive algorithm to non-recursive implementation of the more general ideas. With this idea in mind, we can also apply it to other scenarios where recursion passes to non-recursive implementations by emulating the system stack ourselves with additional containers. Concrete code implementation is as follows:

/** * Binary search tree non-recursive preorder traversal implementation */
public void preOrderNR(a) {
    // Use java.util.Stack to simulate the system Stack
    Stack<Node> stack = new Stack<>();
    // Preorder traversal so push the root node on the stack first
    stack.push(root);
    while(! stack.isEmpty()) {// Offstack the node that is currently being accessed
        Node cur = stack.pop();
        System.out.println(cur.e);

        if(cur.right ! =null) {
            // Since the stack is last in first out, the right subtree is pushed first
            stack.push(cur.right);
        }
        if(cur.left ! =null) { stack.push(cur.left); }}}Copy the code

Using such a tree as an example, let’s briefly describe the execution of the above code:

First, the root node 28 is pushed into the loop, the top element of the stack is pushed out, output 28 the right node of the current element out of the stack is not empty, push the right node 30 into the stack, the left node of the current element out of the stack is not empty, push the left node 16 into the stack, the stack is not empty, continue the loop, the top element out of the stack, 16 (lifo) output current stack elements right node is not null, to press the right node 22 into the stack The current stack elements left node is not null, to press the left 13 nodes into the stack Elements continue to cycle, stack stack, output current 13 out of stack elements right node is empty, do nothing out of the current stack elements left node is empty, Do nothing to continue the loop, the top element out of the stack, output 22 repeat steps 9 and 10 to continue the loop, the top element out of the stack, output 30 The right node of the current element out of the stack is not empty, push the right node 42 into the stack, push the left node of the current element out of the stack is not empty, push the left node 29 into the stack, continue the loop, the top element out of the stack, Output 29 repeat step 9 and 10 to continue the loop, the top element out of the stack, output 42 repeat step 9 and 10 at this time there is no element in the stack, empty, break out of the loop the final output is: 28 16 13 22 30 29 42Copy the code

Remove elements

Remove the largest and smallest element

The operation of deleting binary search tree is relatively complicated, so we first solve a relatively simple task, that is, deleting the largest element and the smallest element in binary search tree. Because of the nature of binary search trees, the minimum value is the leftmost node and the maximum element is the rightmost node.

Take the following binary search tree for example. If you look at the leftmost and rightmost nodes, you know that the smallest element is 13 and the largest element is 42:

In the following binary search tree, if you go to the left, you can only go to 16 nodes, and if you go to the right, you can only go to 30 nodes, so the largest and smallest elements are not necessarily leaves:

In this case, when the maximum and minimum elements are deleted, there are subtrees that need to be mounted on the node being deleted

Let’s first look at how to find the maximum and minimum elements of a binary search tree. The code is as follows:

/** * Get the smallest element of the binary search tree */
public E minimum(a) {
    if (size == 0) {
        throw new IllegalArgumentException("BST is empty!");
    }

    return minimum(root).e;
}

/** * Return the node where the smallest element of the binary search tree is located */
private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }

    return minimum(node.left);
}

/** * Get the largest element in the binary search tree */
public E maximum(a) {
    if (size == 0) {
        throw new IllegalArgumentException("BST is empty!");
    }
    return maximum(root).e;
}

/** * Return the node where the largest element of the binary search tree is located */
private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }

    return maximum(node.right);
}
Copy the code

Then to achieve the deletion operation, the code is as follows:

/** * Remove the node where the largest element in the binary search tree is located and return that element */
public E removeMax(a) {
    E ret = maximum();
    root = removeMax(root);
    return ret;
}

/** * Return the root of the new binary search tree */
private Node removeMax(Node node) {
    if (node.right == null) {
        // If there is a left subtree, it needs to be hung on the node to be deleted
        Node leftNode = node.left;
        node.left = null;
        size--;

        return leftNode;
    }

    node.right = removeMax(node.right);
    return node;
}

/** * Remove the node where the smallest element in the binary search tree is located and return that element */
public E removeMin(a) {
    E ret = minimum();
    root = removeMin(root);
    return ret;
}

/** * Return the root of the new binary search tree */
private Node removeMin(Node node) {
    if (node.left == null) {
        // If there is a right subtree, you need to hang it on the node to be deleted
        Node rightNode = node.right;
        node.right = null;
        size--;

        return rightNode;
    }

    node.left = removeMin(node.left);
    return node;
}
Copy the code

Delete any element

With the above foundation, you should have a certain idea of how to delete any element of the binary search tree. First, let’s look at some of the situations we’ll encounter during implementation,

In the first case, the target node to be deleted has only one left subtree, such as 58 in the following figure:

In this case, you simply hang the left subtree on the target node to be deleted, similar to the basic logic for deleting the largest element

The second case is the opposite of the first case, where the target node to be deleted has only one right subtree:

Similarly, just hang the right subtree on the target node to be deleted, similar to the basic logic for deleting the smallest element

In the third case, the target node to be deleted is a leaf node. In this case, the processing logic of any of the above cases can be directly reused, because we can also regard a leaf node as having a left subtree or a right subtree, but it is empty.

The fourth case is more complicated, that is, the target node to be deleted has two child nodes, as shown in the figure below:

In this case, we need to fuse the left and right subtrees under the node 58 together, and then the Hibbard Deletion method proposed by Hibbard in 1962 can be used to solve this problem.

First, the node we’re going to delete is called ddThe first step is ddFind the smallest node s in the right subtree ofs, the ssIt is ddIs the successor to. The second step is a simple onesRemove from the original tree and remove ssThe right subtree of s points to the deleted right subtree, and then puts ssThe left subtree of theta points to DdThe left subtree of theta, and finally let ddThe parent of s points to ssAt this point, the target node D is completeddIs deleted. The diagram below:

The specific implementation code is as follows:

/** * Remove e from binary search tree */
public void remove(E e) {
    root = remove(root, e);
}

/** * return the root of the new binary search tree */
private Node remove(Node node, E e) {
    if (node == null) {
        return null;
    }

    if (e.compareTo(node.e) < 0) {
        // The node to be deleted is in the left subtree
        node.left = remove(node.left, e);
        return node;
    } else if (e.compareTo(node.e) > 0) {
        // The node to be deleted is in the right subtree
        node.right = remove(node.right, e);
        return node;
    }

    // The node to delete is found
    // The left subtree of the node to be deleted is empty
    if (node.left == null) {
        // If there is a right subtree, you need to hang it on the node to be deleted
        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) {
        // If there is a left subtree, it needs to be hung on the node to be deleted
        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
    Node successor = minimum(node.right);
    // Replace the node to be deleted with this node
    // Since the size has already been maintained once in removeMin, there is no need to maintain the size once
    successor.right = removeMin(node.right);
    successor.left = node.left;
    return successor;
}
Copy the code

What is a binary tree?

Binary tree definition

The type of the binary tree

What is a binary search tree?

Binary search tree implementation

The basic structure

Add elements

Improved add operations: insight into recursive termination conditions

Look for the element

Basic Query Operations

The former sequence traversal

In the sequence traversal

After the sequence traversal

Sequential traversal of a binary search tree

Preorder traversal non-recursive implementation

Remove elements

Remove the largest and smallest element

Delete any element

Related Posts

MySQL database: Chapter 10: Paging query

Still feel Linux command difficult, look at this 2W Linux command details, easy to understand

K8s install mongodb(NFS persistence)