Ссылки:
Декартово дерево: часть 1 - https://habr.com/ru/post/101818/
Декартово дерево: часть 2 - https://habr.com/ru/post/102006/
Декартово дерево: часть 3 - https://habr.com/ru/post/102364/

ДЗ:
Реализация красно-чёрного дерева, вставки и поиска
Основное задание:
1. Реализовать самостоятельно красно-черное дерево, операции вставка, удаление, поиск

2. Тест на производительность. 
Сравнить АВЛ-дерево и красно-черное дерево.
- тест вставки
- тест поиска
- тест удаления

Тест вставки
- 5 млн случайных чисел - random(0..LONG_MAX)
- 5 млн упорядоченных чисел
- данные из dataset в материалах занятия. Код загрузки датасета в массив там же.

Замерить высоту дерева

Тест поиска
- 5 млн случайных чисел - random(0..LONG_MAX)
- 5 тыс случайных чисел, сохранить в массив, потом поиск этих чисел в цикле 1000 раз. Общее количество поиска - 5 млн
- 5 млн случайных чисел из датасет

Тест удаление
- 1 млн случайных чисел

Замерить высоту дерева

Опционально 1:
Реализовать на выбор одно из деревьев
- BST - бинарное дерево поиска
- Splay - расширяющееся дерево
- рандомизированное дерево

Добавить в тест.

Опционально 2:
Сделать глобальный тест, добавив туда все варианты деревьев
Добавить в тест 
- hash-таблицы
- стандартную реализацию деревьев из языка