红黑书删除 C 语言实现

举报
pdudo 发表于 2021/11/09 23:49:17 2021/11/09
【摘要】 红黑树删除推荐一个红黑树可视化网站: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html推荐一篇红黑树删除的博客: https://www.cnblogs.com/qingergege/p/7351659.html红黑树删除,按照 排序二叉树规则删除即可,只不过删除前需要根据周边的节点来判断删除节点后是否满足平衡条件,不...

红黑树删除

推荐一个红黑树可视化网站: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

推荐一篇红黑树删除的博客: https://www.cnblogs.com/qingergege/p/7351659.html

红黑树删除,按照 排序二叉树规则删除即可,只不过删除前需要根据周边的节点来判断删除节点后是否满足平衡条件,不平衡需要调整。

博客后面提供插入完整代码

红黑树删除,只需要跟着规则进行写就可以了

重点阐述我不太明白的点

  1. 删除调整的样式有哪些
  2. 删除后如何进行回溯

1. 什么是红黑树

红黑树是一种自平衡二叉查找树,巴拉巴拉— , 请注意前提,是一颗二叉查找树

关于二叉查找树: https://baike.baidu.com/item/二叉排序树/10905079?fromtitle=二叉查找树&fromid=7077965&fr=aladdin

2. 红黑树概念

  • 每个节点要么是红色,要么是黑色
  • 根节点和叶节点是黑色的(红黑树的叶节点是NULL LEAF,默认NULL节点为黑色)
  • 如果一个节点是红色,那么它的孩子是黑色的(不允许连续2个红节点,但是允许2个连续的黑节点)
  • 任意节点到叶节点的树链中包含相同数量的黑节点

红黑树图示

image.png

3. 二叉树删除规则

根据二叉树的删除规则,删除某个数据的时候,其删除的节点地址永远是 子节点,例如

image.png

删除110 这个节点,我们只需要将90这个节点(蓝色的),替换到 110 这个位置(绿色的),删除90这个节点(蓝色的),即可 完成删除110 这个操作,且不会破坏二叉树平衡

(将蓝色数据 复制 到 绿色节点,且将蓝色节点删除即可)

image.png

删除后图示

image.png

4. 红黑树删除图示

  1. 删除节点为 根节点
    直接删除

  2. 删除节点为 红色节点
    直接删除,不会影响平衡

  3. 删除节点为 黑色节点

  • 删除节点在父节点左边
    • 兄弟节点为红色
    • 兄弟节点为黑色 且 兄弟节点右子节点为 红色
    • 兄弟节点为黑色 且 兄弟节点左子节点为 红色
    • 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点
    • 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点
    • 若以上条件均不匹配,则进行回溯
  • 删除节点在父节点右边
    • 兄弟节点为红色
    • 兄弟节点为黑色 且 兄弟节点左子节点为 红色
    • 兄弟节点为黑色 且 兄弟节点右子节点为 红色
    • 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点
    • 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点
    • 若以上条件均不匹配,则进行回溯

4.1 删除情况图示

  • 删除节点为根节点

image.png

  • 删除节点为 红色节点

    例如删除85

image.png

红色节点,直接删除即可。

  • 删除黑色节点 且 删除节点为 左子节点

    • 兄弟节点为红色

      例如删除85

image.png

  • 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点

    例如删除 85

image.png

  • 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点

    例如删除 85

image.png

  • 兄弟节点为黑色 且 兄弟节点右子节点为 红色
    例如删除 85

image.png

  • 兄弟节点为黑色 且 兄弟节点左子节点为 红色
    例如删除 85

image.png

  • 删除黑色节点 且 删除节点为 右子节点
    • 兄弟节点为红色
      例如删除240

image.png

  • 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点

    例如删除240
    image.png

  • 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点

    例如删除 240

image.png

  • 兄弟节点为黑色 且 兄弟节点左子节点为 红色

    例如删除 240

image.png

  • 兄弟节点为黑色 且 兄弟节点右子节点为 红色

    例如删除 240
    image.png

4. 红黑树删除调整图示

4.1 需要删除的是根/红节点

如果遇到 需要删除根 / 红节点 直接删除即可

仅仅列举 待删除节点在父节点 左边的情况哈

4.2 兄弟节点为红色

