问题描述
我有关于平衡BST一个理论性的问题
。
我想建完美平衡树
,有 2 ^的K - 1
节点,从一个普通的不平衡BST
。我能想到的最简单的解决方法是使用一个排序阵列/链表
和递归地划分阵列子阵列,并建立完美平衡BST
从它。
I would like to build Perfect Balanced Tree
that has 2^k - 1
nodes, from a regular unbalanced BST
. The easiest solution I can think of is to use a sorted Array/Linked list
and recursively divide the array to sub-arrays, and build Perfect Balanced BST
from it.
不过,在非常大的树尺寸的情况下,我需要在相同的尺寸创建一个阵列/列表
所以这种方法会消耗大量的内存
However, in a case of extremely large Tree sizes, I will need to create an Array/List
in the same size so this method will consume a large amount of memory.
另一种选择是使用 AVL
旋转功能,通过元素插入元素和平衡的树,根据树的平衡因子旋转 - 三高左,右分树木。
Another option is to use AVL
rotation functions, inserting element by element and balancing the tree with rotations depending on the Tree Balance Factor - three height of the left and right sub trees.
我的问题是,我说的对我的假设?是否有任何其他的方法来创建一个完美的 BST
从不平衡 BST
?
My questions are, am I right about my assumptions? Is there any other way to create a perfect BST
from unbalanced BST
?
推荐答案
我并没有找到需要一个完美的平衡搜索树一个很好的局面。如果你的情况确实需要的话,我想听到它。通常它是更好更快地拥有近平衡树。
I did not yet find a very good situation for needing a perfectly balanced search tree. If your case really needs it, I would like to hear about it. Usually it is better and faster to have a almost balanced tree.
如果你有一个大的搜索树,扔掉所有现有的结构通常没有什么好主意。使用旋转功能是得到一个更平衡的树的好方法,而preserving大多数现有的结构。但通常你用一个合适的数据结构,以确保您永远不会有一个完全不平衡的树。所谓的自平衡树。
If you have a large search tree, throwing away all existing structure is usually no good idea. Using rotation functions is a good way of getting a more balanced tree while preserving most of the existing structure. But normally you use a suitable data structure to make sure you never have a completely unbalanced tree. So called self balancing trees.
有例如AVL树,红黑树或喷射 - 树,它使用旋转略有不同的变体,以保持树均衡
There is for example an AVL tree, a red-black-tree or a splay-tree, which use slightly different variants of rotation to keep the tree balanced.
如果你真的有一个完全不平衡的树,你可能有一个不同的问题。 - 在你的情况下转动它的AVL方式可能是解决这个问题的最好办法
If you really have a totally unbalanced tree you might have a different problem. - In your case rotating it the AVL way is probably the best way to fix it.
这篇关于完美的平衡二叉搜索树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!