C++ AVLtree删除节点和余额

Question

我正在尝试在C++中实现一个AVL-Tree。到目前为止，插入和平衡树工作得很好。我尝试实现的算法是：

步骤1:像BST一样删除/插入想要的节点。

第二步:对同一插入/删除过程的树进行平衡。

我想把它分成两个步骤，这样就不会很难阅读和编程了。问题出在第2步，“insert”运行得很好，因为我可以在树中搜索现有节点，然后使用递归来更新它所经历的过程。

但是在删除时，因为节点已经被删除了，所以我找不到它在步骤1中经过的路由。

我想过插入后继者，但没有运气，我真的希望通过两个步骤来保持它，即使我在网上看到的所有实现都结合了这两个步骤

Answer 1

以下视频有助于理解AVL树的旋转和插入以及删除操作：https://www.youtube.com/watch?v=8JkBIA9V6Nc&list=PL30dC-5PIyXljRGbjvZ-mG8OITMESqxuj&index=12

示例：https://www.youtube.com/watch?v=LkwZggRs0t8&list=PL30dC-5PIyXljRGbjvZ-mG8OITMESqxuj&index=13