Слияние 2 деревьев бинарного поиска

Question

Как объединить 2 дерева двоичного поиска таким образом, чтобы результирующее дерево содержало все элементы обоих деревьев, а также поддерживало свойство BST.

Я видел решение, представленное в Какэффективно объединить два BST?

Однако это решение включает в себя преобразование в двойной связанный список.Мне было интересно, если есть более элегантный способ сделать это, что можно было бы сделать на месте без преобразования.Я придумал следующий псевдокод.Это работает для всех случаев?Также у меня проблемы с 3-м случаем.

node* merge(node* head1, node* head2) {
        if (!head1)
            return head2;
        if (!head2)
            return head1;

        // Case 1.
        if (head1->info > head2->info) {
            node* temp = head2->right;
            head2->right = NULL;
            head1->left = merge(head1->left, head2);
            head1 = merge(head1, temp);
            return head1;
        } else if (head1->info < head2->info)  { // Case 2
            // Similar to case 1.
        } else { // Case 3
            // ...
        }
}

Answer 1

Два двоичных дерева поиска (BST) не могут быть объединены непосредственно во время рекурсивного обхода.Предположим, мы должны объединить дерево 1 и дерево 2, показанные на рисунке.

Рекурсия должна уменьшить объединение до более простой ситуации.Мы не можем уменьшить объединение только до соответствующих левых поддеревьев L1 и L2, потому что L2 может содержать числа больше 10, поэтому нам нужно будет включить в процесс правое поддерево R1.Но затем мы включаем числа больше 10 и, возможно, больше 20, поэтому нам нужно будет также включить правильное поддерево R2.Подобные рассуждения показывают, что мы не можем упростить объединение, включив поддеревья из дерева 1 и дерева 2 одновременно.

Единственная возможность сокращения - это упрощение только внутри соответствующих деревьев.Таким образом, мы можем преобразовать деревья в их правильные колючки с отсортированными узлами:

Теперь мы можем легко объединить два колючки в один.Этот позвоночник на самом деле BST, поэтому мы могли бы остановиться здесь.Однако этот BST полностью несбалансирован, поэтому мы преобразуем его в сбалансированный BST.

Сложность:

Spine 1: time = O(n1),    space = O(1) 
Spine 2: time = O(n2),    space = O(1) 
Merge:   time = O(n1+n2), space = O(1) 
Balance: time = O(n1+n2), space = O(1) 
Total:   time = O(n1+n2), space = O(1)

Полный рабочий код находится на http://ideone.com/RGBFQ. Вотосновные части.Код верхнего уровня:

Node* merge(Node* n1, Node* n2) {
    Node *prev, *head1, *head2;   
    prev = head1 = 0; spine(n1, prev, head1); 
    prev = head2 = 0; spine(n2, prev, head2);
    return balance(mergeSpines(head1, head2));
}

Вспомогательные функции для преобразования в шипы:

void spine(Node *p, Node *& prev, Node *& head) {   
    if (!p) return;   
    spine(p->left, prev, head);   
    if (prev) prev->right = p;   
    else head = p;  
    prev = p; 
    p->left = 0;  
    spine(p->right, prev, head); 
} 

Слияние шипов:

void advance(Node*& last, Node*& n) {
    last->right = n; 
    last = n;
    n = n->right; 
}

Node* mergeSpines(Node* n1, Node* n2) {
    Node head;
    Node* last = &head;
    while (n1 || n2) {
        if (!n1) advance(last, n2);
        else if (!n2) advance(last, n1);
        else if (n1->info < n2->info) advance(last, n1);
        else if (n1->info > n2->info) advance(last, n2);
        else {
            advance(last, n1);
            printf("Duplicate key skipped %d \n", n2->info);
            n2 = n2->right;
        }
    }
    return head.right; 
}

Балансировка:

Node* balance(Node *& list, int start, int end) {
    if (start > end) return NULL;  
    int mid = start + (end - start) / 2;    
    Node *leftChild = balance(list, start, mid-1);   
    Node *parent = list;
    parent->left = leftChild;   
    list = list->right;   
    parent->right = balance(list, mid+1, end);   
    return parent; 
}   

Node* balance(Node *head) {
    int size = 0;
    for (Node* n = head; n; n = n->right) ++size;
    return balance(head, 0, size-1); 
} 

Answer 2

Предполагая, что у нас есть два дерева A и B, мы вставляем корень дерева A в дерево B и с помощью вращений перемещаем вставленный корень, чтобы стать новым корнем дерева B. Затем мы рекурсивно объединяем левое и правое поддеревья деревьев A и B. Этот алгоритм учитывает структуру обоих деревьев, но вставка все еще зависит от того, насколько сбалансировано целевое дерево. Вы можете использовать эту идею для объединения двух деревьев во O(n+m) времени и O(1) пространстве.

