AVL树轮转效率

Question

AVL树轮转的大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）次旋转。无论事实如何，复杂性就像你说的对数一样。