不太理解 BST的remove的code

[ 本帖最后由 voiding 于 2014-11-9 11:32 编辑 ]\n\n又遇到recursion的问题想请教大家，下面的code的是Binary Search Tree的delete a node的code， 我不理解这里 x.left  = delete(x.left,  key)， delete（x.left, key）应该return的就是要被delete的那个node，为什么那个node会成为x的left child呢？谢谢。

不是return 那个被delete的node，而是 return the node that will replace the deleted node

返回的是进行删除操作的子树的根节点

一看就知道是Princeton 那个老教授算法课上的code， 你光秃秃看这个肯定看不懂。搜一下 hibbard deletion

做递归你首先要理解这个函数是干嘛的，题上这个函数返回的是一个删除了目标node的树的根，当（cmp<0）,那就是说明要删的node在左子树里，所以delete(x.left,key)返回的就是删除了目标node的左子树的根，然后把这个根赋给原root.left就行了，右树同理

看了大家的讲解以后，现在完全明白了，谢谢！