---

Следующая реализация обусловлена ​​ Dzmitry Huba :

// Converts tree to sorted singly linked list and appends it
// to the head of the existing list and returns new head.
// Left pointers are used as next pointer to form singly
// linked list thus basically forming degenerate tree of
// single left oriented branch. Head of the list points
// to the node with greatest element.
static TreeNode<T> ToSortedList<T>(TreeNode<T> tree, TreeNode<T> head)
{
    if (tree == null)
        // Nothing to convert and append
        return head;
    // Do conversion using in order traversal
    // Convert first left sub-tree and append it to
    // existing list
    head = ToSortedList(tree.Left, head);
    // Append root to the list and use it as new head
    tree.Left = head;
    // Convert right sub-tree and append it to list
    // already containing left sub-tree and root
    return ToSortedList(tree.Right, tree);
}

// Merges two sorted singly linked lists into one and
// calculates the size of merged list. Merged list uses
// right pointers to form singly linked list thus forming
// degenerate tree of single right oriented branch.
// Head points to the node with smallest element.
static TreeNode<T> MergeAsSortedLists<T>(TreeNode<T> left, TreeNode<T> right, IComparer<T> comparer, out int size)
{
    TreeNode<T> head = null;
    size = 0;
    // See merge phase of merge sort for linked lists
    // with the only difference in that this implementations
    // reverts the list during merge
    while (left != null || right != null)
    {
        TreeNode<T> next;
        if (left == null)
            next = DetachAndAdvance(ref right);
        else if (right == null)
            next = DetachAndAdvance(ref left);
        else
            next = comparer.Compare(left.Value, right.Value) > 0
                        ? DetachAndAdvance(ref left)
                        : DetachAndAdvance(ref right);
        next.Right = head;
        head = next;
        size++;
    }
    return head;
}



static TreeNode<T> DetachAndAdvance<T>(ref TreeNode<T> node)
{
    var tmp = node;
    node = node.Left;
    tmp.Left = null;
    return tmp;
}

// Converts singly linked list into binary search tree
// advancing list head to next unused list node and
// returning created tree root
static TreeNode<T> ToBinarySearchTree<T>(ref TreeNode<T> head, int size)
{
    if (size == 0)
        // Zero sized list converts to null
        return null;

    TreeNode<T> root;
    if (size == 1)
    {
        // Unit sized list converts to a node with
        // left and right pointers set to null
        root = head;
        // Advance head to next node in list
        head = head.Right;
        // Left pointers were so only right needs to
        // be nullified
        root.Right = null;
        return root;
    }

    var leftSize = size / 2;
    var rightSize = size - leftSize - 1;
    // Create left substree out of half of list nodes
    var leftRoot = ToBinarySearchTree(ref head, leftSize);
    // List head now points to the root of the subtree
    // being created
    root = head;
    // Advance list head and the rest of the list will
    // be used to create right subtree
    head = head.Right;
    // Link left subtree to the root
    root.Left = leftRoot;
    // Create right subtree and link it to the root
    root.Right = ToBinarySearchTree(ref head, rightSize);
    return root;
}

public static TreeNode<T> Merge<T>(TreeNode<T> left, TreeNode<T> right, IComparer<T> comparer)
{
    Contract.Requires(comparer != null);

    if (left == null || right == null)
        return left ?? right;
    // Convert both trees to sorted lists using original tree nodes
    var leftList = ToSortedList(left, null);
    var rightList = ToSortedList(right, null);
    int size;
    // Merge sorted lists and calculate merged list size
    var list = MergeAsSortedLists(leftList, rightList, comparer, out size);
    // Convert sorted list into optimal binary search tree
    return ToBinarySearchTree(ref list, size);
}

Answer 3

Лучший способ объединить деревья - это что-то вроде:

For each node n in first BST {
    Go down the 2nd tree and find the appropriate place to insert n
    Insert n there
}

Каждая итерация в цикле for - это O (log n), так как мы имеем дело с деревьями, а цикл for будетповторить n раз, так что в сумме мы имеем O (n log n).

Answer 4

Этот пост в блоге предоставляет решение проблемы сложности O (logn) пространства. (Обратите внимание, что данный подход не изменяет входные деревья.)

Answer 5

BST - это упорядоченное или отсортированное двоичное дерево. Мой алгоритм был бы прост:

• пройти через оба дерева
• сравнить значения
• вставьте меньшее из двух в новый BST.

Код python для обхода выглядит следующим образом:

def traverse_binary_tree(node, callback):
    if node is None:
        return
    traverse_binary_tree(node.leftChild, callback)
    callback(node.value)
    traverse_binary_tree(node.rightChild, callback)

