8

我有一个关于Balanced BST.

我想构建Perfect Balanced Tree具有2^k - 1节点的常规unbalanced BST. 我能想到的最简单的解决方案是使用排序Array/Linked list并递归地将数组划分为子数组，并Perfect Balanced BST从中构建。

但是，在 Tree 大小非常大的情况下，我需要创建一个Array/List相同大小的树，因此这种方法会消耗大量内存。

另一种选择是使用AVL旋转函数，逐个元素插入并根据树平衡因子（左右子树的三个高度）通过旋转平衡树。

我的问题是，我的假设是否正确？有没有其他方法可以BST从不平衡创造完美BST？

4

3 回答 3

2

AVL 和类似的树不是完全平衡的，所以我不确定它们在这种情况下如何有用。

left您可以使用和right指针代替forward和指针，从树节点构建双向链表backward。对该列表进行排序，并从下往上递归地构建树，从左到右使用该列表。

构建大小为 1 的树很简单：只需咬掉列表中最左边的节点即可。

现在，如果您可以构建一棵大小的树N，那么您也可以构建一棵大小的树2N+1：构建一棵大小的树N，然后咬掉一个节点，然后构建另一棵大小的树N。单个节点将是大树的根，两个较小的树将是它的左右子树。由于列表已排序，因此该树自动成为有效的搜索树。

这很容易修改其他尺寸2^k-1。

更新：由于您是从搜索树开始的，因此您可以在O(N)时间和O(log N)空间上直接从它构建一个排序列表（也许甚至在空间中有点巧思），并在时间和（或）空间O(1)中自下而上构建树.O(N)O(log N)O(1)

于 2012-12-24T14:54:04.710 回答
1

我还没有找到一个非常好的需要完美平衡的搜索树的情况。如果您的情况确实需要它，我想听听。通常，拥有几乎平衡的树会更好更快。

如果您有一个大型搜索树，丢弃所有现有结构通常不是一个好主意。使用旋转函数是获得更平衡的树同时保留大部分现有结构的好方法。但通常你使用合适的数据结构来确保你永远不会有一个完全不平衡的树。所谓的自平衡树。

例如，有一个 AVL 树、一个红黑树或一个展开树，它们使用稍微不同的旋转变体来保持树的平衡。

如果你真的有一棵完全不平衡的树，你可能会遇到不同的问题。- 在您的情况下，旋转 AVL 方式可能是修复它的最佳方式。

于 2012-12-24T14:57:17.643 回答
0

如果您的内存受限，那么您可以使用可以在 O(log n) 时间内在 AVL 树上完成的拆分和连接操作，并且我相信空间不变。

如果您还能够维护订单统计信息，那么您可以按中位数拆分，使 LHS 和 RHS 完美，然后加入。

伪代码（用于递归版本）将是

void MakePerfect (AVLTree tree) {

    Tree left, right;
    Data median;

    SplitOnMedian(tree, &left, &median, &right);
    left = MakePerfect(left);
    right = MakePerfect(right);
    return Join(left, median, right);
}

我相信这可以在 O(n) 时间和 O(log n) 空间中实现。

于 2012-12-24T23:45:59.173 回答