Обсуждение участницы:Анна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше)
(Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше)
Строка 23: Строка 23:
 
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>. Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.
 
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>. Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.
  
Вернемся к примеру (рис. <tex>1</tex>). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.
+
Вернемся к примеру (рис. <tex>1</tex>). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. <tex>1</tex> первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.
  
 
Алгоритм построения следующий: пусть мы пришли в поддерево <tex>S</tex> с корнем <tex>\leqslant x</tex>. Тогда сольем его с уже построенным на тот момент <tex>T_{1}</tex> (<tex>T_{1}</tex> пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, <tex>S \leqslant T_{1}</tex> и <tex>h(T_{1}) \leqslant h(S)</tex>). Но так как обычная процедура слияния сливает два АВЛ-дерева, а <tex>S</tex> не является корректным АВЛ-деревом, мы немного ее изменим.
 
Алгоритм построения следующий: пусть мы пришли в поддерево <tex>S</tex> с корнем <tex>\leqslant x</tex>. Тогда сольем его с уже построенным на тот момент <tex>T_{1}</tex> (<tex>T_{1}</tex> пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, <tex>S \leqslant T_{1}</tex> и <tex>h(T_{1}) \leqslant h(S)</tex>). Но так как обычная процедура слияния сливает два АВЛ-дерева, а <tex>S</tex> не является корректным АВЛ-деревом, мы немного ее изменим.

Версия 09:54, 31 мая 2015

Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше

Пусть у нас есть дерево [math]T[/math]. Мы должны разбить его на два дерева [math]T_{1}[/math] и [math]T_{2}[/math] такие, что [math]T_{1} \leqslant x[/math] и [math]x \lt T_{2}[/math].

Предположим, что корень нашего дерева [math]\leqslant x[/math], в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево [math]T_{1}[/math]. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи [math]\leqslant x[/math]). Если же корень оказался [math]\gt x[/math], то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.

Пусть мы пришли в поддерево [math]S[/math], корень которого [math]\leqslant x[/math]. В таком случае этот корень со своим левым поддеревом должен отойти в дерево [math]T_{1}[/math]. Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево [math]S[/math], удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево [math]S[/math]). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины [math]S[/math] и запускаем балансировку. Обозначим полученное дерево за [math]T'[/math]. Теперь нам нужно объединить его с уже построенным ранее [math]T_{1}[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math]). Для этого мы ищем в дереве [math]T_{1}[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]T'[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math], сливая [math]P[/math] и [math]T'[/math] (очевидно, все ключи в [math]T_{1}[/math] меньше ключей в [math]T'[/math], поэтому мы можем это сделать). Теперь в дереве [math]T_{1}[/math] у отца вершины, в которой мы остановились при поиске дерева [math]P[/math], правым поддеревом делаем дерево [math]K[/math] и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева [math]S[/math] (по ссылке, которую мы ранее запомнили) и обработать его.

Если мы пришли в поддерево [math]Q[/math], корень которого [math]\gt x[/math], совершаем аналогичные действия: делаем NULL'ами ссылки на корень [math]Q[/math], запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины [math]Q[/math] и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее [math]T_{2}[/math] аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево [math]T_{2}[/math].

Рассмотри пример (рис. [math]1[/math]). Цветом выделены поддеревья, которые после разделения должны отойти в дерево [math]T_{1}[/math]. [math]x = 76[/math].

Рис. 1. Разделение АВЛ-дерева на два.

Корень дерева [math]\leqslant x[/math], поэтому он со всем выделенным поддеревом должен отойти в дерево [math]T_{1}[/math]. По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево [math]T'[/math] (рис. [math]2[/math]). Так как это первая ситуация, в которой корень рассматриваемого поддерева был [math]\leqslant x[/math], [math]T'[/math] становится [math]T_{1}[/math]. Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень [math]\gt x[/math]. Следовательно, строим из него и его правого поддерева [math]T_{2}[/math] и спускаемся в левое поддерево. Снова корень [math]\leqslant x[/math]. Строим новое [math]T'[/math] и объединяем его с уже существующим [math]T_{1}[/math] (рис. [math]3[/math]).

Рис. 2. Создание T'. Рис. 3. Объединение T' и T1.

Далее действуем по алгоритму и в итоге получаем (рис. [math]4[/math]):

Рис. 4. АВЛ-деревья после разделения.

Данный алгоритм имеет сложность [math]O(\log^{2} n)[/math]. Рассмотрим решение, которое имеет сложность [math]O(\log{n})[/math].

Вернемся к примеру (рис. [math]1[/math]). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья [math]T_{1}[/math] и [math]T_{2}[/math], передавая наверх корректные АВЛ-деревья. То есть для рис. [math]1[/math] первым в дерево [math]T_{1}[/math] придет вершина [math]75[/math] с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением [math]70[/math] и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.

Алгоритм построения следующий: пусть мы пришли в поддерево [math]S[/math] с корнем [math]\leqslant x[/math]. Тогда сольем его с уже построенным на тот момент [math]T_{1}[/math] ([math]T_{1}[/math] пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, [math]S \leqslant T_{1}[/math] и [math]h(T_{1}) \leqslant h(S)[/math]). Но так как обычная процедура слияния сливает два АВЛ-дерева, а [math]S[/math] не является корректным АВЛ-деревом, мы немного ее изменим.