6

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.

Improve this question
2
  • What are the operations a Map should support? Can they be implemented using a BST? What is the storage complexity of a BST? Under which conditions will these operations be faster using a BST, compared with just using, say, a linked list? Commented Dec 31, 2015 at 16:43
  • see en.wikipedia.org/wiki/Abstract_data_type Commented Dec 31, 2015 at 16:45

1 Answer 1

Reset to default
7

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

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

array in which the key is always a number - in many languages, but not all.
So, the Map implemented by BST is still not as good as hash map whose complexity is O(1).
@greybeard: if the key of an array is not a number then it's not an array, it's an associative array or map. Now the term is rather smokey since some languages pretend to call their maps array (because they allow to map any kind of key with a value), but they are not array, they are maps.
@1ang: yes, hashmap has O(1) but that fixed complexity could be higher than a simple O(logn) lookup for smaller data structures. Then you have to take into account the memory complexity, you have to take into account the fact that and hashmap needs rehashing when going over its load factor and most importantly a BST can manage ordering, while a hashmap can't.
@greybeard: I'm not considering balanced trees, speaking about general BSTs you have O(logn) for average case and O(n) for worst case. You can improve worst-case with balanced trees but that's not the point. Specified in sense of "provable through coputational complexity theory", another issue which is not the point of the answer and is irrelevant to the OP.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.