-
В этом видео мы продвинемся дальше за пределы элементарных двоичных деревьев поиска
-
как те что мы обсуждали раньше, и начнем обсуждать
-
сбалансированные двоичные деревья поиска. Это именно те деревья, которые стоит
-
использовать на практике, так как они предоставляют хорошие гарантии на время выполнения.
-
Эти деревья поддерживают свою сбалансированность, что означает,
-
что высота остается логорифмической, что в свою очередь означает что все операции,
-
поддерживаемые деревом поиска которые мы знаем и любим так же будут иметь сложность,
-
логарифмическую от количества сохраненных ключей.
-
Итак, давайте быстро повторим пройденное. Какое основное свойство структуры дерева?
-
Для каждой вершины дерева должно выполняться: в левом поддереве
-
будут только элементы меньше чем рассматриваемая вершина,
-
в правом -- все элементы будут больше.
-
Очень важно, что по фиксированному набору ключей
-
можно построить очень много корректных бинарных деревьев поиска, содержащих
-
данные ключи. Мы уже рассматривали пример
-
с ключами один, два, три, четыре и пять.
-
С одной стороны вы можете построить отлично сбалансированное дерево с высотой равной двум
-
и с ключами от одного до пяти. С другой, можно так же построить
-
безумную цепочку, практически превращая дерево в связанный список, высота которого для
-
N элементов может достигать N-1. Итак, вообще говоря высота древьев может
-
различаться экспоненциально. В лучшем случае высота будет
-
логорифмической и в худшем -- линейной.
-
Это мотивирует поиск деревьев, которые позволят
-
не беспокоится об их высоте. Мы просто знаем что они
-
хорошо сбалансированны, знаем что их высота
-
логорифмична. Мы никогда не беспокоимся что они
-
будут линейны. Помните, почему это так важно чтобы
-
высота была небольшой? Потому, что время выполнения всех
-
операций на дереве поиска зависит от его высоты.
-
Хотите ли вы искать элементы, добавлять, находить предшествующий элемент
-
или что бы то ни было ещё, высота дерева определяет время выполнения всех
-
этих операций. Итак, основная идея работы
-
с бинарными деревьями: так как высота
-
не может быть меньше чем логорифмической от количество сохраненных
-
элементов, потому что деревья бинарные => количество узлов может лишь
-
удваиваться на каждом уровне => вам необходимо логорифмическое количество уровней
-
чтобы сохранить все элементы.
-
Если мы хотим, чтобы она была логорифмична, давайте убедимся что она остаётся такой
-
всё время, даже после выполнения вставок и удалений. Если нам это удастся, мы получим огромное
-
количество выполняемых за логорифмическое время операций.
-
Как и всегда N обозначает количество ключей сохраненных в дереве.
-
На свете очень очень много различных сбалансированных деревьев.
-
Большинство из них не очень отличается от остальных.
-
Я расскажу про одно из наиболее популярных -- Красно Черное Дерево.
-
Оно было придумано в семидесятых
-
и не является самым первым из известных сбалансированных деревьев -- это звание
-
принадлежит АВЛ деревьям, которые в общем то не слишком отличаются от Красно Черных деревьев,
-
хотя поддерживаемые инваринты и различны.