Binary Search Tree

trees

Definition

Binary Search Tree

A binary search tree is a binary tree that allows for logarithmic search by enforcing a specific path rule.

Example: The left path of a tree node contains values lower or equal to the current tree node. The right path contains values greater than the current tree node.

By using this rule, we can efficiently insert and search for nodes. Instead of linearly searching through all nodes, we can ignore paths that are not of interest.

Operations

Insertion

Inserting a tree node is quite trivial. The paths must be walked where the node to be inserted is expected to be positioned. If we reach the expected position, which is null if the node is not already contained in the tree, then the node can be inserted at that position.

Algorithm:

def insert(root: TreeNode, q: TreeNode) -> None:
	r = null
	p = null
 
	while p != null:
		r = p
		
		if q.key < p.key:
			p = p.left
		else:
			p = p.right
 
	q.parent = r
	q.left = null
	q.right = null
 
	if r == null:
		root = q
	else:
		if q.key < r.key:
			r.left = q
		else:
			r.right = q

Removal

There are three cases that can occur when removing a tree node:

1. No children: If the tree node does not have any children, i.e. leaf nodes, can simply be removed without further complications.
2. One child: If the tree node does only have a single child, then the process of removing the tree node is equivalent to removing a node in a linked list, i.e. replacing the tree node with its child.
3. Two children: If the tree node has two children, then a replacement for that node must be found which can be removed from its original position.

Possible replacement nodes are:

• the tree node with the highest key of the left subtree (predecessor), or
• the tree node with the lowest key of the right subtree (Successor)

Algorithm:

Let $root$ be the root node of a binary tree and $q$ be the tree node to be removed:

def remove(root: TreeNode, q: TreeNode) -> None:
	if q.left == null or q.right == nul:
		r = q
	else :
		r = successor(q)
		q.key = r.key
		q.info = r.info
 
	if r.left != null:
		p = r.left
	else:
		p = r.right
 
	if p != null:
		p.parent = r.parent
 
	if r.parent == null:
		root = p
	else:
		if r == r.parent.left:
			r.parent.left = p
		else:
			r.parent.right = p