合并2个二进制搜索树

Question

如何合并两个二进制搜索树，以使结果树包含这两个树的所有元素，并保持BST属性。

我看到了How to merge two BST's efficiently?中提供的解决方案

然而，该解决方案涉及到转换为双向链表。我想知道是否有一种更优雅的方法可以在没有转换的情况下就地完成。我想出了下面的伪代码。它对所有情况都有效吗？另外，我在第三个案例中遇到了麻烦。

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 )，并且for循环将迭代n次，因此总共有O( n )。