完美平衡二叉树

Question

我有一个关于Balanced BST的理论问题。

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

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

另一种选择是使用AVL旋转函数，逐个元素插入元素，并根据树平衡系数-左子树和右子树的三个高度-来平衡树的旋转。

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

Answer 1

我还没有找到一个非常好的情况，需要一个完美平衡的搜索树。如果你的案子真的需要的话，我想听听。通常，拥有一棵几乎平衡的树会更好、更快。

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

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

如果你真的有一个完全不平衡的树，你可能会有一个不同的问题。+在你的例子中，以AVL的方式旋转它可能是修复它的最好方法。

Answer 2

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

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

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

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

对于2^k-1以外的其他大小，这也很容易修改。

更新:由于您是从搜索树开始的，因此您可以在O(N) time和O(log N)空间(甚至可以巧妙地在O(1)空间中)直接从它构建一个排序列表，也可以在O(N) time和O(log N) (或O(1))空间中自下而上地构建树。

Answer 3

如果你是内存受限的，那么你可以使用拆分和连接操作，这可以在O(log )时间内在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 )空间内实现。