Can binary search tree implement a Map?

Question

I am confused about the relationship between BST and Map when teacher asked a question "what it means for a binary tree to have the binary search tree property and why this makes it suitable to implement a Map". Can anyone explain it for me? Thanks.

Answer 1

A map is a kind of associative container in which keys are not forcibly integer (contrary to, for example, an array in which the key is always a number).

Now you want to store multiple pairs of key,value and you want to be able to lookup a value by its key efficiently, or add pairs efficiently, or remove pairs efficiently or whatever operation you are doing most.

A binary search tree is a data structure which has specified complexity of O(log n) for average case on all operations. This means that you are able to search for a specific node of the tree (which will have its own key and value) in an efficient manner.

This is the point, you can implement a map using a BST under the hood to obtain a structure which is efficient with some respect for many operations, but it's not the only way to implement a map (think about an hashmap).