“This is my 8th day of the November Gwen Challenge.The final text challenge in 2021”

Abstract

If you have n elements in a linear table, the time is O(n). If binary search is used, the time complexity can be reduced to O(logn), but the average time complexity for additions and deletions is O(n).

Using binary search trees, the worst time complexity of add, delete, and search can be optimized to O(logn).

Binary Search Tree (BST) It is a kind of binary tree, the application of the scene is also very wide, other places also called binary search tree, binary sort tree. The main features are:

  • The value of any node is greater than the value of all nodes in its left subtree
  • The value of any node is less than the value of all nodes in its right subtree
  • Its left and right subtrees are also binary search trees
List 1: binary search tree

Binary search tree can greatly improve the search efficiency, but the elements stored in the node must be comparable, otherwise the search efficiency is impossible to talk about.

comparability

You can compare sizes, like ints and doubles. You can also define your own comparison rules here.

But NULL is not comparable, that is, elements must not be NULL.

Design of the interface

Before implementing the binary search tree function, define the interface of the binary search tree. The external interface is as follows:

  1. Number of elements

    int size()
Copy the code

  2. Whether is empty

    boolean isEmpty()
Copy the code

  3. Clear all elements

    void clear()
Copy the code

  4. Add elements

    void add(E element)
Copy the code

  5. Remove elements

    void remove(E element)
Copy the code

  6. Whether an element is contained

    boolean contains(E element)
Copy the code

implementation

Create a class with size to record the number of nodes. Create a root node as the root node of the binary tree. The root node acts as the entry point of the binary tree.

