首页 > 代码库 > 【算法导论】二叉搜索树的插入和删除

【算法导论】二叉搜索树的插入和删除

        上一篇说了有关二叉树遍历的三种方式,文本将继续探讨如何实现二叉搜索树的插入和删除节点。

        在继续之前,我们先来了解两个概念:前驱和后继。


一、后继和前驱


        后继:如果所有的关键字互不相同,则一个节点x的后继是大于x.key的最小关键字的节点。


        前驱:如果所有的关键字互不相同,则一个节点x的前驱是小于x.key的最大关键字的节点。


        如果联系二叉搜索树的性质:

        节点的key值总是大于它的左节点(如果存在)的key值并且小于它的右节点(如果存在)的key值。那么我们容易推知:如果一个节点有右子树,它后继即是它的右子树的最“左”端的节点,也即右子树的最左节点,否则它的后继位于它的某个父或祖父点,这个父或祖父节点有最后一次的左分支指向当前节点所在的子树;而一个节点如果有左子树,它的前驱即是它的左子树的最“右”端的节点,也即左子树的最大节点,否则它的前驱位于它的某个父或者祖父节点,这个父或者祖父节点有最后一次的右分支指向当前节点所在的子树。

        了解了上面的内容,就不难给出前驱和后继的代码:


后继:

	/*
	 * 求x节点的后继,后继的key值为大于x.key的最小值
	 */
	node* successor(node* x) {
		if (x->right != NULL) {
			//右子树中的最小值,没有左节点
			return minimum(x->right);
		}

		node* y = x->parent;

		while (y != NULL && x == y->right) {
			x = y;
			y = y->parent;
		}
		return y;
	}



前驱:

	/*
	 * 求x节点的前驱,前驱的key值为小于x.key的最大值
	 */
	node* predessor(node* x) {
		if (x->left != NULL) {
			//左子树中的最大值,没有右节点
			return maximum(x->left);
		}

		node* y = x->parent;
		while (y != NULL && x == y->left) {
			x = y;
			y = y->parent;
		}
		return y;
	}


二、节点的插入


        插入的操作相对比较简单,我们只需要注意满足二叉树节点之间的关系,以及注意树是否为空的判断即可,代码如下:


递归的方式插入:

	/*
	 * 递归方式插入,r:当前递归遍历到的节点,pre:r的父节点,x要插入的节点
	 */
	void tree_insert(node* pre, node* r, node*x) {
		if (r == NULL) {
			if (pre == NULL) {
				this->root = x;
			} else if (pre->key > x->key) {
				pre->left = x;
			} else {
				pre->right = x;
			}
			x->parent = pre;
		} else {
			if (r->key > x->key) {
				tree_insert(r, r->left, x);
			} else {
				tree_insert(r, r->right, x);
			}
		}
	}

	void tree_insert(node* x) {
		tree_insert(NULL, root, x);
	}


非递归方式插入:

	/*
	 * 插入一个关键值为key的节点
	 */
	void tree_insert(int key) {
		node* n = new node(key);
		node* back = NULL;
		if (root == NULL) {
			root = n;
		} else {
			node* current = root;

			while (current != NULL) {
				back = current;
				if (current->key > key) {
					current = current->left; //左边放小的key值
				} else {
					current = current->right; //右边放大的key值
				}
			}

			if (back == NULL) {
				//表明树是空树
				this->root = n;
			} else if (back->key > key) {
				back->left = n;
			} else {
				back->right = n;
			}
			n->parent = back;
		}
	}


三、节点的删除


        二叉搜索树删除节点的操作比较复杂,主要考虑以下几种情况:


        ①要删除的节点没有孩子,那么直接删除即可


        ②要删除的节点只有一个孩子,那么将孩子放到节点位置,再删除节点即可


        ③要删除的节点有两个孩子,那么可以寻找节点的后继。

        由于有两颗子树,所以它的后继一定在右子树中,且是右子树中最小的那个节点,所以没有左子节点。这里又要分量小细分情况:如果这个后继节点就是要删除节点的右子节点,那么使用右子节点替换原节点,再删除原节点即可;如果这个后继节点并不是要删除节点右子节点,而是在右子树的下层之中,那么要先用后继的右子树替换后继,然后再用后继节点替换要删除的节点。


        上面提到的“替换”操作,实际上是一种节点的“移植”,我们将这个操作抽取出来,以方便使用:


	/*
	 * 移植操作:
	 * 用以b为根的子树去替换以a为根的子树,这里只管替换,不管a的处理,也不管b的值是否合适,
	 * 也不管b节点左右子树的处理
	 */
	void transplant(node* a, node* b) {
		if (b == NULL) {
			return;
		}
		if (a->parent == NULL) {
			root = b;
		}

		if (a->parent->left == a) {
			//a是其父节点的左节点
			a->parent->left = b;
		} else {
			a->parent->right = b;
		}

		if (b != NULL) {
			b->parent = a->parent;
		}
	}


节点的删除操作:

	void tree_delete(node* n) {
		if (n == NULL) {
			return;
		}
		if (n->left == NULL) { //如果左子节点为空,那么最多只会有一个右节点,直接执行移植操作即可
			transplant(n, n->right);
		} else if (n->right == NULL) { //如果左子节点不为空,而右子节点为空,则只有一个左子节点,也可以直接执行移植操作
			transplant(n, n->left);
		} else {
			//左右两个子节点都不为空的情况
			node* succ = minimum(n->right); //求右子树中的最小值

			if (succ == n->right) { //如果suc是n的直系右节点
				transplant(succ, succ->right);
				transplant(n, succ);
				succ->left = n->left;//因为是直系右节点,所以只需要处理左子树即可
				succ->left->parent = succ;

			} else { //如果suc不是n的直系右节点

				transplant(succ, succ->right); //将后继的右子树替换后继
				transplant(n, succ); //将后继替换要删除的节点
				succ->parent = n->parent;
				succ->right = n->right;//处理右子树
				succ->left = n->left;
				succ->left->parent = succ;//处理左子树
				succ->right->parent = succ;
			}
		}
		delete n;
	}


至此就完成了删除的操作。










【算法导论】二叉搜索树的插入和删除