big-o - AVL 树旋转效率

Question

AVL树旋转的Big O效率具体是多少？

例如插入时： - O(logN) 搜索位置 - O(1) 插入 - ? 用于平衡（如果需要重新平衡）

我以为它会是 O(logN)，但我发现一个声称它是 O(1) 的网站 - 除非我读错了 - http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml

（这对于 2-3 树也一样吗？）

我在这里先向您的帮助表示感谢

Answer 1

正如你所说，复杂性是 O(log n)。我相信在文章中，它们意味着每次重新平衡操作（即每次旋转）的恒定时间，而您必须进行 O(log n) 次旋转。无论真相如何，正如您所说的那样，复杂性是对数的。