AVL树最坏情况下插入和删除时的旋转次数
AVL tree worst case number of rotations during insertion and deletion
在AVL树中，插入和删除n个元素时最坏情况下的旋转次数是多少？
我认为插入应该是O(n)，删除应该是O(nlogn)。但是，我不太确定删除。
我说的对吗？
对于两个操作 - 插入或删除节点 x，有些情况需要在 x[=19= 的所有节点上进行旋转] 直到根。由于具有 n 个节点的树的高度是 O(log n)，因此两种操作的最坏情况都需要 O(log n) 次旋转。对于 n insert/delete 给出 O(n log n).
的操作
在AVL树中，插入和删除n个元素时最坏情况下的旋转次数是多少？
我认为插入应该是O(n)，删除应该是O(nlogn)。但是，我不太确定删除。
我说的对吗？
对于两个操作 - 插入或删除节点 x，有些情况需要在 x[=19= 的所有节点上进行旋转] 直到根。由于具有 n 个节点的树的高度是 O(log n)，因此两种操作的最坏情况都需要 O(log n) 次旋转。对于 n insert/delete 给出 O(n log n).
的操作