Binary Search Tree

Abbreviated as BST.

The idea is to create a non-linear linked nodes. This way, we can perform a binary search with the expected efficiency, but also an efficient insertion and removal.

• You don't need to calculate the mid point, because the mid point leads you to another mid point.

This is a tree- the root is at the top and the branches are growing downwards.

• The first node where the tree originates from is called the root node.
• Except for the root node, every other node has a parent and zero or more children.
  • Nodes with the same parents are called siblings.
• Nodes with no children are called leaves.
• the parent-child relationship can be extended to ancestors and descendants.

In a binary tree, each node has at most two children (hence called binary).

A binary tree is a recursive structure. You can imagine that there is a left and right subtree to the left and right sides of the roots, each with their own roots and subtrees, etc. The

• In a tree T, a node n together with all of its decendants, is called a subtree of T. Node n is root of its subtree.
• Because it is recursive, it lends itself to a recursive implementation of operations on it.
• You can write itself by smaller instances of itself.

Binary Search Tree

Also called search tree. In a binary search tree, you will find all the values smaller than the root on the left subtree, and all the values bigger than the root is on the right subtree.

Implementation

The Node has pointers to the left and the right subtree.

Search if a value exists:

public boolean has(T t) {  
 Node<T> curr = root;  
while (curr != null) {  
   if (curr.data.equals(t)) {  
     return true;  
} else {  
     curr = (curr.data.compareTo(t) < 0) ? curr.right : curr.left;  
}  
 }  
 return false;  
}

Insert a value: Recursive method

@Override  
public void insert(T t) {  
  root = insert(root, t);  
  
}  
  
private Node<T> insert(Node<T> parent, T t) {  
  if (parent == null) {  
    return new Node<>(t);  
 }  
  
  if (parent.data.compareTo(t) > 0) {  
    parent.left = insert(parent.left, t);  
 } else {  
    parent.right = insert(parent.right, t);  
 }  
  return parent;  
}

Removal The remove operation needs to deal with three scenarios

1. Node to be removed is a leaf : remove from tree.
2. Node to be removed has only one child: copy child value into node and delete the child node.
3. Node to be removed has two children: find the smallest value in the node's right subtree (in-order succession). Copy the value key of the in-order successor to the target node and delete the in-order successor. (The largest value in the left subtree can also be used)