Search Tree Operations¶

Before we look at the implementation, let’s review the interface provided by the map ADT. You will notice that this interface is very similar to the Python dictionary.

• Map() Create a new, empty map.
• put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
• get(key) Given a key, return the value stored in the map or None otherwise.
• del Delete the key-value pair from the map using a statement of the form del map[key].
• len() Return the number of key-value pairs stored in the map.
• in Return True for a statement of the form key in map, if the given key is in the map.