Стоимость обхода BST и построения нового объединенного BST останется O (n)

Answer 6

Это можно сделать за 3 шага:

1. преобразовать BST в отсортированный связанный список (это можно сделать за время O (m + n))
2. Объединить эти два отсортированных связанных списка в один список (это можно сделать за время O (m + n))
3. Преобразовать отсортированный связанный список в сбалансированный BST (это можно сделать с помощью O(m + n) время)

Answer 7

MergeTwoBST_to_BalancedBST.java

public class MergeTwoBST_to_BalancedBST {

// arr1 and arr2 are the input arrays to be converted into a binary search
// structure and then merged and then balanced.
int[] arr1 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
int[] arr2 = new int[] { 11, 12, 13, 14, 15, 16, 17, 18 };

BSTNode root1;
BSTNode root2;

// vector object to hold the nodes from the merged unbalanced binary search
// tree.
Vector<BSTNode> vNodes = new Vector<BSTNode>();

/**
 * Constructor to initialize the Binary Search Tree root nodes to start
 * processing. This constructor creates two trees from two given sorted
 * array inputs. root1 tree from arr1 and root2 tree from arr2.
 * 
 * Once we are done with creating the tree, we are traversing the tree in
 * inorder format, to verify whether nodes are inserted properly or not. An
 * inorder traversal should give us the nodes in a sorted order.
 */
public MergeTwoBST_to_BalancedBST() {
    // passing 0 as the startIndex and arr1.length-1 as the endIndex.
    root1 = getBSTFromSortedArray(arr1, 0, arr1.length - 1);
    System.out.println("\nPrinting the first binary search tree");
    inorder(root1); // traverse the tree in inorder format to verify whether
                    // nodes are inserted correctly or not.

    // passing 0 as the startIndex and arr2.length-1 as the endIndex.
    root2 = getBSTFromSortedArray(arr2, 0, arr2.length - 1);
    System.out.println("\nPrinting the second binary search tree");
    inorder(root2); // same here - checking whether the nodes are inserted
                    // properly or not.
}

/**
 * Method to traverse the tree in inorder format. Where it traverses the
 * left child first, then root and then right child.
 * 
 * @param node
 */
public void inorder(BSTNode node) {
    if (null != node) {
        inorder(node.getLeft());
        System.out.print(node.getData() + " ");
        inorder(node.getRight());
    }
}

/**
 * Method to traverse the tree in preorder format. Where it traverses the
 * root node first, then left child and then right child.
 * 
 * @param node
 */
public void preorder(BSTNode node) {
    if (null != node) {
        System.out.print(node.getData() + " ");
        preorder(node.getLeft());
        preorder(node.getRight());
    }
}

/**
 * Creating a new Binary Search Tree object from a sorted array and
 * returning the root of the newly created node for further processing.
 * 
 * @param arr
 * @param startIndex
 * @param endIndex
 * @return
 */
public BSTNode getBSTFromSortedArray(int[] arr, int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return null;
    }

    int middleIndex = startIndex + (endIndex - startIndex) / 2;
    BSTNode node = new BSTNode(arr[middleIndex]);
    node.setLeft(getBSTFromSortedArray(arr, startIndex, middleIndex - 1));
    node.setRight(getBSTFromSortedArray(arr, middleIndex + 1, endIndex));
    return node;
}

/**
 * This method involves two operation. First - it adds the nodes from root1
 * tree to root2 tree, and hence we get a merged root2 tree.Second - it
 * balances the merged root2 tree with the help of a vector object which can
 * contain objects only of BSTNode type.
 */
public void mergeTwoBinarySearchTree() {
    // First operation - merging the trees. root1 with root2 merging should
    // give us a new root2 tree.
    addUtil(root1);
    System.out.println("\nAfter the root1 tree nodes are added to root2");
    System.out.println("Inorder Traversal of root2 nodes");
    inorder(root2); // inorder traversal of the root2 tree should display
                    // the nodes in a sorted order.

    System.out.println("\nPreorder traversal of root2 nodes");
    preorder(root2);

    // Second operation - this will take care of balancing the merged binary
    // search trees.
    balancedTheMergedBST();
}

/**
 * Here we are doing two operations. First operation involves, adding nodes
 * from root2 tree to the vector object. Second operation involves, creating
 * the Balanced binary search tree from the vector objects.
 */
public void balancedTheMergedBST() {
    // First operation : adding nodes to the vector object
    addNodesToVector(root2, vNodes);
    int vSize = vNodes.size();

    // Second operation : getting a balanced binary search tree
    BSTNode node = getBalancedBSTFromVector(vNodes, 0, vSize - 1);
    System.out
            .println("\n********************************************************");
    System.out.println("After balancing the merged trees");
    System.out.println("\nInorder Traversal of nodes");
    inorder(node); // traversing the tree in inoder process should give us
                    // the output in sorted order ascending
    System.out.println("\nPreorder traversal of root2 nodes");
    preorder(node);
}