例如删除85

image.png

先将待删除节点兄弟节点(240)染成黑色,再将父亲节点(160)染成红色

image.png

将这棵树向左旋转
image.png

如上情况又变为了: 【父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点】

4.3 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点

例如删除 85

image.png

直接删除掉 85 节点, 且将 兄弟节点 设置为红色 即可

image.png

如果遇到上述删除情况,是最麻烦的,虽然将 兄弟 节点设置为红色节点 后 160 这棵树平衡了,但是往上推,这棵树依旧不平衡,所以,需要将 待删除节点 挪至 160, 再进行下方的判断,【判断条件如删除图示条件】。

4.4 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点

例如删除 85

image.png

直接删除掉 85 , 将兄弟节点设置为 红节点, 将 父亲节点 设置为 黑节点 即可

image.png

调整完毕

4.5 兄弟节点为黑色 且 兄弟节点右子节点为 红色

例如删除 85
image.png

将85节点删掉
image.png

将爷爷节点(160)设置 黑色, 将 兄弟节点右孩子(275) 设置为 黑色

image.png

将这棵树向左旋转
image.png

调整完毕

4.6 兄弟节点为黑色 且 兄弟节点左子节点为 红色

image.png

以兄弟节点,向右旋转
image.png

染色,将兄弟节点子节点(230)染成黑色,将兄弟节点染成(240) 红色
image.png

这种情况回到了【兄弟节点为黑色 且 兄弟节点右子节点为 红色】

4.7 回溯

回溯缘由是因为 【父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点】

若对于待删除节点为左子树节点而言,删除黑节点后, 将右子树节点调整为红色

举例:

如下图 删除 55 节点
image.png

根据 【删除节点在父节点左边】【父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点】

调整为如下

且节点向上回溯,为 【69】 节点

image.png

根据【删除节点在父节点右边】【兄弟节点为黑色 且 兄弟节点左子节点为 红色】(删除节点在父节点右边未画出来,参考 【删除节点在父节点左边】【兄弟节点为黑色 且 兄弟节点右子节点为 红色】)

调整为如下

image.png

调整完毕

5. 删除代码实现

头文件

# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>

# define RED 1
# define BLACK 0

typedef struct {
	int data; // 数据节点
	struct TreeNode *left; // 左子树
	struct TreeNode *right; // 右字树
	int color;  // 二叉树颜色,1: 红色 0:黑色
	
} TreeNode , *PTreeNode;

搜索二叉树删除代码

bool deleteNode(PTreeNode *root,int data) {
	if (NULL == (*root)) return NULL;

	printf("删除节点为:%d\n",data);

	TreeNode *tmp = (*root);
	TreeNode *tmp2 = NULL;

	while (NULL != tmp) {
		if (tmp->data == data) {
			// 待删除的节点为头结点
			// 1. 左子树的最右节点代替头结点
			// 2. 右字树的最左节点代替头节点	

			if (NULL != tmp->left) {
				// 方案1
				tmp2 = tmp->left;
				while (NULL != tmp2->right) {
					tmp2 = tmp2->right;
				}
				//tmp->data = tmp2->data;
				delNodeFixup(root,tmp2, tmp);
				return true;


			} else if (NULL != tmp->right) {
				// 方案2
				tmp2 = tmp->right;
				while (NULL != tmp2->left) {
					tmp2 = tmp2->left;
				}
				//tmp->data = tmp2->data;
				delNodeFixup(root,tmp2, tmp);
				return true;

			} else {
				if (tmp == (*root)) {
					// 该树只有一颗根节点
					free(tmp);
					(*root) = NULL;
					return true;
				} else {
					// 删除的数据为叶子节点
					delNodeFixup(root,tmp, tmp);
					return true;
				}
			}
		}
		
		(data > tmp->data) ? (tmp = tmp->right) : (tmp = tmp->left);
	}
	return false;
}

删除修复代码

bool delNodeFixup(PTreeNode *root,PTreeNode delNode, PTreeNode replaceNode) {
	if (NULL == root) return false;

	// 删除的是红色
	if (RED == delNode->color) {
		nodeDel(root ,delNode ,replaceNode);
	} else {
	// 删除的是黑色
		delBlackNode(root,delNode,replaceNode);
	}
}

