2

作为 AVL 模板的一部分,我正在研究(C++ 模板),当 n1+n2 是两棵树中的总元素时,我试图以 O(n1+n2) 复杂度合并 2 棵 AVL 树。

我想到了下一个算法。

  1. 在第一棵树上进行中序遍历并构建一个数组/列表 - O(n1)
  2. 在第二棵树上进行中序遍历并构建一个数组/列表 - O(n2)
  3. 合并这两个数组的排序并以 n1+n2 - O(n1+n2) 的大小构建最终排序的数组/列表
  4. 用 n1+n2 个顶点构建一个空的几乎完整的二叉树 - O(n1+n2)。
  5. 在使用合并数组/列表中的元素更新顶点时,在几乎完整的二叉树上进行中序遍历。

我的问题是我如何实际构建具有 n1+n2 个顶点的空几乎完整的二叉树

4

1 回答 1

1

如果将归并排序发出的节点存储在向量中,则可以相对容易地完成。您的节点已经排序,因此您可以按以下方式“插入”节点:

  1. 从数组 1/2 的元素构建根节点;
  2. 使用数组的 1/4 和 3/4 处的元素构建根的子节点;
  3. 递归地重复2。

这对您来说应该是按顺序遍历恰好被表示为排序数组的二叉树。

请注意,要使其正常工作,您需要在“关闭”平衡的情况下构建树。这很可能需要您将其设置为您的类的私有方法,可能是一个特殊的构造函数。

于 2011-04-17T15:14:28.703 回答