BST representation of Hash Tables

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:

• https://stackoverflow.com/questions/22996474/why-implement-a-hashtable-with-a-binary-search-tree

• https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/

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

• The node of the BST would have the following structure. $Node \space := (Key,Value)$.

• Insert a key-value pair by performing comparisons on the keys of two different pairs.

• 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.

• No change in delete function.

• 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.

StackExchange Computer Science Q#97370, answer score: 4