algorithm - 在二叉搜索树中删除节点的伪代码和条件

Question

我正在尝试编写一个函数来从二叉树中删除一个节点。我还没有编写函数代码，我正在尝试考虑删除节点时应该考虑的不同条件。我猜测可能的条件是:

1. 该节点没有 child

2. 该节点有一个 child

3. 该节点有2个 child

在每种情况下，执行删除功能的算法是什么？

Answer 1

这是你可以在任何有关算法的标准教科书中找到的东西，但假设你对不平衡的情况感兴趣(平衡树通常在移除后执行一些称为“旋转”的重新平衡操作)并且你使用“明显”的数据结构(保存值和两个指向其他 tree_node 的指针的 tree_node 结构):

1. No children:释放节点持有的内存，并将指向它的父节点的子链接设置为NULL；
2. One child:释放节点占用的内存，将父节点指向它的子链接设置为其唯一子节点的地址；
3. 二孩:这确实是个“复杂”的案子。找到左 child 的最右边节点(或右 child 的最左边节点)，取其值，将其删除(它是“情况 1”，所以很容易，可以递归完成)并将当前节点的值设置为该节点之一。这是 O(tree_height) = O(n)，但这不是问题(至少在理论上)，因为这将是查找节点的复杂性。