WEBVTT 00:00:00.000 --> 00:00:03.084 В этом видео мы продвинемся дальше за пределы элементарных двоичных деревьев поиска 00:00:03.084 --> 00:00:07.035 как те что мы обсуждали раньше, и начнем обсуждать 00:00:07.035 --> 00:00:10.067 сбалансированные двоичные деревья поиска. Это именно те деревья, которые стоит 00:00:10.067 --> 00:00:13.852 использовать на практике, так как они предоставляют хорошие гарантии на время выполнения. 00:00:13.852 --> 00:00:17.627 Эти деревья поддерживают свою сбалансированность, что означает, 00:00:17.627 --> 00:00:21.015 что высота остается логорифмической, что в свою очередь означает что все операции, 00:00:21.015 --> 00:00:25.005 поддерживаемые деревом поиска которые мы знаем и любим так же будут иметь сложность, 00:00:25.005 --> 00:00:27.012 логарифмическую от количества сохраненных ключей. 00:00:27.012 --> 00:00:30.056 Итак, давайте быстро повторим пройденное. Какое основное свойство структуры дерева? 00:00:30.056 --> 00:00:34.075 Для каждой вершины дерева должно выполняться: в левом поддереве 00:00:34.075 --> 00:00:38.060 будут только элементы меньше чем рассматриваемая вершина, 00:00:38.060 --> 00:00:42.025 в правом -- все элементы будут больше. 00:00:42.025 --> 00:00:45.614 Очень важно, что по фиксированному набору ключей 00:00:45.614 --> 00:00:48.875 можно построить очень много корректных бинарных деревьев поиска, содержащих 00:00:48.875 --> 00:00:50.986 данные ключи. Мы уже рассматривали пример 00:00:50.986 --> 00:00:53.532 с ключами один, два, три, четыре и пять. 00:00:53.532 --> 00:00:57.589 С одной стороны вы можете построить отлично сбалансированное дерево с высотой равной двум 00:00:57.589 --> 00:01:01.618 и с ключами от одного до пяти. С другой, можно так же построить 00:01:01.618 --> 00:01:05.957 безумную цепочку, практически превращая дерево в связанный список, высота которого для 00:01:05.957 --> 00:01:08.936 N элементов может достигать N-1. Итак, вообще говоря высота древьев может 00:01:08.936 --> 00:01:13.479 различаться экспоненциально. В лучшем случае высота будет 00:01:13.479 --> 00:01:16.417 логорифмической и в худшем -- линейной. 00:01:16.417 --> 00:01:20.148 Это мотивирует поиск деревьев, которые позволят 00:01:20.148 --> 00:01:23.621 не беспокоится об их высоте. Мы просто знаем что они 00:01:23.621 --> 00:01:25.589 хорошо сбалансированны, знаем что их высота 00:01:25.589 --> 00:01:28.236 логорифмична. Мы никогда не беспокоимся что они 00:01:28.236 --> 00:01:32.309 будут линейны. Помните, почему это так важно чтобы 00:01:32.309 --> 00:01:35.481 высота была небольшой? Потому, что время выполнения всех 00:01:35.481 --> 00:01:38.773 операций на дереве поиска зависит от его высоты. 00:01:38.773 --> 00:01:43.455 Хотите ли вы искать элементы, добавлять, находить предшествующий элемент 00:01:43.455 --> 00:01:48.334 или что бы то ни было ещё, высота дерева определяет время выполнения всех 00:01:48.334 --> 00:01:50.013 этих операций. Итак, основная идея работы 00:01:50.013 --> 00:01:54.776 с бинарными деревьями: так как высота 00:01:54.776 --> 00:01:58.463 не может быть меньше чем логорифмической от количество сохраненных 00:01:58.463 --> 00:02:02.186 элементов, потому что деревья бинарные => количество узлов может лишь 00:02:02.186 --> 00:02:05.151 удваиваться на каждом уровне => вам необходимо логорифмическое количество уровней 00:02:05.151 --> 00:02:07.040 чтобы сохранить все элементы. 00:02:07.040 --> 00:02:11.007 Если мы хотим, чтобы она была логорифмична, давайте убедимся что она остаётся такой 00:02:11.007 --> 00:02:16.399 всё время, даже после выполнения вставок и удалений. Если нам это удастся, мы получим огромное 00:02:16.399 --> 00:02:21.012 количество выполняемых за логорифмическое время операций. 00:02:21.056 --> 00:02:25.048 Как и всегда N обозначает количество ключей сохраненных в дереве. 00:02:25.048 --> 00:02:29.006 На свете очень очень много различных сбалансированных деревьев. 00:02:29.006 --> 00:02:33.022 Большинство из них не очень отличается от остальных. 00:02:33.022 --> 00:02:37.092 Я расскажу про одно из наиболее популярных -- Красно Черное Дерево. 00:02:37.092 --> 00:02:40.062 Оно было придумано в семидесятых 00:02:40.096 --> 00:02:44.674 и не является самым первым из известных сбалансированных деревьев -- это звание 00:02:44.674 --> 00:02:49.000 принадлежит АВЛ деревьям, которые в общем то не слишком отличаются от Красно Черных деревьев, 00:02:49.000 --> 00:02:51.617 хотя поддерживаемые инваринты и различны.