删除黑节点调整代码

// 删除节点调整
void delBlackNode(PTreeNode *root , PTreeNode delNode , PTreeNode replaceNode) {
	TreeNode *ss = delNode;

	while (ss != (*root)) {
		// 寻找父亲/兄弟等节点
		TreeNode *parent = NULL;
		TreeNode *brother = NULL;
		TreeNode *grandParent = NULL;
		TreeNode *childLeft = NULL;
		TreeNode *childRight = NULL;
		
		TreeNode *tmp = (*root);
		while (tmp != NULL) {
			if (tmp->data == ss->data) {
				break;
			}

			grandParent = parent;
			parent = tmp;

			(tmp->data < ss->data) ? (tmp = tmp->right) : (tmp = tmp->left);
		}		

		(ss == parent->left) ? (brother = parent->right) : (brother = parent->left);

		childLeft = brother->left;
		childRight = brother->right;

		// 删除节点在父节点左边
		if (ss == parent->left) {
			// 兄弟节点为红色
			if (RED == brother->color) {

				brother->left = parent;
				parent->right = childLeft;

				brother->color = BLACK;
				parent->color = RED;

				if (grandParent != NULL) {
					(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother);
				} else {
					(*root) = brother;
				}
				continue;
			}
			// 兄弟节点为黑色 且 兄弟节点右子节点为 红色
			if (NULL != childRight) {
				if ((BLACK == brother->color) && (RED == childRight->color)) {
					brother->left = parent;
					parent->right = childLeft;
				
					brother->color = parent->color;
					parent->color = BLACK;

					childRight->color = BLACK;

					if (grandParent != NULL) {
						(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother);
					} else {
						(*root) = brother;
					}
				
					break;
				}
			}
			// 兄弟节点为黑色 且 兄弟节点左子节点为 红色
			if (NULL != childLeft) {
				if ((BLACK == brother->color) && (RED == childLeft->color)) {
					TreeNode *childLeftRight = childLeft->right;

					parent->right = childLeft;
					childLeft->right = brother;
					brother->left = childLeftRight;
	
					brother->color = RED;
					childLeft->color = BLACK;

					continue;
				}
			}
			// 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((RED == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				parent->color = BLACK;
				break;
			}
			// 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((BLACK == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				// 进行回溯
				ss = parent;
				continue;
			}

			// 若以上条件均不匹配,则进行回溯
			brother->color = RED;
			ss = parent;
			continue;

		// 删除节点在父节点右边
		} else if (ss == parent->right) {
			// 兄弟节点为红色
			if (RED == brother->color) {
				brother->right = parent;
				parent->left = childRight;

				brother->color = BLACK;
				parent->color = RED;

				if (grandParent != NULL) {
					(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother) ;
				} else {
					(*root) = brother;
				}

				continue;
			}
			// 兄弟节点为黑色 且 兄弟节点左子节点为 红色
			if (NULL != childLeft) {
				if ((BLACK == brother->color) && (RED == childLeft->color)) {
					brother->right = parent;
					parent->left = childRight;
					
					brother->color = parent->color;
					parent->color = BLACK;
					
					childLeft->color = BLACK;
	
					if (grandParent != NULL) {
						(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother);
					} else {
						(*root) = brother;
					}
	
					break;
				}
			}
			// 兄弟节点为黑色 且 兄弟节点右子节点为 红色
			if (NULL != childRight) {
				if ((BLACK == brother->color) && (RED == childRight->color)) {
					TreeNode *childRightLeft = childRight->left;
	
					childRight->left = brother;
					brother->right = childRightLeft;
				
					parent->left = childRight;

					childRight->color = BLACK;
					brother->color = RED;
	
					continue;
				}

			}
			// 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((RED == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				parent->color = BLACK;
				break;
			}
			// 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((BLACK == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				// 回溯
				ss = parent;
				continue;
			}
			// 若以上条件均不匹配,则进行回溯
			brother->color = RED;
			ss = parent;
			continue;
		}	
	}
	
	// 删除节点
	nodeDel(root ,delNode ,replaceNode);
}

实际删除代码

