CODEWITHSUNDEEP
algorithmdata-structures
1ang
1ang

Reputation: 321

Can binary search tree implement a Map?

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.

Upvotes: 6

Views: 10958

Answers (1)

Jack
Jack

Reputation: 133609

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

Upvotes: 7

Related Questions