Операции для дерева поиска¶

Перед тем, как рассмотреть реализацию, давайте освежим в памяти интерфейс, предоставляемый АТД map. Вы можете заметить, что он очень похож на словарь Python.

• Map() Создаёт новое пустое отображение.
• put(key,val) Добавляет в отображение новую пару ключ-значение. Если ключ уже существует, то заменяет старое значение новым.
• get(key) По заданному ключу возвращает значение, хранящееся в отображении, или None, если такого ключа не существует.
• del Удаляет пару ключ-значение из отображения, используя оператор вида del map[key].
• len() Возвращает количество пар ключ-значение, хранящихся в отображении.
• in Возвращает True для оператора вида key in map, если заданный ключ присутствует в отображении.