老师，你好，我想问下，关于二分搜索树的删除任意元素，左右孩子均不为空(JS实现)

Question

老师，你好，我想问下，关于二分搜索树的删除任意元素那里，如果删除的元素左右孩子均不为空的情况下，找到右孩子中的最小值，然后将这个最小值的left指向左孩子，这样也能够实现删除的效果，相比你的思路是将右孩子的最小节点去替代删除的节点来说，我的这个想法有哪些弊端呢，或者说这个想法能不能行得通呢（我测试了好像可以=，=，）

let rightNode = node.right;
let rightMin = this.searchMinimum(node.right); // 找到右节点中最小的节点
rightMin.left = node.left; // 将左节点拼接到右节点最小的节点上
node.left = null;
node.right = null;
return rightNode;

Answer 1

提问者 慕标8212032 2018-11-25 16:49:51

老师，这个是我的思路，删除53这个元素，跟你讲的思路有点区别

• liuyubobobo #1

  wow！赞绘图说明问题！同时大赞思路！我理解了！完全没有问题！是正确的！赞赞赞！如果说有弊端的话，潜在的会让整棵树的高度变高（想象40的节点是一个很高的树的情况）。但是由于我们在这一章探讨的二分搜索树本身也没有考虑这个问题，所以你的思考完全没有问题！再次大赞！???

• 提问者 慕标8212032 回复 liuyubobobo #2

  哈哈，谢谢，不过老师的思路更好

• liuyubobobo 回复 提问者 慕标8212032 #3

  NoNoNoNoNo，这个删除策略不是我的思路，是标准的二分搜索树的删除策略。我甚至没有思考过还能不能使用别的策略删除。 你的这个方法真正是你的思考，再次大赞！前途无量！

Answer 2

liuyubobobo 2018-11-25 16:27:31

我没有实际测试，但猛地看这样是有问题的。我没有看到哪里将rightMin的父亲节点和rightMin断开联系？而原先node的右子树似乎丢失了？

可以尝试用一组随机数据（小数据即可，8-10个元素）创建BST，然后不断删除最小值，不断用中序遍历打印整个树中的所有节点，验证一下整个过程是否正确？

加油！：）