完美平衡的二进制搜索树

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

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

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

另一种选择是使用AVL旋转function,逐个元素插入并根据树平衡因子平衡树和旋转 – 左和右子树的三个高度。

我的问题是,我对我的假设是对的吗? 还有其他方法可以从不平衡的BST创建完美的BST吗?

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

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

例如,AVL树,红黑树或展开树,其使用略微不同的旋转变体来保持树平衡。

如果你真的有一个完全不平衡的树,你可能会有一个不同的问题。 – 在你旋转它的情况下,AVL方式可能是修复它的最佳方法。

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

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

构建一个大小为1的树是微不足道的:只需从列表中咬掉最左边的节点。

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

对于2^k-1以外的尺寸,这也很容易修改。

更新:既然您是从搜索树开始的,那么您可以在O(N)时间和O(log N)空间中直接从它构建一个排序列表(甚至可能在O(1)空间中有一些小巧的创造),并构建树自下而上也在O(N)时间和O(log N) (或O(1) )空间。

如果你受内存限制,那么你可以使用可以在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)空间中实现。