我有一个理论问题Balanced BST.
我想建立Perfect Balanced Tree具有2^k - 1节点，从常规unbalanced BST。我能想到的最简单的解决方案是使用排序Array/Linked list并递归地将数组划分为子数组，并构建Perfect Balanced BST从中。
但是，在树尺寸非常大的情况下，我需要创建一个Array/List在相同的大小下，这种方法会消耗大量的内存。
另一种选择是使用AVL旋转函数，逐个元素插入并根据树平衡因子（左右子树的三个高度）旋转来平衡树。
我的问题是，我的假设正确吗？有没有其他方法可以创造一个完美的BST来自不平衡BST?
AVL 和类似的树不是完美平衡，所以我不确定它们在这种情况下有何用处。
您可以使用树节点构建双向链表left and right指针代替forward and backward指针。对该列表进行排序，并从下往上递归地构建树，从左到右使用该列表。
构建一棵大小为 1 的树很简单：只需将列表中最左边的节点咬下来即可。
现在如果你能建造一棵这么大的树N，你还可以构建一棵大小为2N+1：构建一棵大小树N，然后咬掉单个节点，然后构建另一棵大小相同的树N。单个节点将是较大树的根，两个较小的树将是其左右子树。由于列表已排序，因此该树自动成为有效的搜索树。
对于除此之外的尺寸，这很容易修改2^k-1 too.
更新：由于您是从搜索树开始，因此您可以直接从中构建排序列表O(N)时间和O(log N)空间（也许甚至在O(1)具有一点独创性的空间），并自下而上地构建树O(N)时间和O(log N) (or O(1)） 空间。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
