Data Structures: Binary Search Trees

Data Structures and time-complexity are an incredibly important aspect of computer science, and absolutely essential to thoroughly understand when dealing with any forms of data.

Today I am going to talk about Search Trees. Trees represent a very basic and incredibly simple data structure, that become more efficient and more complex as we add more rules to it. There are many types of search trees but we are going to talk about Binary Search Trees

Binary Trees are extremely fast, running with an average time complexity for most operations at O(log(n)), and in the worst scenario, at linear speed.

How fast is O(log(n)) exactly? Well if we had a binary tree with 4.2 million entries, it would take a mere 32 operations to complete. Now that is exciting!!


Explanation

Binary trees are actually very simple to program and even simpler to conceptualize:

  1. A binary tree is filled with nodes (represented by a circle on the image). This node can be filled with data but has a numerical value that determines its position
  2. Each node is a Sub Tree. In fact, unlike many other data structures, search trees don’t require a storage variable. This opens the door for the rotation of the root Node without altering the structure or integrity of their position.
  3. The algorithm for a Binary Tree is simple. When looking at a Node:
  • If the numerical value of the new tree is less than its parent node, a Sub Tree is created down the left branch of the parent Node
  • Otherwise, if the numerical value is greater than its parent node, a Sub Tree is created down the right branch of the parent node.

Visualization

Searching and Time Complexity

The Time Complexity of a Binary Search Tree is O(log(n)), it works by constantly splitting the list of trees in halves. Log(n) time complexity can only be achieved if the binary tree is equally distributed. An uneven binary tree might be O(n).

Binary Search Tree Implementation

  1. Start from the top of the tree, if the search value is larger, go to the right, if it is less than the current value, go to the left
  2. repeat
var BinarySearchTree = function(val){ 
this.val = val;
this.left = null;
this.right = null;
}
BinarySearchTree.prototype.addChild = function(val){ 
if(val <= this.val){
if(this.left === null){
this.left = new BinarySearchTree(val);
}else{
this.left.addChild(val);
}
}else{
if(this.right === null){
this.right = new BinarySearchTree(val);
}else{
this.right.addChild(val)
}
}
}
BinarySearchTree.prototype.contains = function(val){  
if(this.val === val){
return true
}else{
if(val < this.val && this.left){
return this.left.contains(val)
}else if(this.right){
return this.right.contains(val);
}
}
return “Not In Tree”
}

Binary Search in an Array

  1. calculate the start location, end location and the midpoint
  2. check to see if the element we are looking for is in the midpoint
  3. checks to see if the element we are looking for is greater or lower than the midpoint
  4. recursively check the relevant half of the array in the same fashion

Binary Search Array Function:

var binarySearch = function(array, element, start, end) { 
var start = start || 0; var end = end || array.length - 1;
var midpoint = Math.floor((end + start)/2);
if(array[midpoint] === element) {
return midpoint;
} if(array[midpoint]>element){
return binarySearch(array, element, start, midpoint-1);
} else {
return binarySearch(array, element, midpoint+1, end);
}
};

Now that is some cool stuff!


Originally published at questhenkart.com on March 30, 2015.