Обсуждение участницы:Анна

Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного 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]T_{1}[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math]). Для этого мы ищем в дереве [math]T_{1}[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]tmpT[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math], сливая [math]P[/math] и [math]tmpT[/math] (очевидно, все ключи в [math]T_{1}[/math] меньше ключей в [math]P[/math], поэтому мы можем это сделать). Теперь в дереве [math]T_{1}[/math] у отца вершины, в которой мы остановились при поиске дерева [math]P[/math], правым поддеревом делаем дерево [math]K[/math] и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева [math]S[/math] (по ссылке, которую мы ранее запомнили) и обработать его.