Binary Tree: Insert in O(log N) time, Delete, and Search
Problem Statement
We want to create a balanced binary tree that supports insertion in O(log N) time, deletion, and search operations.
Let’s have the following two constraints on insertion:
- We insert a node in the next level if the current level is complete.
- We create a right child if the left child is already present.
With these constraints, we guarantee that the binary tree is a complete binary tree that could be a perfect binary tree, given that we insert the right amount of nodes in the tree. Also, the binary tree will be a balanced binary tree.
Representation
First of all, we need to represent the binary tree. From the definition, a tree is a collection of nodes. A node consists of a value and references to its child nodes. We can represent the node as:
Node =>
Value
Node Left
Node Right
We can represent the tree as:
Tree =>
Node Root
The outside world need not know the internals of the node and the tree. We will provide the following interfaces for the outside world:
tree.insert(value)
tree.delete(value)
tree.search(value)
Observation
Before we start with insertion and deletion operations, let’s consider the following complete and balanced…