Ksh*_*ain 3 algorithm avl-tree time-complexity binary-search-tree data-structures
当我学习二元搜索树(平衡和不平衡)时,我想出了我需要解决的问题:
如果我构造一个二进制搜索树(不需要平衡),使用n个元素那么树构造的总时间复杂度是多少？
如果AVL树是由n个元素构成的,那么构造该AVL树的时间复杂度是多少？
它应该超过nlog(n)吗？因为我们需要大量的旋转来进行AVL树构建.
我知道AVL树中的插入和删除操作将是log(n)顺序(如果使用随机元素构造的二叉搜索树具有log(n)高度,则同样如此).
但是我需要了解整体树的构建成本以及它如何变化,因为我需要使用平衡搜索树进行分类.
Sal*_*ali 22
让我们从构建AVL树开始.要创建树,您必须在其中插入n元素.要在需要的平衡树中插入元素log(n).因此你最终得到了O(n*log(n)).
回到常规BST.这是违反直觉的,但这取决于你如何构建这棵树.如果您事先不知道BST的所有元素(在线算法),那么您必须n逐个插入每个元素.如果你非常不走运,插入的复杂性就会O(n)因此而恶化O(n^2).
请注意,这种情况极不可能发生,但仍有可能.
但O(nlog(n))如果您事先了解所有元素,您仍然可以实现.您可以对它们进行排序O(nlog(n)),然后按以下顺序插入元素.取中间元素并将其作为根插入,然后递归地对剩下的两个部分执行相同操作.您将最终创建平衡的BST,n使用插入元素log(n).
小智 7