Ole*_*aKL 8 c algorithm linked-list avl-tree binary-search-tree
我有一个理论问题Balanced BST.
我想构建Perfect Balanced Tree具有2^k - 1节点的节点unbalanced BST.我能想到的最简单的解决方案是使用排序Array/Linked list并递归地将数组划分为子数组,并Perfect Balanced BST从中构建.
但是,在树大小非常大的情况下,我需要创建一个Array/List相同大小的内容,因此这种方法会占用大量内存.
另一种选择是使用AVL旋转功能,逐个元素插入并根据树平衡因子平衡树和旋转 - 左侧和右侧子树的三个高度.
我的问题是,我对我的假设是对的吗？还有其他方法可以BST从不平衡中创造完美BST吗？
我还没有找到需要完美平衡搜索树的非常好的情况。如果您的案例确实需要，我很想听听。通常，拥有一棵几乎平衡的树会更好更快。
如果您有一个很大的搜索树，那么丢弃所有现有的结构通常不是一个好主意。使用旋转函数是获得更平衡的树同时保留大部分现有结构的好方法。但通常您会使用合适的数据结构来确保您永远不会拥有完全不平衡的树。所谓的自平衡树。
例如，AVL 树、红黑树或展开树，它们使用略有不同的旋转变体来保持树平衡。
如果你真的有一棵完全不平衡的树，你可能会遇到不同的问题。- 在您的情况下，以 AVL 方式旋转它可能是修复它的最佳方法。