Рубрики

Объединение двух сбалансированных бинарных поисковых деревьев

Вам даны два сбалансированных бинарных дерева поиска, например, AVL или Red Black Tree. Напишите функцию, которая объединяет два заданных сбалансированных BST в сбалансированное двоичное дерево поиска. Пусть будет m элементов в первом дереве и n элементов в другом дереве. Ваша функция слияния должна занять O (m + n) время.

В следующих решениях предполагается, что размеры деревьев также приведены в качестве входных данных. Если размер не указан, то мы можем получить размер, пройдя по дереву (см. Это ).

Метод 1 (Вставка элементов первого дерева во второе)
Возьмите все элементы первого BST по одному и вставьте их во второй BST. Вставка элемента в самобалансировани BST занимает LogN времени (см это ) где п размер BST. Таким образом, временная сложность этого метода составляет Log (n) + Log (n + 1)… Log (m + n-1). Значение этого выражения будет между mLogn и mLog (m + n-1). В качестве оптимизации мы можем выбрать меньшее дерево в качестве первого.

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

Временная сложность этого метода составляет O (m + n), что лучше, чем метод 1. Этот метод занимает время O (m + n), даже если входные BST не сбалансированы.
Ниже приведена реализация этого метода.

C ++

// C ++ программа для объединения двух сбалансированных деревьев бинарного поиска
#include<bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка
и указатель на правого ребенка * /

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
// Утилита unction для объединения двух отсортированных массивов в один

int *merge(int arr1[], int arr2[], int m, int n); 

  
// Вспомогательная функция, которая хранит порядок
// обход дерева в массиве inorder

void storeInorder(node* node, int inorder[],

                            int *index_ptr); 

  
/ * Функция, которая создает Balanced
Двоичное дерево поиска из отсортированного массива
См. Https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/amp/ * /

node* sortedArrayToBST(int arr[], int start, int end); 

  
/ * Эта функция объединяет два сбалансированных
BST с корнями как root1 и root2.
m и n - размеры деревьев соответственно * /

node* mergeTrees(node *root1, 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); 

  
/ * Вспомогательная функция, которая выделяет
новый узел с заданными данными и
NULL левый и правый указатели. * /

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

  

    return(Node); 

  
// Полезная функция для печати заказа
// обход заданного двоичного дерева

void printInorder(node* node) 

    if (node == NULL) 

        return

  

    / * первый рецидив на левом ребенке * /

    printInorder(node->left); 

  

    cout << node->data << " "

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder(node->right); 

  
// Утилита unction для слияния
// два отсортированных массива в один

int *merge(int arr1[], int arr2[], int m, int n) 

    // mergedArr [] будет содержать результат

    int *mergedArr = new int[m + n]; 

    int i = 0, j = 0, k = 0; 

  

    // пройти через оба массива

    while (i < m && j < n) 

    

        // Выберите элемент smaler и поместите его в 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; 

  
// Вспомогательная функция, которая хранит порядок
// обход дерева с узлом

void storeInorder(node* node, int inorder[], int *index_ptr) 

    if (node == NULL) 

        return

  

    / * первый рецидив на левом ребенке * /

    storeInorder(node->left, inorder, index_ptr); 

  

    inorder[*index_ptr] = node->data; 

    (*index_ptr)++; // увеличиваем индекс для следующей записи

  

    / * теперь возвращаемся на правильного ребенка * /

    storeInorder(node->right, inorder, index_ptr); 

  
/ * Функция, которая создает Balanced
// Двоичное дерево поиска из отсортированного массива
См. Https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/amp/ * /

node* sortedArrayToBST(int arr[], int start, int end) 

    /* Базовый вариант */

    if (start > end) 

    return NULL; 

  

    / * Получить средний элемент и сделать его корневым * /

    int mid = (start + end)/2; 

    node *root = newNode(arr[mid]); 

  

    / * Рекурсивно сконструировать левое поддерево и сделать его

    левый потомок корня * /

    root->left = sortedArrayToBST(arr, start, mid-1); 

  

    / * Рекурсивно построить правильное поддерево и сделать его

    правый потомок корня * /

    root->right = sortedArrayToBST(arr, mid+1, end); 

  

    return root; 

  
/ * Код водителя * /

