Linked List

Hash Table and Binary Tree

   Binary tree is a-node based binary tree that can do some operations like:

1. Search.
2. Insert.
3. Delete. 

The Binary tree has a composition of:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

this picture next of this text is an example of Binary Tree.

   Hash table is a data structure that has the same use like Binary tree, Hash table used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots. This program will implement hash table where at each array index, we will create a Binary tree, to prevent key collision. Key having same index will be stored in Binary tree as it can store multiple data.

Hash table supports : 

1. Search.
2. Insert.
3. Delete.

in the same time, it was the major advantages over binary search tree.

this is the example of the hashing table.

While it seems like Hash table is more superior than BST, but there is always a reason too pick BST over HT, those situations are:

• We can get all keys in sorted order by just doing Inorder Traversal of BST. This is not a natural operation in Hash Tables and requires extra efforts.
• Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BST. Like sorting, these operations are not a natural operation with Hash Tables.
• BST are easy to implement compared to hashing, we can easily implement our own customized BST. To implement Hashing, we generally rely on libraries provided by programming languages.
• ith Self-Balancing BST, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.