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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше)
(Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше)
Строка 4: Строка 4:
 
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.
 
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.
  
Пусть мы пришли в поддерево, корень которого <tex>\leqslant x</tex>. В таком случае этот корень с левым поддеревом должен отойти в дерево <tex>T_{1}</tex>.Поэтому мы делаем следующее: удаляем корень, запоминая его значение. Таким образом мы имеем сбалансированное АВЛ-дерево (бывшее левое поддерево). Делаем новую вершину со значением бывшего корня правым листом самого правого листа и запускаем балансировку. Обозначим полученное дерево за <tex>tmpT</tex>.Если это было первое поддерево, у которого корень был <tex>\leqslant x</tex>, то больше мы ничего не делаем, это и есть <tex>T_{1}</tex>. Иначе нам нужно объединить его с уже построенным <tex>T_{1}</tex>. Для этого мы ищем в дереве <tex>T_{1}</tex> самое правое поддерево высоты, равной высоте <tex>tmpT</tex>.
+
Пусть мы пришли в поддерево <tex>S</tex>, корень которого <tex>\leqslant x</tex>. В таком случае этот корень со своим левым поддеревом должен отойти в дерево <tex>T_{1}</tex>. Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево <tex>S</tex>, удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'ами). Таким образом мы имеем сбалансированное АВЛ-дерево (бывшее левое поддерево <tex>S</tex>). Делаем новую вершину со значением бывшего корня правым листом самого правого листа <tex>S</tex> и запускаем балансировку. Обозначим полученное дерево за <tex>tmpT</tex>.Если это было первое поддерево, у которого корень был <tex>\leqslant x</tex>, то больше мы ничего не делаем, это и есть <tex>T_{1}</tex>. Иначе нам нужно объединить его с уже построенным <tex>T_{1}</tex>. Для этого мы ищем в дереве <tex>T_{1}</tex> самое правое поддерево высоты, равной высоте <tex>tmpT</tex>. Отде

Версия 21:00, 17 мая 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]tmpT[/math].Если это было первое поддерево, у которого корень был [math]\leqslant x[/math], то больше мы ничего не делаем, это и есть [math]T_{1}[/math]. Иначе нам нужно объединить его с уже построенным [math]T_{1}[/math]. Для этого мы ищем в дереве [math]T_{1}[/math] самое правое поддерево высоты, равной высоте [math]tmpT[/math]. Отде