[数据结构与算法]数据结构——二叉查找树(BST)的删除

数据结构——二叉树(BST)的删除

前言

一、BST删除的几种情况

如果要删除的是树叶，那么可以立即删除，如果有一个儿子，就直接让该节点删除并让儿子占有该位置。关键是有两个孩子的情况：分别有以下几种方法对两个孩子的情况进行实现。

二、节点删除方法

1.一般方法

void remove(const Comparable & x, BinaryNode * & t)
{
	if(t == nullptr)
		return;
	if(x < t->element)
		remove(x, t->right);
	else if(t->left != nullptr && t->right != nullptr)//有两个孩子
	{
		t->element = findMin(t->right)->element;
		remove(t->element, t->right);
	}
	else
	{
		BinaryNode *oldNode = t;
		t = (t->left != nullptr) ? t->left : t->right;
		delete oldNode;
	}
}

上面代码的效率不高，因为它沿着该树进行两趟搜索以查找和删除右子树的最小节点。这也是书上给出的最简单方法。其实还有更易理解而且更粗暴的方式，那就是直接让左子树移动到右子树最左节点的左子树上。然后让右子树变成root，但是这样就会增加树的高度。

2.对1方法的优化

代码如下：

BinaryNode removeMin(BinaryNode * & t) const
{
	if( t == nullptr)
	{
		return nullptr;
	}
	if(t->left == nullptr)
	{
		BinaryNode temp = *t;
		if(t->right != nullptr)
		{
			*t = *t->right;
			delete t->right;
		}
		else
			delete t;
		return temp;
	}
	return removeMin(t->left);
}
void remove(const Comparable & x, BinaryNode * & t)
{
	if(t == nullptr)
		return;
	if(x < t->element)
		remove(x, t->right);
	else if(t->left != nullptr && t->right != nullptr)//有两个孩子
	{
		t->element = removeMin(t->right).element;
	}
	else
	{
		BinaryNode *oldNode = t;
		t = (t->left != nullptr) ? t->left : t->right;
		delete oldNode;
	}
}

这样就通过一个removeMin函数达到只找一趟的效果了。

3.懒汉删除（前继和后继）

其实还提书中还提到了一种懒汉删除的做法,它在node结构题内部新添加了一个用于计算重复次数的count变量 并在tree 添加了theSize 和 delSize变量

bool findMin(BinaryNode *t)  {
	if (t) {
		if (findMin(t->left)) return true;
		if (t->count>0) {
			min = t;
			return true;
		}
		return findMin(t->right);
	}
	return false;
}

void insert(const Comparable & x, BinaryNode * & t){
	if (t == nullptr){
		++theSize;
		t = new BinaryNode{ x, nullptr, nullptr };
	}
	else if (x<t->element)
		insert(x, t->left);
	else if (x>t->element)
		insert(x, t->right);
	else ++t->count;
}
void remove(const Comparable & x, BNode * & t){
	if (t == nullptr)return;
	if (x<t->element)
		remove(x, t->left);
	else if (x>t->element)
		remove(x, t->right);
	else if (t->count>0 && --(t->count) == 0 && ++delSize >= --theSize)
	{
	//若count大于0,则减1;若减1后为0,则delSize加1 theSize减1;
	//若delSize>=theSize,则执行delete操作
		deleteNodes(root); //真正的删除操作
		delSize = 0;       //delSize归零
	}
}
void deleteNodes(BinaryNode * & t) {
	if (t == nullptr) return;//空子树,do nothing
	if (t->count == 0) {
		//t需要被删除
		if ((t->left != nullptr) && (t->right != nullptr)) {
			if (findMin(t->right)) {
			//t的两个子树均非空,且在它的右子树中找到了"可用"的最小结点,count > 0
				t->element = min->element;
				t->count = min->count;
				min->count = 0;//右子树中的最小结点即将被删除
				deleteNodes(t->left);
				deleteNodes(t->right);
			}
			else if (findMax(t->left)) {
				t->element = max->element;
				t->count = max->count;
				max->count = 0;
				deleteNodes(t->left);
				deleteNodes(t->right);
			}
			else //t的右子树中的所有结点的count均为0,则将其置空.
				makeEmpty(t);
		}
		else {
			BNode *oldnode = t;
			t = t->left ? t->left : t->right;
			delete oldnode;
			oldnode = nullptr;
			if (t != nullptr) deleteNodes(t);//若新的t非空,继续对它执行删除操作
		}
	}
	else {//t不需要被删除,继续在它的子树中查找
		deleteNodes(t->left);
		deleteNodes(t->right);
	}
}