首页 > 代码库 > seach tree的deletion的实现——对树的指针的进一步理解
seach tree的deletion的实现——对树的指针的进一步理解
一颗binary search tree,我们要在其中删除node1。而node1对应的key是,比如说,key1.删除的基本想法是什么呢?
1.找到key1对应的那个node在哪里。这个用一个迭代就可以完成了。
2.删掉这个node
(1)如果这个node没有左右子树,那么直接删掉就好了。
(2)如果这个node只有左子树或者右子树,那么直接让左右子树缩进上来就好了。
(3)如果既有左子树又有右子树,那么就从左子树里面找出最大的node,用这个node来替换掉需要删除的那个节点。
举个栗子:有一棵BST:
5
3 7
1 4 6 8
figure1
(连接线自行脑补)
如果我们要删除1,那就是先去找1在哪里,找到之后呢,它属于2.(1)的情况,那就直接删除掉了。就变成:
5
3 7
4 6 8
figure2
如果这个时候我们要删除3,那么先找到3在哪里,然后它属于2.(2)的情况,那就让它的右子树(右子树只是对应这个具体的情况,同样地也可能是左子树)“缩进”上来顶替掉需要删除的那个节点。
5
4 7
6 8
figure3
最复杂的情况就是左右子树都在了。比如说我们在figure1中删掉5。我们找到5在哪里,发现它有左右子树,那么在它的左子树里面找出最大的那个元素——4.用4来代替到5,再迭代去删掉4就好了。
simple idea? Definetly.
但是作者在写起代码来却遇到了一个问题:2.(3)的情况中,比如说还是要删掉5,5确实被替换成了4,但是4这个节点却没有被删除掉!
来看看代码吧。
BinaryNode<int> * largest(BinaryNode<int> * &root){ if(root -> right == NULL) return root; else largest(root -> right); } void deleteThis(BinaryNode<int> * & root){ if(root -> left == NULL && root -> right == NULL){ root = NULL;//错误出现的地方 } else if(root -> left == NULL && root -> right != NULL ) root = root -> right; else if(root -> left != NULL && root -> right == NULL) root = root -> left; else{ BinaryNode<int> * large = largest(root -> left); BinaryNode<int> * largeFather = largestFather(root -> left); root -> elem = large -> elem; deleteThis(large); } } bool deletion(BinaryNode<int> * & root, int key){ if(root == NULL) return 0; if(root -> elem > key) return deletion(root -> left, key); else if(root -> elem < key) return deletion(root -> right, key); else if(root -> elem == key){ deleteThis(root); return 1; } }
这个原因是作者对指针的理解不够透彻。root确实是指向了一个节点,但是让它指向null,并非让该节点消失。所以应该添加delete root。这样子会让一个node消失。但是注意,这样子的迭代,并不能改变父节点中的指针。specifically, 在删除4的情况中,我们确实让large指针指向了null并且让4这个节点被删去,但是4的父节点,也就是3,它的右指针却以为4这个节点还在,并且仍然指向4.
后来的解决方法:
///增加此函数 BinaryNode<int> * largestFather(BinaryNode<int> * &root){ if(root -> right -> right == NULL) return root; else largest(root -> right); } //修改原deleteThis为如下: void deleteThis(BinaryNode<int> * & root){ if(root -> left == NULL && root -> right == NULL){ delete root; root = NULL;//修改出现的地方 } else if(root -> left == NULL && root -> right != NULL ) root = root -> right; else if(root -> left != NULL && root -> right == NULL) root = root -> left; else{ BinaryNode<int> * large = largest(root -> left); BinaryNode<int> * largeFather = largestFather(root -> left); root -> elem = large -> elem; //修改出现的地方 if(large -> left != NULL) large = large -> left; else{ delete large; largeFather -> right = NULL; } } }
当然,以上方法只是为了突出这个问题而这么写的,后来在其他资料中查到delete应该这么写会更加好,贴伪代码于此:
Node Delete(Node root, Key k) 1 if (root == null) // failed search 2 return null; 3 if (k == root.key) // successful search 4 return DeleteThis(root); 5 if (k < root.key) // k in the left branch 6 root.left = Delete(root.left, k); 7 else // k > root.key, i.e., k in the right branch 8 root.right = Delete(root.right, k); 9 return root; Node DeleteThis(Node root) 1 if root has two children 2 // replace root with its immediate predecessor p 3 p = Largest(root.left); 4 root.key = p.key; 5 root.left = Delete(root.left, p) 6 return root; 7 if root has only left child 8 return root.left 9 if root has only right child 10 return root.right 11 else // root has no children 12 return null Node Largest(Node root) 1 if root has no right child 2 return root 3 return Largest(root.right)
本文出自 “我才不写代码呢” 博客,请务必保留此出处http://nocodes.blog.51cto.com/9045813/1426563