// 删除节点
void nodeDel(PTreeNode *root , PTreeNode delNode , PTreeNode replaceNode) {
	TreeNode *parent = NULL;
	TreeNode *tmp = (*root);

	while (tmp != NULL) {
		if (tmp->data == delNode->data) break;

		parent = tmp;
		if (tmp->data < delNode->data) {
			tmp = tmp->right;
		} else {
			tmp = tmp->left;
		}
	}

	replaceNode->data = delNode->data;
	
	(delNode == parent->left) ? (parent->left = NULL) : (parent->right = NULL);
	free(delNode);
}

6. 完整删除代码实现

完整代码,包含插入,关于插入博客: 红黑树插入 C语言实现 - 王李 - 博客园 (cnblogs.com)

# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>

# define RED 1
# define BLACK 0

typedef struct {
	int data; // 数据节点
	struct TreeNode *left; // 左子树
	struct TreeNode *right; // 右字树
	int color;  // 二叉树颜色,1: 红色 0:黑色
	
} TreeNode , *PTreeNode;

// 删除节点
void nodeDel(PTreeNode *root , PTreeNode delNode , PTreeNode replaceNode) {
	TreeNode *parent = NULL;
	TreeNode *tmp = (*root);

	while (tmp != NULL) {
		if (tmp->data == delNode->data) break;

		parent = tmp;
		if (tmp->data < delNode->data) {
			tmp = tmp->right;
		} else {
			tmp = tmp->left;
		}
	}

	replaceNode->data = delNode->data;
	
	(delNode == parent->left) ? (parent->left = NULL) : (parent->right = NULL);
	free(delNode);
}

// 删除节点调整
void delBlackNode(PTreeNode *root , PTreeNode delNode , PTreeNode replaceNode) {
	TreeNode *ss = delNode;

	while (ss != (*root)) {
		// 寻找父亲/兄弟等节点
		TreeNode *parent = NULL;
		TreeNode *brother = NULL;
		TreeNode *grandParent = NULL;
		TreeNode *childLeft = NULL;
		TreeNode *childRight = NULL;
		
		TreeNode *tmp = (*root);
		while (tmp != NULL) {
			if (tmp->data == ss->data) {
				break;
			}

			grandParent = parent;
			parent = tmp;

			(tmp->data < ss->data) ? (tmp = tmp->right) : (tmp = tmp->left);
		}		

		(ss == parent->left) ? (brother = parent->right) : (brother = parent->left);

		childLeft = brother->left;
		childRight = brother->right;

		// 删除节点在父节点左边
		if (ss == parent->left) {
			// 兄弟节点为红色
			if (RED == brother->color) {

				brother->left = parent;
				parent->right = childLeft;

				brother->color = BLACK;
				parent->color = RED;

				if (grandParent != NULL) {
					(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother);
				} else {
					(*root) = brother;
				}
				continue;
			}
			// 兄弟节点为黑色 且 兄弟节点右子节点为 红色
			if (NULL != childRight) {
				if ((BLACK == brother->color) && (RED == childRight->color)) {
					brother->left = parent;
					parent->right = childLeft;
				
					brother->color = parent->color;
					parent->color = BLACK;

					childRight->color = BLACK;

					if (grandParent != NULL) {
						(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother);
					} else {
						(*root) = brother;
					}
				
					break;
				}
			}
			// 兄弟节点为黑色 且 兄弟节点左子节点为 红色
			if (NULL != childLeft) {
				if ((BLACK == brother->color) && (RED == childLeft->color)) {
					TreeNode *childLeftRight = childLeft->right;

					parent->right = childLeft;
					childLeft->right = brother;
					brother->left = childLeftRight;
	
					brother->color = RED;
					childLeft->color = BLACK;

					continue;
				}
			}
			// 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((RED == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				parent->color = BLACK;
				break;
			}
			// 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((BLACK == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				// 进行回溯
				ss = parent;
				continue;
			}

			// 若以上条件均不匹配,则进行回溯
			brother->color = RED;
			ss = parent;
			continue;

		// 删除节点在父节点右边
		} else if (ss == parent->right) {
			// 兄弟节点为红色
			if (RED == brother->color) {
				brother->right = parent;
				parent->left = childRight;

				brother->color = BLACK;
				parent->color = RED;

				if (grandParent != NULL) {
					(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother) ;
				} else {
					(*root) = brother;
				}

				continue;
			}
			// 兄弟节点为黑色 且 兄弟节点左子节点为 红色
			if (NULL != childLeft) {
				if ((BLACK == brother->color) && (RED == childLeft->color)) {
					brother->right = parent;
					parent->left = childRight;
					
					brother->color = parent->color;
					parent->color = BLACK;
					
					childLeft->color = BLACK;
	
					if (grandParent != NULL) {
						(parent == grandParent->left) ? (grandParent->left = brother) : (grandParent->right = brother);
					} else {
						(*root) = brother;
					}
	
					break;
				}
			}
			// 兄弟节点为黑色 且 兄弟节点右子节点为 红色
			if (NULL != childRight) {
				if ((BLACK == brother->color) && (RED == childRight->color)) {
					TreeNode *childRightLeft = childRight->left;
	
					childRight->left = brother;
					brother->right = childRightLeft;
				
					parent->left = childRight;

					childRight->color = BLACK;
					brother->color = RED;
	
					continue;
				}

			}
			// 父亲节点为红色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((RED == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				parent->color = BLACK;
				break;
			}
			// 父亲节点为黑色 且 兄弟节点为黑色 且 兄弟节点无子节点
			if ((BLACK == parent->color) && (NULL == childLeft) && (NULL == childRight)) {
				brother->color = RED;
				// 回溯
				ss = parent;
				continue;
			}
			// 若以上条件均不匹配,则进行回溯
			brother->color = RED;
			ss = parent;
			continue;
		}	
	}
	
	// 删除节点
	nodeDel(root ,delNode ,replaceNode);
}

