16.5 BSTs as Sets and Maps

We can use a BST to implement the Set ADT. If we use a BST, we can decrease the runtime of contains to $\log(n)$ because of the BST property which enables us to use binary search!

We can also make a binary tree into a map by having each BST node hold (key,value) pairs instead of singular values. We will compare each element's key in order to determine where to place it within our tree.

Previous16.4 BST Operations Next16.6 Summary

Last updated 1 year ago

We can use a BST to implement the Set ADT. If we use a BST, we can decrease the runtime of contains to $\log(n)$ because of the BST property which enables us to use binary search!