Binary search trees

Posted on

What is a binary search tree?

Binary search trees is a data structure organised in a hierarchical structure of notes which is used for searching. The purpose of a binary search tree is for storing data for rapid access, storage and deletion. Data in a binary search tree are stored in the tree nodes, which must have associated with them a value or key.

The keys are used to structure the tree so that the value of the left child node is less than that of the parent node, so that the value of a right child node is greater than that of the parent node. Sometimes. Typical key storage values include strings, integers and doubles.

binary search tree diagram

Basic operations of a binary search tree

Insertion

Adding a value to a binary search tree can be broken down into two stages

  • Searching for a place to insert the new element
  • Inserting the new element to this place

The steps of insertion of a binary search tree

1. Check to see if the value in the current node and a new value are equal. If so, a duplicate is found.
2. If a new value is less than the node’s value:

  • If the current node has no left child, a place for insertion has been found
  • If not, handle the left child with the same algorithm

3. If a new value is greater than the node’s value:

  • If the current node has no right child, a place for insertion has been found
  • If not, handle the right child with the same algorithm

Example – Insert 4 to the binary search tree

binary search tree diagram 1

binary search tree diagram 2

binary search tree diagram 3

binary search tree diagram 4

Insertion code sample in C++

</pre>
<pre>// Insertation code example
bool BinarySearchTree::add(int val)
{

if(root == NULL)
{
root = new BSTNode(val);
return true;
}

else
return root−>add(val);
}
bool BSTNode::add(int val)
{
if(val == this−>value)
return false;
else if(val < this−>value)
{
if(left == NULL)
{
left = new BSTNode(val);
return true;
}
else
return left−>add(val);
}
else if(val > this−>value)
{
if(right == NULL)
{
right = new BSTNode(val);
return true;
}
else
return right−>add(val);
}
return false;
}
</pre>
<pre>

Searching

Searching for a value in a binary search tree is similar to an insertion operation. The search algorithm traverses the tree in detail, so a proper choice can be made.

The steps of searching a binary tree are:

1. Check the value in the current node and searched value are equal. If so, the value is found. Otherwise

2. If the searched value is less than the node’s value

  • If the current node has no left child, the searched value doesn’t exist in the binary search tree
  • If not, handle the left child with the same steps

3. If a new value is greater, than the node’s value

  • If the current node has no right child, the searched value doesn’t exist in the binary search tree
  • If not, handle the right child with the same steps

Example – Search for 3 in the binary search tree

binary search tree diagram 1

binary search tree diagram 2

binary search tree diagram 3

Searching C++ code sample

// Searching code example
bool BinarySearchTree::search(int val)
{
if(root == NULL)
return false;
else
return root−>search(val);
}

bool BinarySearchTreeNode::search(int val)
{
if(value == this−>val)
return true;
else if(val < this−>val)
{
if(left == NULL)
return false;
else
return left−>search(val);
}
else if(val > this−>value)
{
if(right == NULL)
return false;
else
return right−>search(val);
}
return false;
}

Deletion

The operation of deletion is more complex than add and search. It can be broken down into two parts

  • Searching for a node to remove
  • If the node is found, run the remove steps

There are three concepts of deletion in a binary search tree which are:

1. Node to be removed that has one child

The node is cut from the binary search tree and the algorithm links the single child with it’s subtree directly to the parent of the removed node.

Example: Remove 17 from the binary search tree

binary search tree deletion one child

2. Node to be removed that has two children
The steps are
– Find the minimum value in the right sub tree
– Replace value of the node to be removed with the minimum value found in the previous step
– Call the remove step to the right subtree to remove a duplicate
Example: Remove 17 from the binary search tree

binary search tree deletion two child

binary search tree deletion two part child

binary search tree deletion two part 4 child - Copy - Copy

binary search tree deletion two part 5 child - Copy - Copy - Copy

3. Node to be removed that has no children

This case is the easiest. The algorithm sets a corresponding link of the parent to NULL and disposes the node.
Example – Remove -7 from the binary search tree

binary search tree deletion no child

</pre>
<pre>// Deletion
bool BinarySearchTree::remove(int val)
{
if(root == NULL)
{
return false;
}
else
{
if(root−>getValue() == val)
{
BinarySearchTree_Node auxRoot(0);
auxRoot.setLeftChild(root);
BinarySearchTree_Node* removeNode = root−>remove(val, &auxRoot);
root = auxRoot.getLeft();

if(removeNode != NULL)
{
delete removeNode;
return true;
}
else
{
return false;
}
}
else
{
BinarySearchTree_Node removeNode = root−>remove(value, NULL);
if(removeNode != NULL)
{
delete removeNode;
return true;
}
else
return false;
}
}
}

BinarySearchTree_Node* BinarySearchTree_Node::remove(int value, BinarySearchTree_Node *parent)
{
if(value < this−>val)
{
if(left != NULL)
return left−>remove(val, this);
else
return NULL;
}
else if(value > this−>val)
{
if(right != NULL)
return right−>remove(val, this);
else
return NULL;
}
else
{
if(left != NULL && right != NULL)
{
this−>val = right−>minVal();
return right−>remove(this−>val, this);
}
else if(parent−>left == this)
{
parent−>left = (left != NULL) ? left : right;
return this;
}
else if(parent−>right == this)
{
parent−>right = (left != NULL) ? left :right;
return this;
}
}
}

int BinarySearchTree_Node::minVal()
{
if(left == NULL)
return val;
else
return left−>minVal;
}</pre>
<pre>
Share this post