在AVL树中，插入和删除n个元素时最坏情况下的旋转次数是多少？
我认为插入应该是O(n)，删除应该是O(nlogn)。不过，我对删除不太确定。
我说得对吗？
最佳答案
对于插入或删除节点x这两种操作，有时需要对从x到根的所有节点进行旋转。由于具有 n 个节点的树的高度为 O(log n)，因此两个操作的最坏情况都需要 O(log n) 轮换。对于n个插入/删除操作，给出O(n log n)。
关于data-structures - AVL树插入和删除期间最坏情况的旋转次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45781541/