一起学习交流~

红黑树-02-插入和调整(重点)

算法 laomuji 10个月前 (11-26) 807次浏览 已收录 0个评论

一、插入

插入和普通的二叉搜索树一样,但是插入过后需要进行调整,使红黑树不违反规定

这个比较简单,直接上代码

	/*
		向二叉树插入数据
		成功返回1,失败返回0
	*/
	int insert(T value) {
		//创建需要插入的节点
		Node* insertNode = new Node{value,nullptr,nullptr,COLOR::RED,nullptr};
		//插入节点
		Node* currentNode = root;//需要插入的节点
		Node* lastNode = nullptr;//需要插入的节点的上一个节点
		while (currentNode != nullptr){
			lastNode = currentNode;
			if (currentNode->value > insertNode->value) {
				//插入值小于当前值,往左找
				currentNode = currentNode->left;
			}
			else if (currentNode->value < insertNode->value) {
				//插入值大于当前值,往右找
				currentNode = currentNode->right;
			}
			else{
				//找到了,不允许插入
				delete insertNode;
				return 0;
			}
		}

		if (lastNode == nullptr) root = insertNode;
		else if (lastNode->value > insertNode->value) lastNode->left = insertNode;
		else lastNode->right = insertNode;
		//设置父节点
		insertNode->parent = lastNode;
		//调整红黑树,如果不调整 就是一个普通的二叉排序树
		insertFixUp(insertNode);
		//增加长度
		count++;
		return 1;
	}

二、调整

调整是重点,插入有7种情况,要根据这7种情况进行不同的调整,直到不违反红黑树规定为止

规定:

(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

情况1,很好理解,违反了第二条,进行调整


情况2,没有违反规定


情况3, 违反规定4

没看懂情况3的祖父节点为什么要变红?没关系,先看下一种情况,看完情况4我再对情况3进行解释


情况4,违反规定4

对情况3祖父节点变红进行解释:


情况5,违反规定4


情况6,违反规定4


情况7,违反规定4

	/*
		红黑树插入数据后调整颜色及旋转
	*/
	void insertFixUp(Node* insertNode) {
		Node* child = insertNode;//子节点
		//当子节点为红色时,需要判断是否需要调整
		while (child->color == COLOR::RED)
		{
			Node* parent = child->parent;//父节点

			//情况1 插入的是根节点
			//若父节点为空,则当前节点为根节点
			if (parent == nullptr) {
				//把根节点设置为黑色,就不再违反红黑树规定
				child->color = COLOR::BLACK;
				return;
			}

			//情况2 父节点为黑色
			//若父节点为黑色,直接插入即可
			if (parent->color == COLOR::BLACK) {
				return;
			}
			//此时,父和子节点都为红色
			Node* uncle = nullptr;//叔叔节点
			Node* grand = parent->parent;

			//根据父节点 判断叔叔节点是左孩子还是右孩子
			if (parent == grand->left) {
				uncle = grand->right;
			}
			else{
				uncle = grand->left;
			}

			//情况3 父红,子红,叔红
			if (uncle != nullptr && uncle->color == COLOR::RED) {
				parent->color = COLOR::BLACK;
				uncle->color = COLOR::BLACK;
				grand->color = COLOR::RED;
				child = grand;
				continue;
			}

			//此时 父红 子红 叔黑

			//若父为祖父左孩
			if (parent == grand->left) {

				if (child == parent->left) {
					//情况4 父红 子红 叔黑 父为祖父左孩 子为父左孩
					grand->color = COLOR::RED;
					parent->color = COLOR::BLACK;
					rightRotate(parent);
					continue;
				}
				else
				{
					//情况5 父红 子红 叔黑 父为祖父左孩 子为父右孩
					grand->color = COLOR::RED;
					child->color = COLOR::BLACK;
					leftRotate(child);
					rightRotate(child);
					continue;
				}
			}
			else{
				//若父为祖父右孩

				if (child == parent->right) {
					//情况6 父红 子红 叔黑 父为祖父右孩 子为父右孩
					grand->color = COLOR::RED;
					parent->color = COLOR::BLACK;
					leftRotate(parent);
					continue;
				}
				else{
					//情况7 父红 子红 叔黑 父为祖父右孩 子为父左孩
					grand->color = COLOR::RED;
					child->color = COLOR::BLACK;
					rightRotate(child);
					leftRotate(child);
				}
			}
		}
	}

调整是重点,一定要好好理解

喜欢 (6)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论