int main() 

    / * Создать следующее дерево как первый сбалансированный BST

        100

        / /

        50 300

    / /

    20 70

    * /

    node *root1 = newNode(100); 

    root1->left     = newNode(50); 

    root1->right = newNode(300); 

    root1->left->left = newNode(20); 

    root1->left->right = newNode(70); 

  

    / * Создать следующее дерево как второй сбалансированный BST

            80

        / /

        40 120

    * /

    node *root2 = newNode(80); 

    root2->left     = newNode(40); 

    root2->right = newNode(120); 

  

    node *mergedTree = mergeTrees(root1, root2, 5, 3); 

  

    cout << "Following is Inorder traversal of the merged tree \n"

    printInorder(mergedTree); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Программа C для объединения двух сбалансированных деревьев двоичного поиска
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  
// Утилита unction для объединения двух отсортированных массивов в один

int *merge(int arr1[], int arr2[], int m, int n);

  
// Вспомогательная функция, которая хранит обход дерева по порядку в массиве по порядку

void storeInorder(struct node* node, int inorder[], int *index_ptr);

  
/ * Функция, которая создает сбалансированное дерево двоичного поиска из отсортированного массива

   См. Https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/amp/ * /

struct node* sortedArrayToBST(int arr[], int start, int end);

  
/ * Эта функция объединяет два сбалансированных BST с корнями как 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);

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct node* newNode(int data)

{

    struct node* node = (struct node*)

                        malloc(sizeof(struct node));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

  

    return(node);

}

  
// Утилита для печати обхода заданного двоичного дерева

void printInorder(struct node* node)

{

    if (node == NULL)

        return;

  

    / * первый рецидив на левом ребенке * /

    printInorder(node->left);

  

    printf("%d ", node->data);

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder(node->right);

}

  
// Утилита unction для объединения двух отсортированных массивов в один

int *merge(int arr1[], int arr2[], int m, int n)

{

    // mergedArr [] будет содержать результат

    int *mergedArr = new int[m + n];

    int i = 0, j = 0, k = 0;

  

    // пройти через оба массива

    while (i < m && j < n)

    {

        // Выберите элемент smaler и поместите его в 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;

}

  
// Вспомогательная функция, которая хранит обход по порядку дерева с корнем в узле

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)++;  // увеличиваем индекс для следующей записи

  

    / * теперь возвращаемся на правильного ребенка * /

    storeInorder(node->right, inorder, index_ptr);

}

  
/ * Функция, которая создает сбалансированное дерево двоичного поиска из отсортированного массива

   См. Https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/amp/ * /

struct node* sortedArrayToBST(int arr[], int start, int end)

{

    /* Базовый вариант */

    if (start > end)

      return NULL;

  

    / * Получить средний элемент и сделать его корневым * /

    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;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    / * Создать следующее дерево как первый сбалансированный BST

           100

          / /

        50 300

       / /

      20 70

    * /

    struct node *root1  = newNode(100);

    root1->left         = newNode(50);

    root1->right        = newNode(300);

    root1->left->left   = newNode(20);

    root1->left->right  = newNode(70);

  

    / * Создать следующее дерево как второй сбалансированный BST

            80

           / /

         40 120

    * /

    struct node *root2  = newNode(80);

    root2->left         = newNode(40);

    root2->right        = newNode(120);

  

    struct node *mergedTree = mergeTrees(root1, root2, 5, 3);

  

    printf ("Following is Inorder traversal of the merged tree \n");

    printInorder(mergedTree);

  

    getchar();

    return 0;

}

Джава

// Java-программа для объединения двух сбалансированных деревьев двоичного поиска

import java.io.*;

import java.util.ArrayList;

  
// Узел двоичного дерева

class Node {

      

    int data;

