完美的平衡二叉搜索树 [英] Perfect Balanced Binary Search Tree

问题描述

我有关于平衡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.

这篇关于完美的平衡二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！