[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.08,Default,,0000,0000,0000,,В этом видео мы продвинемся дальше за пределы элементарных двоичных деревьев поиска
Dialogue: 0,0:00:03.08,0:00:07.04,Default,,0000,0000,0000,,как те что мы обсуждали раньше, и начнем обсуждать
Dialogue: 0,0:00:07.04,0:00:10.07,Default,,0000,0000,0000,,сбалансированные двоичные деревья поиска. Это именно те деревья, которые стоит
Dialogue: 0,0:00:10.07,0:00:13.85,Default,,0000,0000,0000,,использовать на практике, так как они предоставляют хорошие гарантии на время выполнения.
Dialogue: 0,0:00:13.85,0:00:17.63,Default,,0000,0000,0000,,Эти деревья поддерживают свою сбалансированность, что означает,
Dialogue: 0,0:00:17.63,0:00:21.02,Default,,0000,0000,0000,,что высота остается логорифмической, что в свою очередь означает что все операции,
Dialogue: 0,0:00:21.02,0:00:25.00,Default,,0000,0000,0000,,поддерживаемые деревом поиска которые мы знаем и любим так же будут иметь сложность,
Dialogue: 0,0:00:25.00,0:00:27.01,Default,,0000,0000,0000,,логарифмическую от количества сохраненных ключей.
Dialogue: 0,0:00:27.01,0:00:30.06,Default,,0000,0000,0000,,Итак, давайте быстро повторим пройденное. Какое основное свойство структуры дерева?
Dialogue: 0,0:00:30.06,0:00:34.08,Default,,0000,0000,0000,,Для каждой вершины дерева должно выполняться: в левом поддереве
Dialogue: 0,0:00:34.08,0:00:38.06,Default,,0000,0000,0000,,будут только элементы меньше чем рассматриваемая вершина,
Dialogue: 0,0:00:38.06,0:00:42.02,Default,,0000,0000,0000,,в правом -- все элементы будут больше.
Dialogue: 0,0:00:42.02,0:00:45.61,Default,,0000,0000,0000,,Очень важно, что по фиксированному набору ключей
Dialogue: 0,0:00:45.61,0:00:48.88,Default,,0000,0000,0000,,можно построить очень много корректных бинарных деревьев поиска, содержащих
Dialogue: 0,0:00:48.88,0:00:50.99,Default,,0000,0000,0000,,данные ключи. Мы уже рассматривали пример
Dialogue: 0,0:00:50.99,0:00:53.53,Default,,0000,0000,0000,,с ключами один, два, три, четыре и пять.
Dialogue: 0,0:00:53.53,0:00:57.59,Default,,0000,0000,0000,,С одной стороны вы можете построить отлично сбалансированное дерево с высотой равной двум
Dialogue: 0,0:00:57.59,0:01:01.62,Default,,0000,0000,0000,,и с ключами от одного до пяти. С другой, можно так же построить
Dialogue: 0,0:01:01.62,0:01:05.96,Default,,0000,0000,0000,,безумную цепочку, практически превращая дерево в связанный список, высота которого для
Dialogue: 0,0:01:05.96,0:01:08.94,Default,,0000,0000,0000,,N элементов может достигать N-1. Итак, вообще говоря высота древьев может
Dialogue: 0,0:01:08.94,0:01:13.48,Default,,0000,0000,0000,,различаться экспоненциально. В лучшем случае высота будет
Dialogue: 0,0:01:13.48,0:01:16.42,Default,,0000,0000,0000,,логорифмической и в худшем -- линейной.
Dialogue: 0,0:01:16.42,0:01:20.15,Default,,0000,0000,0000,,Это мотивирует поиск деревьев, которые позволят
Dialogue: 0,0:01:20.15,0:01:23.62,Default,,0000,0000,0000,,не беспокоится об их высоте. Мы просто знаем что они
Dialogue: 0,0:01:23.62,0:01:25.59,Default,,0000,0000,0000,,хорошо сбалансированны, знаем что их высота
Dialogue: 0,0:01:25.59,0:01:28.24,Default,,0000,0000,0000,,логорифмична. Мы никогда не беспокоимся что они
Dialogue: 0,0:01:28.24,0:01:32.31,Default,,0000,0000,0000,,будут линейны. Помните, почему это так важно чтобы
Dialogue: 0,0:01:32.31,0:01:35.48,Default,,0000,0000,0000,,высота была небольшой? Потому, что время выполнения всех
Dialogue: 0,0:01:35.48,0:01:38.77,Default,,0000,0000,0000,,операций на дереве поиска зависит от его высоты.
Dialogue: 0,0:01:38.77,0:01:43.46,Default,,0000,0000,0000,,Хотите ли вы искать элементы, добавлять, находить предшествующий элемент
Dialogue: 0,0:01:43.46,0:01:48.33,Default,,0000,0000,0000,,или что бы то ни было ещё, высота дерева определяет время выполнения всех
Dialogue: 0,0:01:48.33,0:01:50.01,Default,,0000,0000,0000,,этих операций. Итак, основная идея работы
Dialogue: 0,0:01:50.01,0:01:54.78,Default,,0000,0000,0000,,с бинарными деревьями: так как высота
Dialogue: 0,0:01:54.78,0:01:58.46,Default,,0000,0000,0000,,не может быть меньше чем логорифмической от количество сохраненных
Dialogue: 0,0:01:58.46,0:02:02.19,Default,,0000,0000,0000,,элементов, потому что деревья бинарные => количество узлов может лишь
Dialogue: 0,0:02:02.19,0:02:05.15,Default,,0000,0000,0000,,удваиваться на каждом уровне => вам необходимо логорифмическое количество уровней
Dialogue: 0,0:02:05.15,0:02:07.04,Default,,0000,0000,0000,,чтобы сохранить все элементы.
Dialogue: 0,0:02:07.04,0:02:11.01,Default,,0000,0000,0000,,Если мы хотим, чтобы она была логорифмична, давайте убедимся что она остаётся такой
Dialogue: 0,0:02:11.01,0:02:16.40,Default,,0000,0000,0000,,всё время, даже после выполнения вставок и удалений. Если нам это удастся, мы получим огромное
Dialogue: 0,0:02:16.40,0:02:21.01,Default,,0000,0000,0000,,количество выполняемых за логорифмическое время операций.
Dialogue: 0,0:02:21.06,0:02:25.05,Default,,0000,0000,0000,,Как и всегда N обозначает количество ключей сохраненных в дереве.
Dialogue: 0,0:02:25.05,0:02:29.01,Default,,0000,0000,0000,,На свете очень очень много различных сбалансированных деревьев.
Dialogue: 0,0:02:29.01,0:02:33.02,Default,,0000,0000,0000,,Большинство из них не очень отличается от остальных.
Dialogue: 0,0:02:33.02,0:02:37.09,Default,,0000,0000,0000,,Я расскажу про одно из наиболее популярных -- Красно Черное Дерево.
Dialogue: 0,0:02:37.09,0:02:40.06,Default,,0000,0000,0000,,Оно было придумано в семидесятых
Dialogue: 0,0:02:40.10,0:02:44.67,Default,,0000,0000,0000,,и не является самым первым из известных сбалансированных деревьев -- это звание
Dialogue: 0,0:02:44.67,0:02:49.00,Default,,0000,0000,0000,,принадлежит АВЛ деревьям, которые в общем то не слишком отличаются от Красно Черных деревьев,
Dialogue: 0,0:02:49.00,0:02:51.62,Default,,0000,0000,0000,,хотя поддерживаемые инваринты и различны.