bool delNodeFixup(PTreeNode *root,PTreeNode delNode, PTreeNode replaceNode) {
	if (NULL == root) return false;

	// 删除的是红色
	if (RED == delNode->color) {
		nodeDel(root ,delNode ,replaceNode);
	} else {
	// 删除的是黑色
		delBlackNode(root,delNode,replaceNode);
	}
}

bool deleteNode(PTreeNode *root,int data) {
	if (NULL == (*root)) return NULL;

	printf("删除节点为:%d\n",data);

	TreeNode *tmp = (*root);
	TreeNode *tmp2 = NULL;

	while (NULL != tmp) {
		if (tmp->data == data) {
			// 待删除的节点为头结点
			// 1. 左子树的最右节点代替头结点
			// 2. 右字树的最左节点代替头节点	

			if (NULL != tmp->left) {
				// 方案1
				tmp2 = tmp->left;
				while (NULL != tmp2->right) {
					tmp2 = tmp2->right;
				}
				//tmp->data = tmp2->data;
				delNodeFixup(root,tmp2, tmp);
				return true;


			} else if (NULL != tmp->right) {
				// 方案2
				tmp2 = tmp->right;
				while (NULL != tmp2->left) {
					tmp2 = tmp2->left;
				}
				//tmp->data = tmp2->data;
				delNodeFixup(root,tmp2, tmp);
				return true;

			} else {
				if (tmp == (*root)) {
					// 该树只有一颗根节点
					free(tmp);
					(*root) = NULL;
					return true;
				} else {
					// 删除的数据为叶子节点
					delNodeFixup(root,tmp, tmp);
					return true;
				}
			}
		}
		
		(data > tmp->data) ? (tmp = tmp->right) : (tmp = tmp->left);
	}
	return false;
}

