Question

Why should you implement BST, AVL, Splay, B, B+, hashing?

For example : if 80% access are to 20% of item , then we use Splay tree ....... etc

Answer 1

Reason to implement BST:

• Binary Search Trees are the data structure that can maintain dynamically changing dataset in a preferably sorted order. Thus Searching becomes efficient(Binary Search) along with insertion and deletion which is not in the case of an array.

Reason to implement AVL:

• AVL Trees are basically BST with difference between heights of left and right subtrees are a maximum of 1. Most of BST operations require a time-complexity of O(h) where h is the height of the tree and for skewed BST h is increased and so does the time. Keeping h as low as possible make the operations efficient.

Reason to implement Splay:

• Splay Tree is a self-balancing tree who's main motive is to bring the recently accessed element to the root of the tree. Thus, using the idea of locality of reference. So when few specific items among many are searched, splay tree becomes useful.

Reason to implement B Tree:

• B-Tree works upon the concept of disk accesses and reduces the total time taken to access disk by having lesser height and keeping multiple keys at a node. Size of keys in a node correspond to a block size as data from disk is always accessed in blocks. Thus a fatter B Tree helps in fast data access keeping height low and equal for all subtrees.

Reason to implement B+ Tree:

• B+ Tree is a variation of B Tree, where all the data are saved in the leaf nodes. Internal node contains only the keys. All leaf nodes are at same level and are linked together for efficient range queries. B+ Trees help store large amount of data in leaves.

Reason to implement Hashing:

• Hashing is implemented to have fast data retrieval. Often target is to retrieve required data in O(1) time and thus hashing is used. Suitable Hash function generate locations to store data based on some calculation based on the data. These location can be obtained from the data again to search faster.