如何合并满足堆顺序的两棵树？

Question

是否可以在时间O(m+n+1)内合并满足堆序的两棵树？而 m 和 n 是输入树的高度。

Example 

Input:
   10              8
     \
      9 
Output: (Can be any one of them)
   10               10             10          10
     \             /  \           /  \        /  
      9           9    8         8    9      9
     /                                      /
    8                                      8

Answer 1

是的，这可以在 O( + ) 中完成，条件是允许输出树与输入树共享节点。

算法

给定两个根节点 a 和 b:

如果 a 和 b 都为空，return 为空（基本情况）
如果其中一个为空，select另一个。否则 select 具有较大值的节点。假设 a 是 selected 节点。
使用与 a 相同的值创建一个新节点 x。
执行递归以合并 a.left 和 b。将合并结果附加到 x.left
将未更改的 a.right 引用分配给 x.right
return x

由于在递归的每一层我们都减少了主题中一棵树的高度，递归深度最多为两棵输入树的高度之和，从中遵循给定的时间复杂度。

在步骤 3 中合并 a.left 或 a.right 的选择是任意的。你可以把它随机化。

示例实现

这里是JavaScript中的粗略实现。当您运行此代码段时，将合并以下两棵树：

        10              8
      /   \            / \
     4     9          7   6
    / \   / \              \
   3   1 2   5              0

class Node {
    constructor(value, left=null, right=null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    toString() {
        return (this.right ? this.right.toString().replace(/^/gm, "  ") + "\n" : "")
             + this.value
             + (this.left ? "\n" + this.left.toString().replace(/^/gm, "  ") : ""); 
    }
}

function merge(a, b) {
    if (a == null && b == null) return null;
    if (a == null || (b != null && b.value > a.value)) { 
        return new Node(b.value, merge(a, b.left), b.right);
    }
    return new Node(a.value, a.left, merge(b, a.right));
}

// Example
let a = new Node(10, 
    new Node(4, 
        new Node(3), 
        new Node(1)
    ), 
    new Node(9, 
        new Node(2), 
        new Node(5)
    )
);

let b = new Node(8, 
    new Node(7), 
    new Node(6, 
        null, 
        new Node(0)
    )
);

console.log("a:");
console.log(a.toString());
console.log("b:");
console.log(b.toString());
console.log("merged:");
console.log(merge(a, b).toString());

这个片段有一个非常基本的打印功能——它打印树旋转 90°，根在左边。没有连接节点的线（你必须想象它们），只有缩进。

示例将生成这棵树：

        10
      /   \
     4     9
    / \   / \
   3   1 8   5
        / \
       7   6
          / \
         2   0

注意：您提到了 O( + + 1)，但该附加常量无关紧要：O( + + 1) = O( + )。

如何合并满足堆顺序的两棵树？

How can I merge two trees which satisfy the heap order?

sorting

algorithm

heap

tree

算法

示例实现