删除节点后，将右子树挂接到node的左子树是会不会出现大小异常？

Question

波波老师你好：
你在删除最小节点的时候，
Node rightNode =node.right;
size–;
return node.right;
将要删除节点的右子树挂接到上个节点的左子树上，会不会出现挂接后的左子树的值大于node的值啊，好纠结这点？

Answer 1

liuyubobobo 2020-06-10 05:07:28

不会。因为二分搜索树的性质是，一个节点的左子树的所有节点都会小于这个节点本身。所以，要删除节点的右子树的所有节点一定比上一个节点小（因为我们一直在向左找）。

试试看，你能不能够造出一个反例，出现你说的情况？如果不能，再仔细想想为什么？二分搜索树的什么性质在阻止这一点？

继续加油！：）

• 提问者 weixin_慕田峪5104257 #1

  谢谢波波老师，嗯嗯，我回去看看二叉树的添加，添加的时候咱们用的递归，如果要添加的元素小于当前节点的元素值，那么，就低轨道当前节点的左子树上，所以，一个节点的左子树的所有节点都会小于这个节点本身

• liuyubobobo 回复 提问者 weixin_慕田峪5104257 #2

  就是这个意思。继续加油！：）