Hi,
I want to know how to merge two AVL trees where elements of the first tree is smaller than all elements of second AVL tree how can I do that in O(log N) of course preserving the balance factor .
aslo how to split one AVL tree into two AVL trees where elements of the first is less than or equal K and elements of the second AVL tree is bigger than K also with preserving the balance factor.
thanks for helping me.
Очень извиняюсь за комментарий на русском языке, боюсь что на английском напишу слишком плохо. Может кто переведет на английский. Возьмем корневую вершину дерева с меньшими элементами. Добавим к ней в качестве левого поддерева дерево с меньшими элементами, в качестве правого — дерево с большими элементами. Проведем операцию удаления одной вершины (корневой) — это стоит O(log n)
Представьте, что в меньшем дереве 1000 элементов, а в большем — один. Тогда нарушится инвариант и не факт, что операция удаления его чудом восстановит.
В сбалансированном АВЛ дереве (которое дано нам по условию), в правом поддереве от корневой вершины один элемент, а в левом 1000? :) Это нарушает определение сбалансированного АВЛ дерева. При разделении сбалансированного АВЛ дерева относительно корня мы получим два сбалансированных АВЛ дерева исходя из определения сбалансированного АВЛ дерева.
// Упс, меня переклинило по-полной. Конечно-же начальные два дерева могут быть разными по размеру.
А если пробежимся по крайним левым узлам дерева с большими элементами, и проведем такую-же операцию (замену на корень меньшего дерева и т.д.) с узлом имеющим поддерево такой-же высоты, как меньшее дерево? Это если в меньшем (с меньшими значениями) дереве элементов меньше чем в большем. И наоборот, пробежимся по правым узлам меньшего дерева, если в нем элементов больше.
Разделение аналогично. Находим в дереве максимальный элемент меньший либо равный к, Всё поддерево с этим узлом — это меньшее дерево. А в большем дереве заменяем родительский узел от найденного элемента на его правое поддерево (на правый узел), и проводим операцию добавления родительского узла.
Добавлено. При замене (удалении) родительского узла, перед его последующем добавлением, вроде нужно сделать операцию балансировки.
Хотя делить так не выйдет. Процедуру отбора левых поддеревьев надо запускать несколько раз (с последующим слиянием с уже полученным маленьким деревом за логарифм), пока не выберем все меньшие к поддеревья, и общая сложность вроде получается log^2
Придумал. Для разделения смотрим корневую вершину. Если она меньше либо равна к, то отделять будем поддерево с элементами больше к, если больше к, то отделим дерево с элементами меньше либо равными к.
Пример отделения поддерева с элементами меньше либо равными к. Спускаясь от корня, по левым ветвям, находим первый элемент меньше либо равный к, отделяем его левое поддерево, заменяем его на вершину правого поддерева, балансируем, сам этот элемент добавляем к дереву с маленькими элементами, затем продолжаем процедуру поиска элементов меньших либо равных к начиная с корня. Найдя опять элемент меньший к — повторяем операцию отделения поддерева с маленькими элементами, добавляем его к уже существующему дереву с маленькими элементами (за логарифм, операцией слияния большого и маленького поддерева, так все элементы нового поддерева больше элементов уже собранного дерева с маленькими элементами) и т.д. Сложность O(log^2) Так как каждый раз мы отделяем как минимум половину элементов меньших либо равных к, количество операций отделения будет логарифм, а каждая операция отделения — О(log)
Good question. I will learn it and give a solution.
Here is the solution: https://i.cs.hku.hk/~provinci/training2016/AVL/Main.java
Good work Sir but next time, check when the blog was posted. It is 4 years old :) I'm sure kingofnumbers now knows how to do it!
but but .. it could be helpful to others ;):)