Обсуждение участницы:Анна
Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше
Пусть у нас есть дерево . Мы должны разбить его на два дерева и такие, что и .
Предположим, что корень нашего дерева , в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево . Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи ). Если же корень оказался , то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.
Пусть мы пришли в поддерево , корень которого . В таком случае этот корень со своим левым поддеревом должен отойти в дерево . Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево , удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево ). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины и запускаем балансировку. Обозначим полученное дерево за . Теперь нам нужно объединить его с уже построенным ранее (оно может быть пустым, если мы первый раз нашли такое дерево ). Для этого мы ищем в дереве самое правое поддерево высоты, равной высоте (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево , сливая и (очевидно, все ключи в меньше ключей в , поэтому мы можем это сделать). Теперь в дереве у отца вершины, в которой мы остановились при поиске дерева , правым поддеревом делаем дерево и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева (по ссылке, которую мы ранее запомнили) и обработать его.
Если мы пришли в поддерево , корень которого , совершаем аналогичные действия: делаем NULL'ами ссылки на корень , запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево .
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево . .
Корень дерева , поэтому он со всем выделенным поддеревом должен отойти в дерево . По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был , становится . Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень . Следовательно, строим из него и его правого поддерева и спускаемся в левое поддерево. Снова корень . Строим новое и объединяем его с уже существующим (рис. 3).
Далее действуем по алгоритму и в итоге получаем (рис. 4):
Данный алгоритм имеет сложность . Рассмотрим решение, которое имеет сложность .
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья и , передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево придет вершина с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.
Пусть мы пришли в поддерево с корнем . Тогда сольем его с уже построенным на тот момент ( пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, и ). Но так как обычная процедура слияния сливает два АВЛ-дерева, а не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве нашли самое правое поддерево , высота которого равна высоте . Тогда сделаем новое дерево , корнем которого будет вершина (без нее это дерево является сбалансированным), правым поддеревом — , левым — . И подвесим на то место, где мы остановились при поиске . Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, , все аналогично.
Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла . Ключ больше , поэтому эта вершина станет деревом и передастся наверх. Теперь мы поднялись в узел . Он со своим левым поддеревом станет деревом и мы снова поднимемся наверх в узел . Он со своим левым поддеревом снова должен отойти в дерево , и так как теперь дерево уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)
После мы поднимемся в вершину с ключом . Она с правым поддеревом отойдет в дерево (рис. 6).
И на последней итерации мы поднимемся в корень дерева с ключом , он с левым поддеревом отойдет в дерево , после чего алгоритм завершится.
Пусть поддеревьев с ключами оказалось больше, чем поддеревьев с ключами . Докажем для них логарифмическую асимптотику. Мы запускаем балансировку от высот деревьев , где - высоты поддеревьев, которые мы вставили и после которых должны произвести балансировку. Дерево на последнем уровне имеет высоту (она может быть не равна , если мы придём в ). Его мы передаем наверх и вставляем в поддерево высотой .
Поэтому асимптотика алгоритма .
