Изменения

Перейти к: навигация, поиск

АВЛ-дерево

37 байт убрано, 19:27, 24 марта 2012
Слияние двух AVL-деревьев
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
==Слияние двух AVL-деревьев==
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>. В дереве <tex>T_1</tex> [[#Удаление вершины|удаляем]] самую правую вершину, назовём её <tex>a</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_2</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>a</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.
== Литература ==
Анонимный участник

Навигация