1 00:00:00,000 --> 00:00:03,084 В этом видео мы продвинемся дальше за пределы элементарных двоичных деревьев поиска 2 00:00:03,084 --> 00:00:07,035 как те что мы обсуждали раньше, и начнем обсуждать 3 00:00:07,035 --> 00:00:10,067 сбалансированные двоичные деревья поиска. Это именно те деревья, которые стоит 4 00:00:10,067 --> 00:00:13,852 использовать на практике, так как они предоставляют хорошие гарантии на время выполнения. 5 00:00:13,852 --> 00:00:17,627 Эти деревья поддерживают свою сбалансированность, что означает, 6 00:00:17,627 --> 00:00:21,015 что высота остается логорифмической, что в свою очередь означает что все операции, 7 00:00:21,015 --> 00:00:25,005 поддерживаемые деревом поиска которые мы знаем и любим так же будут иметь сложность, 8 00:00:25,005 --> 00:00:27,012 логарифмическую от количества сохраненных ключей. 9 00:00:27,012 --> 00:00:30,056 Итак, давайте быстро повторим пройденное. Какое основное свойство структуры дерева? 10 00:00:30,056 --> 00:00:34,075 Для каждой вершины дерева должно выполняться: в левом поддереве 11 00:00:34,075 --> 00:00:38,060 будут только элементы меньше чем рассматриваемая вершина, 12 00:00:38,060 --> 00:00:42,025 в правом -- все элементы будут больше. 13 00:00:42,025 --> 00:00:45,614 Очень важно, что по фиксированному набору ключей 14 00:00:45,614 --> 00:00:48,875 можно построить очень много корректных бинарных деревьев поиска, содержащих 15 00:00:48,875 --> 00:00:50,986 данные ключи. Мы уже рассматривали пример 16 00:00:50,986 --> 00:00:53,532 с ключами один, два, три, четыре и пять. 17 00:00:53,532 --> 00:00:57,589 С одной стороны вы можете построить отлично сбалансированное дерево с высотой равной двум 18 00:00:57,589 --> 00:01:01,618 и с ключами от одного до пяти. С другой, можно так же построить 19 00:01:01,618 --> 00:01:05,957 безумную цепочку, практически превращая дерево в связанный список, высота которого для 20 00:01:05,957 --> 00:01:08,936 N элементов может достигать N-1. Итак, вообще говоря высота древьев может 21 00:01:08,936 --> 00:01:13,479 различаться экспоненциально. В лучшем случае высота будет 22 00:01:13,479 --> 00:01:16,417 логорифмической и в худшем -- линейной. 23 00:01:16,417 --> 00:01:20,148 Это мотивирует поиск деревьев, которые позволят 24 00:01:20,148 --> 00:01:23,621 не беспокоится об их высоте. Мы просто знаем что они 25 00:01:23,621 --> 00:01:25,589 хорошо сбалансированны, знаем что их высота 26 00:01:25,589 --> 00:01:28,236 логорифмична. Мы никогда не беспокоимся что они 27 00:01:28,236 --> 00:01:32,309 будут линейны. Помните, почему это так важно чтобы 28 00:01:32,309 --> 00:01:35,481 высота была небольшой? Потому, что время выполнения всех 29 00:01:35,481 --> 00:01:38,773 операций на дереве поиска зависит от его высоты. 30 00:01:38,773 --> 00:01:43,455 Хотите ли вы искать элементы, добавлять, находить предшествующий элемент 31 00:01:43,455 --> 00:01:48,334 или что бы то ни было ещё, высота дерева определяет время выполнения всех 32 00:01:48,334 --> 00:01:50,013 этих операций. Итак, основная идея работы 33 00:01:50,013 --> 00:01:54,776 с бинарными деревьями: так как высота 34 00:01:54,776 --> 00:01:58,463 не может быть меньше чем логорифмической от количество сохраненных 35 00:01:58,463 --> 00:02:02,186 элементов, потому что деревья бинарные => количество узлов может лишь 36 00:02:02,186 --> 00:02:05,151 удваиваться на каждом уровне => вам необходимо логорифмическое количество уровней 37 00:02:05,151 --> 00:02:07,040 чтобы сохранить все элементы. 38 00:02:07,040 --> 00:02:11,007 Если мы хотим, чтобы она была логорифмична, давайте убедимся что она остаётся такой 39 00:02:11,007 --> 00:02:16,399 всё время, даже после выполнения вставок и удалений. Если нам это удастся, мы получим огромное 40 00:02:16,399 --> 00:02:21,012 количество выполняемых за логорифмическое время операций. 41 00:02:21,056 --> 00:02:25,048 Как и всегда N обозначает количество ключей сохраненных в дереве. 42 00:02:25,048 --> 00:02:29,006 На свете очень очень много различных сбалансированных деревьев. 43 00:02:29,006 --> 00:02:33,022 Большинство из них не очень отличается от остальных. 44 00:02:33,022 --> 00:02:37,092 Я расскажу про одно из наиболее популярных -- Красно Черное Дерево. 45 00:02:37,092 --> 00:02:40,062 Оно было придумано в семидесятых 46 00:02:40,096 --> 00:02:44,674 и не является самым первым из известных сбалансированных деревьев -- это звание 47 00:02:44,674 --> 00:02:49,000 принадлежит АВЛ деревьям, которые в общем то не слишком отличаются от Красно Черных деревьев, 48 00:02:49,000 --> 00:02:51,617 хотя поддерживаемые инваринты и различны.