2
$\begingroup$

I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables.

I googled a lot for BST Representation of Hash Table. Code in C++ but didn't find any link or example. Can someone help me with the implementation. I'm really confused how to represend Key-Value pairs on BST. And what if there are collisions etc.

All, I found was comparison b/w BST and HasTables:

  1. https://stackoverflow.com/questions/22996474/why-implement-a-hashtable-with-a-binary-search-tree
  2. https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/

enter image description here

$\endgroup$
3
$\begingroup$

What the author means by implementing a HashTable as a BST is simply implementing a BST with $insert(), \space delete() \space and \space search()$ with slight modifications

  1. The node of the BST would have the following structure. $Node \space := (Key,Value)$.
  2. Insert a key-value pair by performing comparisons on the keys of two different pairs.
  3. Avoids nodes with redundant keys i.e. before insertion, if a node in the BST with the same key value exists, do not insert it. Else if no node with the same key exists, insert the key-value pair.
  4. No change in delete function.
  5. Search returns $null$ if no node's key matches, else return the value associated with the key which was searched.

Then use these functions assuming that these perform the corresponding operations on a HashTable.
Using a self-balancing BST would give $O(log\space n)$ time complexity for all the three functions defined above. And iterating through all the key-value pairs would simply mean doing an in-order traversal of the BST.

$\endgroup$
  • $\begingroup$ Actually, the author says about ability to iterate over keys IN ORDER, so in-order traversal is that she means $\endgroup$ – Bulat Sep 16 '18 at 20:17
  • $\begingroup$ @Bulat Oh right, thanks for the correction. I guess I glanced over the last part of the sentence. $\endgroup$ – RandomPerfectHashFunction Sep 16 '18 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.