Вопрос 20. Алгоритм реализации двуместной операции с АВЛ-деревьями: схема слияния с использованием массивов ссылок на узлы дерева.

1. Выполнить обход первого дерева и сохранить элементы обхода во временный массив arr1[]. Это займет время $O(m)$.
2. Выполнить обход второго дерева и сохранить элементы обхода во временный массив arr2[]. Это займет время $O(n)$.
3. Массивы полученные в 1. и 2. отсортированны их следует объединить в один массив, это займет время $O(m + n)$.
4. Построить сбалансированное АВЛ дерево по полученному массиву.

Временная сложность алгоритма будет $O(2(m + n) + \log_2 (m + n)$).

/* Узел двоичного дерева имеет данные, указатель на левое дерево
    и указатель на правое дерево */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

// Функция утилиты для объединения двух отсортированных массивов в один
int *merge(int arr1[], int arr2[], int m, int n);

// Вспомогательная функция, которая хранит обход дерева в массиве inorder
void storeInorder(struct node* node, int inorder[], int *index_ptr);

// Функция, которая строит сбалансированное двоичное дерево поиска из отсортированного массива
struct node* sortedArrayToBST(int arr[], int start, int end);

/* Эта функция объединяет два сбалансированных дерева с корнями как root1 и root2.
    M и n - размеры деревьев соответственно */
struct node* mergeTrees(struct node *root1, struct node *root2, int m, int n)
{
    // получаем элементы из первого дерева arr1[]
    int *arr1 = new int[m];
    int i = 0;
    storeInorder(root1, arr1, &i);

    // получаем элементы из второго дерева arr2[]
    int *arr2 = new int[n];
    int j = 0;
    storeInorder(root2, arr2, &j);

    // объединяем массивы
    int *mergedArr = merge(arr1, arr2, m, n);

    // строим и возвращаем новое дерево
    return sortedArrayToBST (mergedArr, 0, m+n-1);
}

/* Вспомогательная функция, которая выделяет новый узел с помощью
    Данных и nullptr левый и nullptr правый указатели.*/
struct node* newNode(int data)
{
    struct node* node = new (struct node);
    node->data = data;
    node->left = nullptr;
    node->right = nullptr;

    return(node);
}

// слияние двух отсортированных массивов
int *merge(int arr1[], int arr2[], int m, int n)
{
    // результирующий массив
    int *mergedArr = new int[m + n];
    int i = 0, j = 0, k = 0;

    // Пройдите через оба массива
    while (i < m && j < n)
    {
        // Выберите меньший элемент и поместите его в mergedArr
        if (arr1[i] < arr2[j])
        {
            mergedArr[k] = arr1[i];
            i++;
        }
        else
        {
            mergedArr[k] = arr2[j];
            j++;
        }
        k++;
    }

    // Если в первом массиве больше элементов
    while (i < m)
    {
        mergedArr[k] = arr1[i];
        i++; k++;
    }

    // Если во втором массиве больше элементов
    while (j < n)
    {
        mergedArr[k] = arr2[j];
        j++; k++;
    }

    return mergedArr;
}

// вспомогательная функция, которая сохраняет элементы обхода в inorder
void storeInorder(struct node* node, int inorder[], int *index_ptr)
{
    if (node == NULL)
        return;

    /* Сначала повторить на левом дереве */
    storeInorder(node->left, inorder, index_ptr);

    inorder[*index_ptr] = node->data;
    (*index_ptr)++;  // increase index for next entry

    /* потом на правом */
    storeInorder(node->right, inorder, index_ptr);
}

/* Функция, которая строит сбалансированное двоичное дерево поиска из отсортированного массива */
struct node* sortedArrayToBST(int arr[], int start, int end)
{
    if (start > end)
      return NULL;

    /* Получить средний элемент и сделать его root */
    int mid = (start + end)/2;
    struct node *root = newNode(arr[mid]);

    /* Рекурсивно построить левое поддерево */
    root->left =  sortedArrayToBST(arr, start, mid-1);

    /* рекурсивно построить правое поддерево */
    root->right = sortedArrayToBST(arr, mid+1, end);

    return root;
}