PTreeNode InsertFixup(PTreeNode *root,PTreeNode newNode) {

	TreeNode *parent = NULL; // 父亲节点
	TreeNode *grandParent = NULL; // 爷爷节点 
	TreeNode *greatGrandParent = NULL; // 祖爷爷节点
	TreeNode *uncle = NULL; // 叔叔节点
	int uncleColor = 0; // 叔叔节点颜色,默认为黑色

	while (true) {
		//
		// 寻找节点 父亲/爷爷祖爷爷节点
		TreeNode *tmp = (*root);
		while (tmp != NULL) {
			if (newNode->data == tmp->data) {
				break;
			}
			greatGrandParent = grandParent;
			grandParent = parent;
			parent = tmp;

			(newNode->data > tmp->data) ? (tmp = tmp->right) : (tmp = tmp->left);
		}

		// 当前节点是根节点,染成黑色
		if (newNode == (*root)) newNode->color = BLACK;
		
		if (grandParent == NULL) break;

		// 获取叔叔节点
		(parent == grandParent->left) ? (uncle = grandParent->right) : (uncle = grandParent->left);

		// 获取叔叔节点颜色
		if (uncle != NULL) uncleColor = uncle->color;

		// 染色操作
		if ((parent->color == RED) && (uncleColor == RED)) {
			printf("红黑树不平衡,对节点 %d 进行染色操作\n",newNode->data);
			parent->color = BLACK;
			uncle->color = BLACK;
			grandParent->color = RED;
	
			newNode = grandParent;
			continue;
		}

		// 父节点为红色,叔叔节点为黑色,则需要进行旋转
		if ((parent->color == RED) && uncleColor == BLACK) {
			// 左左
			if ((parent == grandParent->left) && (newNode == parent->left)) {
				printf("红黑树不平衡,进行左左旋转\n");
				grandParent->left = NULL;

				TreeNode *oldParentRight = parent->right;				

				parent->right = grandParent;
				grandParent->left = oldParentRight;

				if ((*root) == grandParent) {
					(*root) = parent;
				} else {
					(greatGrandParent->left == grandParent) ? (greatGrandParent->left = parent) : (greatGrandParent->right = parent);
				}

				// 染色
				newNode->color = RED;
				grandParent->color = RED;
				parent->color = BLACK;
				//continue;
				break;
			// 左右
			} else if ((parent == grandParent->left) && (newNode == parent->right)) {
				printf("红黑树不平衡,进行左右旋转\n");
				grandParent->left = newNode;

				TreeNode *newNodeLeft = newNode->left;
				

				newNode->left = parent;	
				parent->right = newNodeLeft;		

				TreeNode *newNodeRight = newNode->right;
				newNode->right = grandParent;
				grandParent->left = newNodeRight;
				//newNode->left = parent;

				// 若要旋转的树是根节点
				if ((*root) == grandParent) {
					(*root) = newNode;
				} else {
					// 要旋转的树非根节点
					(greatGrandParent->left == grandParent) ? (greatGrandParent->left = newNode) : (greatGrandParent->right = newNode);
				}

				parent->color = RED;
				grandParent->color = RED;
				newNode->color = BLACK;
				//continue;
				break;

			// 右左
			} else if ((parent == grandParent->right) && (newNode == parent->left)) {
				printf("红黑树不平衡,进行右左旋转\n");
				parent->left = NULL;
				
				TreeNode *newNodeRight = newNode->right;
				newNode->right = parent;
				parent->left = newNodeRight;

				grandParent->right = newNode;

				TreeNode *newNodeLeft = newNode->left;
				newNode->left = grandParent;
				grandParent->right = newNodeLeft;
				
				
				// 要旋转的树是根节点
				if ((*root) == grandParent) {
					(*root) = newNode;

				} else {
					// 要旋转的树是非根节点
					(greatGrandParent->left == grandParent) ? (greatGrandParent->left = newNode) : (greatGrandParent->right = newNode);
				}

				// 染色
				newNode->color = BLACK;
				grandParent->color = RED;
				parent->color = RED;
				//continue;
				break;

			// 右右	
			} else if ((parent == grandParent->right) && (newNode == parent->right)) {
				printf("红黑树不平衡,进行右右旋转\n");
				grandParent->right = NULL;

				TreeNode *oldParentLeft = parent->left;
				parent->left = grandParent;
				grandParent->right = oldParentLeft;
				
				// 要旋转的树是根节点
				if ((*root) == grandParent) {
					(*root) = parent;

				} else {
					// 要旋转的树是非根节点
					(greatGrandParent->left == grandParent) ? (greatGrandParent->left = parent) : (greatGrandParent->right = parent);
				}
				
				// 染色
				grandParent->color = RED;
				newNode->color = RED;
				parent->color = BLACK;
				//continue;
				break;
			}
		}
		break;
	}
	return (*root);
}