/**
 * This method will provide us a Balanced Binary Search Tree. Elements of
 * the root2 tree has been added to the vector object. It is parsed
 * recursively to create a balanced tree.
 * 
 * @param vNodes
 * @param startIndex
 * @param endIndex
 * @return
 */
public BSTNode getBalancedBSTFromVector(Vector<BSTNode> vNodes,
        int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return null;
    }

    int middleIndex = startIndex + (endIndex - startIndex) / 2;
    BSTNode node = vNodes.get(middleIndex);
    node.setLeft(getBalancedBSTFromVector(vNodes, startIndex,
            middleIndex - 1));
    node.setRight(getBalancedBSTFromVector(vNodes, middleIndex + 1,
            endIndex));

    return node;
}

/**
 * This method traverse the tree in inorder process and adds each node from
 * root2 to the vector object vNodes object only accepts objects of BSTNode
 * type.
 * 
 * @param node
 * @param vNodes
 */
public void addNodesToVector(BSTNode node, Vector<BSTNode> vNodes) {
    if (null != node) {
        addNodesToVector(node.getLeft(), vNodes);
        // here we are adding the node in the vector object.
        vNodes.add(node);
        addNodesToVector(node.getRight(), vNodes);
    }
}

/**
 * This method traverse the root1 tree in inorder process and add the nodes
 * in the root2 tree based on their value
 * 
 * @param node
 */
public void addUtil(BSTNode node) {
    if (null != node) {
        addUtil(node.getLeft());
        mergeToSecondTree(root2, node.getData());
        addUtil(node.getRight());
    }
}

/**
 * This method adds the nodes found from root1 tree as part it's inorder
 * traversal and add it to the second tree.
 * 
 * This method follows simple Binary Search Tree inserstion logic to insert
 * a node considering the tree already exists.
 * 
 * @param node
 * @param data
 * @return
 */
public BSTNode mergeToSecondTree(BSTNode node, int data) {

    if (null == node) {
        node = new BSTNode(data);
    } else {
        if (data < node.getData()) {
            node.setLeft(mergeToSecondTree(node.getLeft(), data));
        } else if (data > node.getData()) {
            node.setRight(mergeToSecondTree(node.getRight(), data));
        }
    }

    return node;
}

/**
 * 
 * @param args
 */
public static void main(String[] args) {
    MergeTwoBST_to_BalancedBST mergeTwoBST = new MergeTwoBST_to_BalancedBST();
    mergeTwoBST.mergeTwoBinarySearchTree();
  }
}

BSTNode.java:

public class BSTNode {

BSTNode left, right;
int data;

/* Default constructor */
public BSTNode() {
    left = null;
    right = null;
    data = 0;
}

/* Constructor */
public BSTNode(int data) {
    left = null;
    right = null;
    this.data = data;
}

public BSTNode getLeft() {
    return left;
}

public void setLeft(BSTNode left) {
    this.left = left;
}

public BSTNode getRight() {
    return right;
}

public void setRight(BSTNode right) {
    this.right = right;
}

public int getData() {
    return data;
}

public void setData(int data) {
    this.data = data;
  }
}

Answer 8

Предполагается, что вопрос состоит в том, чтобы просто распечатать отсортированные из обоих BST.Тогда более простой способ -

1. Сохранять обход по 2 BST в 2 отдельных массивах.
2. Теперь проблема сводится к объединению \ печати элементов из 2 отсортированных массивов, которые мы получили изпервый шаг.Это объединение может быть выполнено в o (m), когда m> n или o (n), когда m

Сложность: o (m + n) Вспомогательное пространство: o (m + n) для 2 массивов

Answer 9

Следующий алгоритм взят из Алгоритмы на C ++ .

Идея почти такая же, как в алгоритме, опубликованном PengOneЭтот алгоритм выполняет слияние на месте, сложность по времени составляет O (n + m).

link join(link a, link b) {
    if (b == 0) return a;
    if (a == 0) return b;
    insert(b, a->item);
    b->left = join(a->left, b->left);
    b->right = join(a->right, b->right);
    delete a;
    return b;
}

insert просто вставляет элемент в нужное место в дереве.rotateRight и rotateLeft держат дерево в правильном порядке.

void rotateRight(link &h) {
    link x = h->left;
    h->left = x->right;
    x->right = h;
    h = x;
}

void rotateLeft(link &h) {
    link x = h->right;
    h->right = x->left;
    x->left = h;
    h = x;
}

Здесь link равно node *.