我有一个关于平衡二叉树的理论问题。
我想要构建一个拥有2^k - 1个节点的完美平衡树，从一个普通的不平衡的二叉搜索树开始。最简单的解决方法是使用排序好的数组/链表，并递归地将数组分成子数组，然后从中构建完美平衡二叉树。
然而，在极大的树大小的情况下，我需要创建一个相同大小的数组/列表，因此这种方法将消耗大量的内存。
另一个选择是使用AVL旋转函数，逐个插入元素并通过旋转来平衡树，具体取决于树的平衡因子——左右子树的高度差。
我的问题是，我的假设正确吗？是否有其他方法可以从不平衡的BST创建出完美的BST？
我还没有发现需要完全平衡搜索树的非常好的情况。如果您的情况确实需要，我很乐意听取您的意见。通常情况下，拥有一个几乎平衡的树更好、更快。
如果您有一个大的搜索树，抛弃所有现有的结构通常不是一个好主意。使用旋转函数是一种获得更平衡树的好方法，同时保留大部分现有的结构。但通常情况下，您可以使用适当的数据结构来确保您永远不会拥有完全不平衡的树，这被称为自平衡树。
例如，有 AVL 树，红黑树或伸展树，它们使用稍微不同的旋转变体来保持树的平衡。
如果您真的有一个完全不平衡的树，那么您可能有一个不同的问题。 - 在您的情况下，按照 AVL 的方式旋转它可能是修复它的最佳方式。
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)空间内实现。