关于二叉搜索树单孩子节点删除挂载逻辑的疑问

我的问题 #

我正在学习数据结构，刚开始理解二叉树。所学资料中二叉搜索树的节点删除规则如下：

• 待删除节点为叶子节点时，将其父节点对应的左/右指针（根据父节点与子节点的数值大小决定）置为null；
• 若待删除节点仅存在左子节点，需将父节点指针指向该左子节点。此处我有疑问：左子节点的挂载位置是否由其值与父节点的值决定？例如，若删除父节点为50、右子节点为60的节点25，60是否应挂载在50的右侧？
• 仅存在右子节点的情况逻辑基本一致；
• 待删除节点有两个子节点的情况我已理解。

我用画图工具制作了示意图辅助理解，但仍存在困惑，怀疑遗漏了相关概念。

解答 #

首先要抓住二叉搜索树的核心性质：任意节点的左子树所有节点值都小于该节点值，右子树所有节点值都大于该节点值，所有指针调整都要维持这个规则。

针对你的疑问：

• 当待删除节点只有左子节点时，左子节点的挂载位置确实由其值与父节点的值决定。因为待删除节点的左子树所有节点值都小于待删除节点，而待删除节点本身和父节点的大小关系是确定的（比如待删除节点是父节点的左子节点，说明它的值小于父节点），所以它的左子节点值必然也小于父节点，自然要挂载在父节点的左侧；如果待删除节点是父节点的右子节点，那它的左子节点值介于父节点和待删除节点之间，还是要挂载在父节点的右侧。
• 你举的例子里，节点25是50的左子节点（25<50），60是50的右子节点（60>50），删除25的操作和60完全无关，60本来就符合右子节点的性质，会一直留在50的右侧，不需要调整。

你可能混淆了待删除节点的子节点与其他节点的关系，只要时刻紧扣二叉搜索树左小右大的性质，就能理清指针调整的逻辑。

内容的提问来源于stack exchange，提问作者arakakivl