AVL树Delete操作最坏场景的实例验证与疑问
AVL树删除操作的最坏旋转次数验证与疑问
有资料指出AVL树的Delete操作可能产生O(log(N))次旋转。我尝试通过构造实例验证该结论时,曾参考一个示例,删除指定节点后仅触发2次旋转,远未达到对应log(N)的量级。
之后我自行构建了一棵AVL树,删除节点'25'时触发了4次旋转:左旋转、右旋转、左旋转、右旋转。此时树的节点数为12,log₂(12)≈3.6,向上取整后与旋转次数相符,验证了O(log(N))的结论。
请问这是否就是AVL树Delete操作在实际中的最坏情况?是否还有更多相关结论待挖掘?
内容的提问来源于stack exchange,提问作者Niek Beijloos
相关产品推荐
相关产品推荐

