Menu
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.
309
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). array in which the key is always a number - in many languages, but not all.
Inside the TreeMap , the keys are are stored in a binary search tree, which makes it possible to traverse the keys, in order, in linear time.
A binary tree is a tree, where each node does not have more than two children. A Binary Search Tree (BST) is a tree, where for each node, the right child is greater than or equal to the left child. This leads to the right half of the tree having values generally greater than those of the left half at each level.
In computing, binary trees are mainly used for searching and sorting as they provide a means to store data hierarchically. Some common operations that can be conducted on binary trees include insertion, deletion, and traversal.
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).
172
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
