algorithm - 删除 AVL 树中所有元素的最有效方法是什么（排序删除）

Question

我知道删除 AVL 树中的节点需要 O(logn) 的时间复杂度。话虽如此，删除具有 n 个节点的 AVL 树需要 O(n logn)。但是，我想知道我的目标是否是拥有 AVL 树的排序元素，我可以删除 O(n) 而不是 O(n logn) 中的所有元素。可能通过实现一个需要 O(1) 的删除元素。我无法在 O(n) 中找到任何方法。是因为我们不能还是我错过了什么？

标签： algorithmoopdata-structuresbinary-treeavl-tree

Answer 1

如果每次删除后不需要保留AVL结构，则执行后序遍历，只删除每个节点而不进行平衡，而不是“显示数据部分”