具体来说,AVL树旋转的大O效率是多少？
例如,插入时: - O(logN)搜索位置 - O(1)要插入 - ？平衡(如果需要重新平衡)
我以为它会是O(logN),但是我找到了一个声称它是O(1)的网站 - 除非我误读了它 - http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml
(这对2-3棵树来说也一样吗？)
我在这里先向您的帮助表示感谢
正如你所说,复杂性是O(log n).我相信在文章中他们指的是每次重新平衡操作的恒定时间,即每次旋转,而你必须进行O(log n)旋转.无论事实如何,复杂性就像你说的那样对数.