首页 > 代码库 > 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