从2d二叉搜索树中删除节点

Question

我想知道是否有人可以提供一些关于从2d二叉搜索树中删除节点的有用信息。

我理解有四种情况下，其中第一个我已经完成：

1. 删除没有子（叶）节点，操作简单，只需设置指针到该节点为空。
2. 删除左侧节点上有一个子节点且右侧节点为空的节点。
3. 删除右节点上有一个子节点且左节点为空的节点。
4. 删除有两个孩子的节点，左侧和右侧。

我不知道如何确切地做2,3和4.我试图做迭代，但是，似乎并没有工作。我假设这必须递归地完成。有人可以澄清一下如何完全做到这一点。这是在java中，应该没关系:)

Answer 1

在2D树中，所有值都存储在叶节点中。内部节点只是作为寻找叶节点的途径。具体而言，内部节点定义了包含基础数据的半平面。我们只处理数据;我们不修改数据结构本身的结构元素。所以，只有上面的情况1成立。所有其他人都无关紧要。