How to optimize a Binary Search Tree (BST) based on use-case

Posted on by

How to optimize a Binary Search Tree (BST) based on use-case

 

[[ What is a Binary Search Tree (BST)? ]]

A Binary Search Tree (BST) is a data structure consisting of node-based binary trees with each node holding a maximum of 2 weighted child nodes, and the child nodes arranged such that the right child-node (or sub-tree) is greater (in terms of weight) than the parent node and the left child-node is less than the parent node.

In cases where there are many nodes (more than one) to the right and left of the parent or root node, the nodes on either side form a sub-tree that must as well be a binary tree, that is, following the right (greater) and left (less) weight rules.

 

[[ Binary Search Tree (BST) Use/Applications ]]

Binary search trees are used for:-

1. Efficient lookup (Lookup Tables);
2. Fast addition and removal of nodes;
3. Efficient sorting;
4. Indexing Databases; and
5. Implementing Search Algorithms.

 

[[ Binary Search Tree (BST) in action ]]

ELEMENTS:: 

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

The elements above are sorted in an ascending order, from the least, 1, to the greatest, 10. Optimization when searching or looking up an element varies with the position of the element of interest, and the approach used to create the BST.

To build a binary search tree using the elements above, several approaches can be used. One approach results in a binary search tree with the Highest Height while another results in the Shortest Height.

 

[ BST with the Highest Height ]

(a) To generate a Binary Search Tree (BST) with the HIGHEST HEIGHT, one can use two approaches [this is the Worst-Case Scenario for BST in terms of height];

1. Make the least number, 1, the Root node. In this case, the BST will have the highest height, with the tree totally skewed to the right.

2. Make the greatest number, 10, the Root node. In this case, the BST will also have the highest height, with the tree totally skewed to the left.

The height for this Binary Search Tree (BST) is 10.

 

[ BST with the Least Height ]

(b) To generate a Binary Search Tree (BST) with the LEAST HEIGHT, one approach applies [this is the Best-Case Scenario for BST in terms of height] the following steps;

1. First, divide the list of elements in half.
2. Make the middle element the Root node.
3. Recursively do the same to each half, left and right, making each middle element the next (left or right, depending on if it is less or greater than the root node respectively) in the tree after the preceding.
4. Do this until the elements in the list are all included in the BST.

The height for this Binary Search Tree (BST) is 10/2 == 5

 

[[ TIme Complexity ]]

Worst Case Scenario :: O(n) 

Best Case Scenario :: O(log n)

 

How to optimize a Binary Search Tree (BST) based on use-case
Data Structures and Algorithms | thetqweb