# Домашнее задание №4

📗 В домашнем задании нужно реализовать упорядоченный словарь.



Идея упорядоченного словаря заключается в том, что он будет реализован на основе бинарного дерева поиска (BST). Дерево будет строиться только по ключам элементов, значения элементов при построении дерева не учитываются. Элементы с одинаковыми ключами в упорядоченном словаре хранить нельзя.



Поподробнее с бинарными деревьями поиска можно познакомиться здесь.



API для упорядоченного словаря будет выглядеть следующим образом:


```go
type OrderedMap struct { ... }

func NewOrderedMap() OrderedMap                      // создать упорядоченный словарь
func (m *OrderedMap) Insert(key, value int)          // добавить элемент в словарь
func (m *OrderedMap) Erase(key int)                  // удалить элемент из словари
func (m *OrderedMap) Contains(key int) bool          // проверить существование элемента в словаре
func (m *OrderedMap) Size() int                      // получить количество элементов в словаре
func (m *OrderedMap) ForEach(action func(int, int))  // применить функцию к каждому элементу словаря от меньшего к большему
```

📌 Для выполнения домашнего задания подготовлен шаблон кода и основные тесты, которую помогут проверить корректность реализации конвертации. Шаблона доступен по ссылке.



### Задание со звездочкой
Выполнять необязательно, но если вы уже знакомы c дженериками в Go, то попробуйте реализовать обобщенную OrderedMap, которая сможет работать с любыми comparable типами данных в качестве ключей и абсолютно любыми типами данных в качестве значений.