0:00:00.000,0:00:03.084
В этом видео мы продвинемся дальше за пределы элементарных двоичных деревьев поиска

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

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

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

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

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

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

0:00:25.005,0:00:27.012
логарифмическую от количества сохраненных ключей.

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

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

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

0:00:38.060,0:00:42.025
в правом -- все элементы будут больше.

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

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

0:00:48.875,0:00:50.986
данные ключи. Мы уже рассматривали пример

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

0:00:53.532,0:00:57.589
С одной стороны вы можете построить отлично сбалансированное дерево с высотой равной двум

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

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

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

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

0:01:13.479,0:01:16.417
логорифмической и в худшем -- линейной.

0:01:16.417,0:01:20.148
Это мотивирует поиск деревьев, которые позволят

0:01:20.148,0:01:23.621
не беспокоится об их высоте. Мы просто знаем что они

0:01:23.621,0:01:25.589
хорошо сбалансированны, знаем что их высота

0:01:25.589,0:01:28.236
логорифмична. Мы никогда не беспокоимся что они

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

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

0:01:35.481,0:01:38.773
операций на дереве поиска зависит от его высоты.

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

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

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

0:01:50.013,0:01:54.776
с бинарными деревьями: так как высота

0:01:54.776,0:01:58.463
не может быть меньше чем логорифмической от количество сохраненных

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

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

0:02:05.151,0:02:07.040
чтобы сохранить все элементы.

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

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

0:02:16.399,0:02:21.012
количество выполняемых за логорифмическое время операций.

0:02:21.056,0:02:25.048
Как и всегда N обозначает количество ключей сохраненных в дереве.

0:02:25.048,0:02:29.006
На свете очень очень много различных сбалансированных деревьев.

0:02:29.006,0:02:33.022
Большинство из них не очень отличается от остальных.

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

0:02:37.092,0:02:40.062
Оно было придумано в семидесятых

0:02:40.096,0:02:44.674
и не является самым первым из известных сбалансированных деревьев -- это звание

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

0:02:49.000,0:02:51.617
хотя поддерживаемые инваринты и различны.