4.Бинарные поисковые деревья

Бинарное дерево – у каждого отца не более 2 сыновей.

Бинарное дерево наз-ся поисковым, если для любой вершины ее ключ не меньше ключей всех ее левых потомков и не больше ключей всех ее правых потомков.

Каждая вершина хранит ключ, указатели на сыновей.

Поиск элемента

Добавление элемента

В бинарном поисковом дереве, образованном N случайными ключами, для успешного поиска в среднем требуется около 2logN сравнений.

В бинарном поисковом дереве, образованном N случайными ключами, для вставок и неудачного поиска в среднем требуется около 2 logN сравнений.

Для поиска в дереве бинарного поиска с N ключами в худшем случае может потребоваться N сравнений.

Вставка в корень. Ротация деревьев (Меняет ролями отца и сына)