PTreeNode Insert(PTreeNode *root,int data) {

	printf("插入数据: %d\n",data);
	TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
	newNode->data = data;
	newNode->color = RED; // 新增节点染成红色

	TreeNode *parent = NULL;
	TreeNode *grandParent = NULL;

	if (NULL == (*root)) {
		newNode->color = BLACK; // 将头结点染成黑色
		return newNode;
	} else {
		TreeNode *tmp = (*root);
		while (tmp != NULL) {
			//printf("插入查找值: %d\n",tmp->data);
			grandParent = parent;
			parent = tmp;
			
			if (data > tmp->data){
				tmp = tmp->right;
			} else if (data < tmp->data){
				tmp = tmp->left;
			} else {
				printf("%d 该值已经存在\n",data);
			}
		}
		if (data > parent->data) {
			parent->right = newNode;
			//printf("parent data:%d newNode data:%d\n",parent->data,newNode->data);
		} else {
			parent->left = newNode;
		}
	}
	// 如果插入父节点是黑色,则保持不变
	if (parent->color == BLACK) return (*root);

	// 进行插入修复
	return InsertFixup(root,newNode); 
}

// 前序遍历
void Print1(TreeNode *root) {
	if (NULL == root) return;
	printf("[颜色:%s  数据:%d]\t",(root->color == RED) ? ("红"):("黑") ,root->data);
	Print1(root->left);
	Print1(root->right);
}

// 中序遍历
void Print2(TreeNode *root) {
	if (NULL == root) return;
	Print2(root->left);
	printf("[颜色:%s  数据:%d]\t",(root->color == RED) ? ("红"):("黑") ,root->data);
	Print2(root->right);
}

int main() {
	TreeNode *root = NULL;

	int num[] = {55,30,27,29,32,42,123,21,69,200,18};	

	int i;
	for (i=0;i<sizeof(num)/sizeof(int);i++) {
		root = Insert(&root,num[i]);
	}

	printf("前序遍历:\n");
	Print1(root);
	printf("\n");
	printf("后续遍历:\n");
	Print2(root);
	printf("\n");
	printf("\n");
	printf("\n");

	int delNum[] = {200,18,123,21,69,29};
	for (i=0;i<sizeof(delNum)/sizeof(int);i++) {
		deleteNode(&root,delNum[i]);

	}

	printf("前序遍历:\n");
	Print1(root);
	printf("\n");
	printf("后续遍历:\n");
	Print2(root);
	printf("\n");


	return 0;
}

7.代码测试

# gcc RedBlackTreeDel.c -w -g
# ./a.out 
插入数据: 55
插入数据: 30
插入数据: 27
红黑树不平衡,进行左左旋转
插入数据: 29
红黑树不平衡,对节点 29 进行染色操作
插入数据: 32
插入数据: 42
红黑树不平衡,进行左右旋转
插入数据: 123
红黑树不平衡,对节点 123 进行染色操作
插入数据: 21
插入数据: 69
红黑树不平衡,进行右左旋转
插入数据: 200
红黑树不平衡,对节点 200 进行染色操作
红黑树不平衡,进行右右旋转
插入数据: 18
红黑树不平衡,对节点 18 进行染色操作
红黑树不平衡,对节点 27 进行染色操作
前序遍历:
[颜色:黑  数据:42]      [颜色:黑  数据:30]      [颜色:红  数据:27]      [颜色:黑  数据:21]      [颜色:红  数据:18]      [颜色:黑  数据:29]  [颜色:黑  数据:32]      [颜色:黑  数据:69]      [颜色:黑  数据:55]      [颜色:黑  数据:123]     [颜色:红 数据:200]
后续遍历:
[颜色:红  数据:18]      [颜色:黑  数据:21]      [颜色:红  数据:27]      [颜色:黑  数据:29]      [颜色:黑  数据:30]      [颜色:黑  数据:32]  [颜色:黑  数据:42]      [颜色:黑  数据:55]      [颜色:黑  数据:69]      [颜色:黑  数据:123]     [颜色:红数据:200]


删除节点为:200
删除节点为:18
删除节点为:123
删除节点为:21
删除节点为:69
删除节点为:29
前序遍历:
[颜色:黑  数据:30]      [颜色:黑  数据:27]      [颜色:红  数据:42]      [颜色:黑  数据:32]      [颜色:黑  数据:55]
后续遍历:
[颜色:黑  数据:27]      [颜色:黑  数据:30]      [颜色:黑  数据:32]      [颜色:红  数据:42]      [颜色:黑  数据:55]
# 
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。