作为 AVL 模板的一部分,我正在研究(C++ 模板),当 n1+n2 是两棵树中的总元素时,我试图以 O(n1+n2) 复杂度合并 2 棵 AVL 树。
我想到了下一个算法。
- 在第一棵树上进行中序遍历并构建一个数组/列表 - O(n1)
- 在第二棵树上进行中序遍历并构建一个数组/列表 - O(n2)
- 合并这两个数组的排序并以 n1+n2 - O(n1+n2) 的大小构建最终排序的数组/列表
- 用 n1+n2 个顶点构建一个空的几乎完整的二叉树 - O(n1+n2)。
- 在使用合并数组/列表中的元素更新顶点时,在几乎完整的二叉树上进行中序遍历。
我的问题是我如何实际构建具有 n1+n2 个顶点的空几乎完整的二叉树?