我正在学习 AVL 树并在递归代码中获得了 TLE。我的导师建议迭代解决方案。我搜索并找到了一个将父节点保存在子节点中的解决方案。我想知道这个可能会在内存中出现问题，不是吗？还有另一种方法可以在 AVL 树中插入、删除不需要将父级保存在子级中的内容吗？请给我一个提示。
问问题
5703 次
2 回答
4
实现 AVL 树时有多种选择： - 递归或迭代 - 存储平衡因子（右侧高度减去左侧高度）或高度 - 是否存储父引用
具有高度的递归往往会提供最优雅的解决方案，但迭代在某些情况下可能表现更好，因此值得考虑。您可以阅读有关选择的信息： http ://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx 并查看 Java 中的迭代实现： https ://github.com/dmcmanam/bbst-showdown
于 2017-10-19T01:00:56.797 回答
0
迭代（非递归）方法需要父引用，因为插入/删除后需要回溯，我们可以在递归方法中使用堆栈进行回溯，而在迭代方法中我们只能使用父引用进行回溯。请参阅https://en.wikipedia.org/wiki/AVL_tree#Insert和https://en.wikipedia.org/wiki/AVL_tree#Delete。
在此插入之后，有必要检查每个节点的祖先是否与 AVL 树的不变量一致：这称为“回溯”。
这是 C 中基于迭代 BalanceFactor 的 AVL 树实现：https ://github.com/xieqing/avl-tree
于 2019-03-15T15:52:29.047 回答