我正在学习AVL树，但在递归代码中遇到了TLE。我的导师建议使用迭代解决方案。我搜索并找到了一种解决方案，该方案将父节点保存在子节点中。
我想知道这种方法是否会有内存问题？还有没有其他方法可以在AVL树中进行插入、删除而不需要保存父节点在子节点中呢？请给我一些提示。
2个回答
4
实现AVL树时有几种选择:
- 递归或迭代
- 存储平衡因子(右侧高度减去左侧高度)或高度
- 存储父引用或不存储
递归与高度一起使用通常会给出最优雅的解决方案，但在某些情况下，迭代可能表现更佳，因此值得考虑。 您可以阅读有关这些选择的内容: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx 并查看Java中的迭代实现: https://github.com/dmcmanam/bbst-showdown
递归与高度一起使用通常会给出最优雅的解决方案，但在某些情况下，迭代可能表现更佳，因此值得考虑。 您可以阅读有关这些选择的内容: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx 并查看Java中的迭代实现: https://github.com/dmcmanam/bbst-showdown
- David McManamon
1
在迭代（非递归）方法中，需要父参考来重新插入/删除后重新跟踪，而在递归方法中，我们可以使用堆栈来重新跟踪，而在迭代方法中，我们只能使用父参考进行重新跟踪。请参见https://en.wikipedia.org/wiki/AVL_tree#Insert和https://en.wikipedia.org/wiki/AVL_tree#Delete。
在插入后，有必要检查每个节点的祖先与AVL树的不变式一致性：这称为“重新跟踪”。
以下是C语言中基于平衡因子的AVL树迭代实现: https://github.com/xieqing/avl-tree。
在插入后，有必要检查每个节点的祖先与AVL树的不变式一致性：这称为“重新跟踪”。
以下是C语言中基于平衡因子的AVL树迭代实现: https://github.com/xieqing/avl-tree。
- xieq
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接