不明白此二进制搜索树（BST）示例算法

Question

在从here删除代码。

我不明白第一个删除代码片段（其中节点没有两个孩子）。

如果被删除的节点本身有一个父节点和一个子节点（即节点有一个孩子），它是如何工作的？

该代码只是删除节点，并没有设置父指针现在孤儿的孩子。

我错过了什么吗？

Answer 1

我可能是错的，但引用网站上的代码似乎没问题。虽然我没有测试过它。

这是真的，因为delete函数接受一个类型为BSTNode **节点的参数。这不是指向节点的指针。这是父节点指向节点本身的指针。这可能有点草率，但我必须承认在实现代码后，它是一种优雅的解决方案。所以当你重写（* node）时，你并没有重写节点本身，而是你正在改写节点的父节点指向节点。有效的代码是以你稍微变态的方式做你的建议：D。希望你明白我的意思，我希望我的理解正确。

我还建议您阅读关于红黑树的更多信息，因为本文仅提供洞察创建树，但所描述的结构对其高度没有渐近边界。如果，例如您在此结构中推送排序值，它将成为连接列表而不是平衡树。

---