    Node left, right;

      

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class BinarySearchTree

{

      

    // Корень BST

    Node root;

  

    // Конструктор

    BinarySearchTree() { 

        root = null

    }

      

    // По обходу дерева

    void inorder()

    {

        inorderUtil(this.root);

    }

      
// Сервисная функция для обхода дерева по порядку

void inorderUtil(Node node)

{

    if(node==null)

        return;

          

    inorderUtil(node.left);

    System.out.print(node.data + " ");

    inorderUtil(node.right);

}

      

  

    // Служебный метод, который хранит обход дерева по порядку

    public ArrayList<Integer> storeInorderUtil(Node node, ArrayList<Integer> list)

    {

        if(node == null)

            return list;

          

        // возвращаемся слева

        storeInorderUtil(node.left, list);

          

        // Добавляет данные в список

        list.add(node.data);

          

        // вернемся к правильному ребенку

        storeInorderUtil(node.right, list);

          

        return list;

    }

      

    // Метод, который хранит обход дерева по порядку

    ArrayList<Integer> storeInorder(Node node)

    {

        ArrayList<Integer> list1 = new ArrayList<>(); 

        ArrayList<Integer> list2 = storeInorderUtil(node,list1); 

        return list2;

    }

  

    // Метод, который объединяет два ArrayLists в один.

    ArrayList<Integer> merge(ArrayList<Integer>list1, ArrayList<Integer>list2, int m, int n)

    {

        // list3 будет содержать слияние list1 и list2

        ArrayList<Integer> list3 = new ArrayList<>();

        int i=0;

        int j=0;

          

        // Обход через оба ArrayLists

        while( i<m && j<n)

        {

            // Меньший входит в list3

            if(list1.get(i)<list2.get(j))

            {

                list3.add(list1.get(i));

                i++;

            }

            else

            {

                list3.add(list2.get(j));

                j++;

            }

        }

          

        // Добавляет остальные элементы list1 в list3

        while(i<m)

        {

            list3.add(list1.get(i));

            i++;

        }

      

        // Добавляет остальные элементы list2 в list3

        while(j<n)

        {

            list3.add(list2.get(j));

            j++;

        }

        return list3;

    }

      

    // Метод, который преобразует ArrayList в BST

    Node ALtoBST(ArrayList<Integer>list, int start, int end)

    {

        // Базовый вариант

        if(start > end)

            return null;

      

        // Получить средний элемент и сделать его корневым

        int mid = (start+end)/2;

        Node node = new Node(list.get(mid));

  

        / * Рекурсивно сконструировать левое поддерево и сделать его

        левый потомок корня * /

        node.left = ALtoBST(list, start, mid-1);

          

        / * Рекурсивно построить правильное поддерево и сделать его

        правый потомок корня * /

        node.right = ALtoBST(list, mid+1, end);

      

    return node;

    }

      

    // Метод, который объединяет два дерева в одно.

    Node mergeTrees(Node node1, Node node2)

    {

        // Сохраняет порядок дерева tree1 в list1

        ArrayList<Integer>list1 = storeInorder(node1);

          

        // Сохраняет порядок дерева tree2 в list2

        ArrayList<Integer>list2 = storeInorder(node2);

          

        // Объединяет list1 и list2 в list3

        ArrayList<Integer>list3 = merge(list1, list2, list1.size(), list2.size());

          

        // В конечном итоге преобразует объединенный список в результирующий BST

        Node node = ALtoBST(list3, 0, list3.size()-1);

        return node;

    }

  

    // Функция драйвера

    public static void main (String[] args)

    {

          

        / * Создание следующего дерева как Первый сбалансированный BST

                100

                / /

                50 300

                / /

               20 70

        * /

          

        BinarySearchTree tree1 = new BinarySearchTree();

        tree1.root = new Node(100);

        tree1.root.left = new Node(50);

        tree1.root.right = new Node(300);

        tree1.root.left.left = new Node(20);

        tree1.root.left.right = new Node(70);

          

        / * Создание следующего дерева в качестве второго сбалансированного BST

                80

                / /

              40 120

        * /

              

        BinarySearchTree tree2 = new BinarySearchTree();

        tree2.root = new Node(80);    

        tree2.root.left = new Node(40);

        tree2.root.right = new Node(120);

              

              

        BinarySearchTree tree = new BinarySearchTree();    

        tree.root = tree.mergeTrees(tree1.root, tree2.root);

        System.out.println("The Inorder traversal of the merged BST is: ");

        tree.inorder();

    }

}
// Этот код предоставлен Камалем Равалом

C #

// C # программа для объединения двух сбалансированных деревьев двоичного поиска

using System;

using System.Collections.Generic;

  
// Узел двоичного дерева

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinarySearchTree

{

  

    // Корень BST

    public Node root;

  

    // Конструктор

    public BinarySearchTree()

    {

        root = null;

    }

  

    // По обходу дерева

    public virtual void inorder()

    {

        inorderUtil(this.root);

    }

  
// Сервисная функция для обхода дерева по порядку

public virtual void inorderUtil(Node node)

{

    if (node == null)

    {

        return;

    }

  

    inorderUtil(node.left);

    Console.Write(node.data + " ");

    inorderUtil(node.right);

}

  

  

    // Служебный метод, который хранит обход дерева по порядку

    public virtual List<int> storeInorderUtil(Node node, List<int> list)

    {

        if (node == null)

        {

            return list;

        }

  

        // возвращаемся слева

        storeInorderUtil(node.left, list);

  

        // Добавляет данные в список

        list.Add(node.data);

  

        // вернемся к правильному ребенку

        storeInorderUtil(node.right, list);

  

        return list;

    }

  

    // Метод, который хранит обход дерева по порядку

    public virtual List<int> storeInorder(Node node)

    {

        List<int> list1 = new List<int>();

        List<int> list2 = storeInorderUtil(node,list1);

        return list2;

    }

  

    // Метод, который объединяет два ArrayLists в один.

    public virtual List<int> merge(List<int> list1, List<int> list2, int m, int n)

    {

        // list3 будет содержать слияние list1 и list2

        List<int> list3 = new List<int>();

        int i = 0;

        int j = 0;

  

        // Обход через оба ArrayLists

        while (i < m && j < n)

        {

            // Меньший входит в list3

            if (list1[i] < list2[j])

            {

                list3.Add(list1[i]);

                i++;

            }

            else

            {

                list3.Add(list2[j]);

                j++;

            }

        }

  

        // Добавляет остальные элементы list1 в list3

        while (i < m)

        {

            list3.Add(list1[i]);

            i++;

        }

  

        // Добавляет остальные элементы list2 в list3

        while (j < n)

        {

            list3.Add(list2[j]);

            j++;

        }

        return list3;

    }

  

    // Метод, который преобразует ArrayList в BST

    public virtual Node ALtoBST(List<int> list, int start, int end)

    {

        // Базовый вариант

        if (start > end)

        {

            return null;

        }

  

        // Получить средний элемент и сделать его корневым

        int mid = (start + end) / 2;

        Node node = new Node(list[mid]);

  

        / * Рекурсивно сконструировать левое поддерево и сделать его

        левый потомок корня * /

        node.left = ALtoBST(list, start, mid - 1);

  

        / * Рекурсивно построить правильное поддерево и сделать его

        правый потомок корня * /

        node.right = ALtoBST(list, mid + 1, end);

  

    return node;

    }

  

    // Метод, который объединяет два дерева в одно.

    public virtual Node mergeTrees(Node node1, Node node2)

    {

        // Сохраняет порядок дерева tree1 в list1

        List<int> list1 = storeInorder(node1);

  

        // Сохраняет порядок дерева tree2 в list2

        List<int> list2 = storeInorder(node2);

  

        // Объединяет list1 и list2 в list3

        List<int> list3 = merge(list1, list2, list1.Count, list2.Count);

  

        // В конечном итоге преобразует объединенный список в результирующий BST

        Node node = ALtoBST(list3, 0, list3.Count - 1);

        return node;

    }

  

    // Функция драйвера

    public static void Main(string[] args)

    {

  

        / * Создание следующего дерева как Первый сбалансированный BST

                100

                / /

                50 300

                / /

               20 70

        * /

  

        BinarySearchTree tree1 = new BinarySearchTree();

        tree1.root = new Node(100);

        tree1.root.left = new Node(50);

        tree1.root.right = new Node(300);

        tree1.root.left.left = new Node(20);

        tree1.root.left.right = new Node(70);

  

        / * Создание следующего дерева в качестве второго сбалансированного BST

                80

                / /

              40 120

        * /

  

        BinarySearchTree tree2 = new BinarySearchTree();

        tree2.root = new Node(80);

        tree2.root.left = new Node(40);

        tree2.root.right = new Node(120);

  

  

        BinarySearchTree tree = new BinarySearchTree();

        tree.root = tree.mergeTrees(tree1.root, tree2.root);

        Console.WriteLine("The Inorder traversal of the merged BST is: ");

        tree.inorder();

    }

}

  

  // Этот код предоставлен Shrikant13

Выход:

Following is Inorder traversal of the merged tree
20 40 50 70 80 100 120 300

Метод 3 (Слияние на месте с использованием DLL)
Мы можем использовать двусвязный список для объединения деревьев на месте. Ниже приведены шаги.

1) Преобразуйте указанные два дерева бинарного поиска в дважды связанный список (см. Этот пост для этого шага).
2) Объединить два отсортированных связанных списка (см. Этот пост для этого шага).
3) Создайте сбалансированное дерево двоичного поиска из объединенного списка, созданного на шаге 2. (см. Этот пост для этого шага)

Временная сложность этого метода также составляет O (m + n), и этот метод выполняет преобразование на месте.

Спасибо Dheeraj и Ronzii за предложение этого метода.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Объединение двух сбалансированных бинарных поисковых деревьев

0.00 (0%) 0 votes