All pastes #976227 Raw Edit

Mine

public text v1 · immutable
·published 2008-04-08 00:21 UTC
rendered paste body
//returns -1 on failure, 
int BinTree::remove(dwelling & result) {
	return del(root,result);
}

//we are going to delete a node with a goal of 'no child left behind'
int BinTree::del(node * curroot,  dwelling &d) {
	if (curroot == NULL) {
		//empty tree D:
		return -1;
	} else if (strcmp(d.location,curroot->d.location) < 0) {
		return del(curroot->left,d);
	} else if (strcmp(d.location,curroot->d.location) > 0) {
		return del(curroot->right,d);
	} else {
		//remove this node
		if (curroot->right == NULL && curroot->left == NULL) {
			//sucessor is null.  no children
		} else if (curroot->right != NULL && curroot->left == NULL) {	//one child
			curroot = curroot->right;
		} else if (curroot->left == NULL && curroot->left != NULL) {	//one child
			curroot = curroot->left;
		} else {						//both children, we have to find a sucessor!
			node * successor;
			successor = curroot->right;
			node * prev = curroot;
			//now go left all the way
			while (successor->left != NULL) {
				prev = successor;
				successor = successor->left;
			}
			prev->left = successor->right;
			//copy sucessor's data  into root
			copyDwelling(successor->d,curroot->d);
			delete successor;
		}
		return 1;	//we removed the node
	}
}