我有一个关于 Balanced BST 的理论问题.
我想构建 Perfect Balanced Tree有 2^k - 1节点，来自常规 unbalanced BST .我能想到的最简单的解决方案是使用排序的 Array/Linked list并递归地将数组划分为子数组，并构建Perfect Balanced BST从它。
但是，在树尺寸非常大的情况下，我需要创建一个 Array/List同样的大小，所以这种方法会消耗大量的内存。
另一种选择是使用 AVL旋转函数，逐个元素插入并根据树平衡因子(左右子树的三个高度)通过旋转平衡树。
我的问题是，我的假设是否正确？有没有其他方法可以创建完美的BST来自不平衡BST ？
最佳答案
AVL 和类似的树不是完美平衡的，所以我不确定它们在这种情况下有何用处。
您可以使用 left 和 right 指针代替 forward 和 从树节点构建双向链表向后 指针。对该列表进行排序，并从下向上递归地构建树，从左到右使用列表。
构建一棵大小为 1 的树很简单:只需咬掉列表中最左边的节点即可。
现在如果你可以构建一棵大小为 N 的树，你也可以构建一棵大小为 2N+1 的树:构建一棵大小为 N，然后咬掉一个节点，然后构建另一棵大小为 N 的树。单个节点将是较大树的根，而两个较小的树将是其左右子树。由于列表已排序，树自动成为有效的搜索树。
对于 2^k-1 以外的尺寸，这也很容易修改。
更新:因为您是从搜索树开始的，所以您可以在 O(N) 时间和 O(log N) 空间内直接从它构建一个排序列表(也许甚至在 O(1) 空间中，只要有一点点独创性)，并在 O(N) 时间和 O(log N)(或O(1))空间。
关于c - 完美平衡二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14021088/