Tuesday, June 26, 2012

Binary Search Tree !!!

In computer science Binary search tree or BST is one of most common data structure used. A Binary search tree is a binary tree which follow the below properties
  • left sub tree of the node should contain less than or equal to node
  • right sub tree of the node should contain the greater than to the node
  • both left and right subtrees should also be a binary search tree
Binary search tree for the input values 8,13,3,11,1,6,14,12,4,7 is given below.
Binary Search Tree

One of the most advantage of Binary search tree is , sorting and searching operations are very efficient. Worst case complexity of searching using BST method is O(log(n)) where n is no. of nodes. And worst case for sorting using BST is O(n), Where as traditional sorting algorithms like bubble sort or quick sort the worst case is O(n*n). In the average case for the sorting in BST, the complexity reduces to (log(n)).

Operations on Binary Search Tree:
  • Searching
  • inserting
  • deleting
  • sort
  • traversal
Click here for complete working binary search tree C code.

Applications of the binary search tree:
  • Dictionaries
  • sets
  • multi sets
  • associate array

Popular Posts