Красно-Черные деревья (21 мин)

В этом видео мы продвинемся дальше за пределы элементарных двоичных деревьев поиска

как те что мы обсуждали раньше, и начнем обсуждать

сбалансированные двоичные деревья поиска. Это именно те деревья, которые стоит

использовать на практике, так как они предоставляют хорошие гарантии на время выполнения.

Эти деревья поддерживают свою сбалансированность, что означает,

что высота остается логорифмической, что в свою очередь означает что все операции,

поддерживаемые деревом поиска которые мы знаем и любим так же будут иметь сложность,

логарифмическую от количества сохраненных ключей.

Итак, давайте быстро повторим пройденное. Какое основное свойство структуры дерева?

Для каждой вершины дерева должно выполняться: в левом поддереве

будут только элементы меньше чем рассматриваемая вершина,

в правом -- все элементы будут больше.

Очень важно, что по фиксированному набору ключей

можно построить очень много корректных бинарных деревьев поиска, содержащих

данные ключи. Мы уже рассматривали пример

с ключами один, два, три, четыре и пять.

С одной стороны вы можете построить отлично сбалансированное дерево с высотой равной двум

и с ключами от одного до пяти. С другой, можно так же построить

безумную цепочку, практически превращая дерево в связанный список, высота которого для

N элементов может достигать N-1. Итак, вообще говоря высота древьев может

различаться экспоненциально. В лучшем случае высота будет

логорифмической и в худшем -- линейной.

Это мотивирует поиск деревьев, которые позволят

не беспокоится об их высоте. Мы просто знаем что они

хорошо сбалансированны, знаем что их высота

логорифмична. Мы никогда не беспокоимся что они

будут линейны. Помните, почему это так важно чтобы

высота была небольшой? Потому, что время выполнения всех

операций на дереве поиска зависит от его высоты.

Хотите ли вы искать элементы, добавлять, находить предшествующий элемент

или что бы то ни было ещё, высота дерева определяет время выполнения всех

этих операций. Итак, основная идея работы

с бинарными деревьями: так как высота

не может быть меньше чем логорифмической от количество сохраненных

элементов, потому что деревья бинарные => количество узлов может лишь

удваиваться на каждом уровне => вам необходимо логорифмическое количество уровней

чтобы сохранить все элементы.

Если мы хотим, чтобы она была логорифмична, давайте убедимся что она остаётся такой

всё время, даже после выполнения вставок и удалений. Если нам это удастся, мы получим огромное

количество выполняемых за логорифмическое время операций.

Как и всегда N обозначает количество ключей сохраненных в дереве.

На свете очень очень много различных сбалансированных деревьев.

Большинство из них не очень отличается от остальных.

Я расскажу про одно из наиболее популярных -- Красно Черное Дерево.

Оно было придумано в семидесятых

и не является самым первым из известных сбалансированных деревьев -- это звание

принадлежит АВЛ деревьям, которые в общем то не слишком отличаются от Красно Черных деревьев,

хотя поддерживаемые инваринты и различны.