Слияние деревьев AVL с использованием пустого дерева (шаблоны C ++)

Question

Как часть шаблона AVL, над которым я работаю (шаблоны C ++), я пытался объединить 2 дерева AVL в сложности O (n1 + n2), когда n1 + n2 - это общее количество элементов в обоих деревьях.

Я думал о следующем алгоритме.

1. Порядок обхода первого дерева и построение массива / списка - O (n1)
2. Порядок обхода второго дерева и построение массива / списка - O (n2)
3. Объединить сортировку этих двух массивов и создать окончательный отсортированный массив / список размером n1 + n2 - O (n1 + n2)
4. Построить пустое почти полное двоичное дерево с n1 + n2 вершинами - O (n1 + n2).
5. Порядок обхода этого почти полного двоичного дерева при обновлении вершин с помощью элементов в объединенном массиве / списке.

У меня вопрос, как мне на самом деле построить пустое почти полное двоичное дерево с n1 + n2 вершинами ?

Answer 1

Если узлы, выдаваемые сортировкой слиянием, хранятся в векторе, это можно сделать относительно легко. Ваши узлы уже отсортированы, поэтому вы можете «вставить» узлы следующим образом:

1. Создайте свой корневой узел из элемента на 1/2 массива;
2. Построить дочерние узлы корня, используя элементы в 1/4 и 3/4 массива;
3. Рекурсивно повторить 2.

Это должно восприниматься вами как упорядоченный обход двоичного дерева, которое представляется в виде отсортированного массива.

Обратите внимание, что для этого вам нужно построить дерево с балансировкой "выключено". Скорее всего, это потребует от вас сделать это закрытым методом вашего класса, возможно, специальным конструктором.