avl-tree - 你将如何着手实现一个带有惰性删除的平衡树？

Question

更具体地说，是一个 AVL 树。是否可以？我想这样做，但我认为未删除的节点可能难以管理轮换。

我有一个可以正常工作的，但我想将这个带有延迟删除的用于其他用途。

Answer 1

如果您希望它相对于所有节点(包括标记为已删除的节点)保持“平衡”，您无需执行任何操作——您已经在那里了。

如果您希望它相对于未删除的节点集保持“平衡”——问题是为什么？平衡的全部意义在于防止失控(线性最坏情况)搜索这取决于节点，而不是它们的删除状态。