Public class BinarySearchTree<E> implements BinaryTreeInfo {// The number of recorded nodes int size = 0; // Root directory Node<E> root; }Copy the code

Node is the definition of a Node. If you are interested, check out the previous installments.

Size (), isEmpty(), and clear() can be implemented quickly with size and root:

int size() { return size; } boolean isEmpty() { return size == 0; } void clear() { root = null; size = 0; // size must be empty}Copy the code

Add elements

To add an element is to create a node containing the element and place it in the appropriate position, such as adding 12 and 5 to the original binary search tree. The result is:

List2: Add elements 5 and 12

How does 5 get to the left subtree of 6 by adding 5:

  1. The root node is 8 (not null), 5 and 8 are compared, the result is less than 8, run to the left subtree of 8;
  2. The left subtree of 8 is 7 (not null). If 5 is less than 7, run to the left subtree of 7.
  3. The left subtree of 7 is 4 (not null). If the result of 5 is greater than 4, run to the right subtree of 4.
  4. The right subtree of 4 is 6 (not null). If 5 is less than 6, run to the left subtree of 6.
  5. 6 is the parent node of 5.
  6. Because 5 is less than 6, 5 is going to be in the left subtree of 6.

It is concluded that the step of adding is to find the parent node first, and then decide to put it in the corresponding position according to the comparison result with the parent node. In comparison, it doesn’t seem to say what if the elements are equal? The simple and straightforward thing to do here is just overwrite the original element, done.

Code implementation:

Void add(E element) {// Element cannot be null. elementNotNullCheck(element); If (root == null) {root = new Node<E>(element, null); size ++; return; } // add to other location Node<E> Node = root; Node<E> parent = null; int cmp = 0; while (node ! = null) { parent = node; cmp = compare(element, node.element); if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else {node.element = element; return; <E> newNode = newNode <>(element, parent); if (cmp > 0) { parent.right = newNode; } else if (cmp < 0) { parent.left = newNode; } else { } }Copy the code

Compare is a custom comparison method. If you’re interested, look at the last sidebar.

Whether an element is contained

The compare method can be used to get nodes based on the contents of the element:

public Node<E> node(E element) { if (element == null) { return null; } Node<E> node = root; while (node ! = null) { int cmp = compare(element, node.element); if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { return node; } } return null; }Copy the code

If an element is included or not, it can be converted to determine whether the node obtained by the element is null:

boolean contains(E element) { return node(element) ! = null; }Copy the code

Remove elements

Deletion of elements can also be converted to deletion of nodes. There are three cases to be considered in the deletion of nodes in binary search trees:

  1. Nodes are leaf nodes
  2. Nodes are nodes of degree 1
  3. Nodes are nodes of degree 2

What is the degree?

Degree is the number of neutron nodes in a node. The degree of each node in a binary tree ranges from 0 to 2.

A leaf node is a node with degree zero

Nodes are leaf nodes

If the node to be deleted is a leaf node, it is relatively simple to set the leaf node to NULL. We only need to consider the case where the node is the root node, in which case root = null is handled.

Nodes are nodes of degree 1

If the node to be deleted is a node of degree 1, its place can be replaced by a child of that node. Also consider that if this node is the root node, then you need to point root to its children.

List3: Delete elements 4 and 13

A node of degree 2

If the node to be deleted is a node with degree 2, it is necessary to find the precursor or successor node of this node, overwrite this node, and then delete and delete the corresponding precursor or successor. (Precursor or successor, look at the bottom supplement)

This is done to preserve the property that the left subtrees of a node are smaller than the node and the right subtrees of a node are larger than the node.

List4: Delete element 8 with degree 2

implementation

After sorting out the three cases of node deletion, it can be seen that the node with degree 2 is returned to the case with degree 0 or 1 again after replacing its precursor or successor. The next processing is to determine whether it is the root node at the end, so the code implementation can logically process the node with degree 2 first. Then the node with degree 0 or 1 is processed, and finally determine whether the node is root node.

void remove(Node<E> node) { if (node == null) { return; } size --; If (node.ishavetowchildren ()) {// Find the succeeded (node <E> s = node); // Assign the value of the succeeding node to node node.element = s.lement; // node = s; // node = s; } // Node<E> replaceNode = node.left! = null ? node.left : node.right; // if (replaceNode! = null) { replaceNode.parent = node.parent; // root node if (node.parent == null) {root = replaceNode; } else if (node == node.parent.left) { node.parent.left = replaceNode; } else { node.parent.right = replaceNode; }} else if (node. Parent == null) {// node with degree 0 and root root = null; If (node == node.parent. Left) {node.parent. Left = null; } else { node.parent.right = null; }}}Copy the code

supplement

comparemethods

Using the JAVA system’s Comparator class, create the object first and set type E to ensure that data of type E complies with the comparison protocol:

private Comparator<E> comparator;
Copy the code

Then implement the comparison method:

private int compare(E e1, E e2) {
  if (comparator == null) {
    return ((Comparable<E>)e1).compareTo(e2);
  }
  return comparator.compare(e1, e2);
}
Copy the code

Precursor and successor nodes

The precursor node is the previous node in the middle order traversal, and also the previous node smaller than it in the binary search tree.

Is the node. Left. Right. Right… , but when node.left == null, is the parent node of Node (e.g. element 4 precedes element 5).

The successor node is the last node in the middle order traversal, and the last node larger than it in the binary search tree.

Is the node. Right. Left. Left… , but when node.right == null, is the parent node of Node (for example, element 6 is the successor of element 5).

List 6: Predecessors and successors

predecessorGet the precursor node

Be aware of termination conditions in your code

public Node<E> predecessor(Node<E> node) { if (node == null) return null; // Node<E> p = node.left; if (p ! = null) { while (p.right ! = null) { p = p.right; } return p; } while (node.parent ! = null && node == node.parent. Left) {// The parent node is in the parent node and node is in the right child tree of the parent node = node.parent; } // node.parent == null // node == node.parent.right return node.parent; }Copy the code

successorGets the successor node

Be aware of termination conditions in your code

public Node<E> successor(Node<E> node) { if (node == null) return null; // Node<E> p = node.right; if (p ! = null) { while (p.left ! = null) { p = p.left; } return p; } while (node.parent ! = null && node == node.parent.right) {// The precursor node is in the parent node and node is in the left child tree of the parent node = node.parent; } // node.parent == null (root node) // node == node.parent. Right return node.parent; }Copy the code