数据结构中红黑树的详细解析

typedef struct TREENODE
{
	struct TREENODE *father;
	struct TREENODE *left;
	struct TREENODE *right;
	int value;
}tNode;

void insertNode(tNode* root, int val) {
	tNode* new = (tNode*)malloc(sizeof(tNode));
	new -> value = val;
	new -> left = NULL;
	new -> right = NULL;
	while (true) {
		if (root -> value < val)
			if (root -> right != NULL)
				root = root -> right;
			else {
				// 右子节点不存在,则新节点成为右子节点
				new -> father = root;
				root -> right = new;
				return;		// 完成赋值之后函数结束
			}
		else 
			if (root -> !=NULL)
				root = root -> left
			else {
				new -> father = root;
				root -> left = new;
				return;
			}
	}
}

// 打印二叉搜索树,输入的值为节点和节点序
void printBST(tNode* root, int start) {
	printf("the %dth node is %d\n",start, root -> value);
	// 如果当前节点有子节点,则继续打印这个子节点和节点序
	if (root -> left != NULL) 
		printBST(root -> left, start + 1);
	if (root -> right) 
		printBST(root -> right, start + 1)
}

int main() {
	tNode* root;
	root -> left = NULL;
	root -> right = NULL;
	root -> value = 10;

	int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
	for (int i = 0; i < 10; i ++)
		inserNode(root, init[i]);

	printBST(root, 0);
	return 0; 
}

// 通过节点的值搜索节点的位置,其中root为根节点
tNode* searchBST(tNode* root, int val) {
	while (root -> value != val) {
		if (root -> value < val && root -> right != NULL)
			root = root -> right;
		else if (root -> value > val && root -> left != NULL)
			root = root -> left;
		else
			return FALSE;
	}
	return root;
}

// 删除节点的值,root为根节点,delNode为待删除节点
void deleteNode(tNode* delNode) {
	if (delNode -> left == NULL && delNode -> right == NULL) {
		if (delNode -> value > pNode -> value)
			pNode -> right = NULL;
		else
			pNode -> left = NULL;
	}
	else if (delNode -> left == NULL && delNode -> right == NULL) {
		int val = delNode -> value;
		// 交换当前节点与右子节点的值
		delNode -> value = delNode -> right -> value;
		delNode -> right -> value = val;
		deleteNode(delNode -> right);	// 删除右节点
	}
	else {
		tNode* pNode = (delNode -> left == NULL) ? delNode -> right : delNode ->left;
		delNode -> value = pNode -> value;
		delNode -> right = pNode -> right;
		delNode -> left = pNode -> left;
	}
}

int main() {
	tNode* root;
	root -> left = NULL;
	root -> right = NULL;
	root -> value = 10;
	int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
	for (int i = 0; i < 10; i++)
		insertNode(root, init[i]);
	tNode* sNode = searchBST(root, 5);
	deleteNode(sNode);
	printBST(root, 0);
	return 0;
}

#define RIGHT 1
#define LEFT 0

// 二叉树的传统旋转节点操作
// flag为LEFT时为左旋,flag为RIGHT时为右旋
void rotNode(tNode* xNode, int flag) {
	tNode* yNode;
	if (flag == LEFT) {
		yNode == xNode -> right;
		xNode -> father -> right = yNode;	// y成为x父节点的右子节点
	} else {
		yNode == xNode -> left;
		xNode -> father -> left = yNode;	 
	}	

	yNode -> father = xNode -> father;		// x的父节点成为y的父节点
	xNode -> father = yNode;				// y成为x的父节点

	if (flag == LEFT) {
		yNode -> left -> father = xNode;	// y的左子节点成为x的子节点
		xNode -> right = yNode -> left;
		yNode -> left = xNode;
	} else {
		yNode -> right -> father = xNode;
		xNode -> left = yNode -> right;
		yNode -> right = xNode;
	}
	
} 

int main() {
	tNode* root;
	root -> left = NULL;
	root -> right = NULL;
	root -> value = 10;
	int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
	for (int i = 0; i < 10; i++)
		insertNode(root, init[i]);
	tNode* sNode = searchBST(root, 5);
	rotNode(sNode, LEFT);
	printBST(root, 0);
	return 0;
}

// 替换意义上的旋转操作,sNode为子节点,pNode为父节点
void turnNode(tNode *sNode, tNode* pNode) {
	if (sNode == pNode -> right) {
		sNode -> left -> father = pNode;
		pNode -> right = sNode ->left;
		sNode -> left = pNode;
	} else {
		sNode -> right -> father = pNode;
		pNode -> left = sNode -> right;
		sNode -> right = pNode;
	}

	sNode -> father = pNode -> father;
	pNode -> father = sNode;
}

#define RED 0
#define BLACK 0
typedef struct rbNODE
{
	struct rbNODE* father;
	struct rbNODE* left;
	struct rbNODE* right;
	int value;
	int color;
}rbNODE;

// 调整红黑树节点
void adjust(rbNode* node) {
	rbNode* pNode = node -> father; // 父节点
	rbNode* qNode;

	while (pNode -> color = RED) {
		int flag = pNode == pNode -> father -> left ? LEFT : RIGHT;
		qNode = flag == LEFT ? pNode -> father -> right : pNode -> father -> left;	// 叔节点
		// 如果叔节点存在且为红色
		if (qNode != NULL || qNode -> color == RED) {
			pNode -> color = BLACK;
			qNode -> color = BLACK;
			pNode -> father -> color = RED;
			node = pNode -> father;
			pNode = node -> father;
		} else {
			if (flag != (node == pNode -> left ? LEFT : RIGHT)) {
				turnRbNode(node, pNode);	// 此时插入节点与父节点在异侧
				node = pNode;
				pNode = node -> father;
			}
			// 执行上面的操作,插入节点和父节点变为同侧
			pNode -> color = BLACK;
			pNode -> father = RED;
			turnRbNode(pNode,pNode -> father);
		} 
	} 
} 

// 打印红黑树,显示节点的红黑特性
void printRBT(rbNode* root, int start) {
	printf("the %dth node : %d with %d\n", start, root -> value, root -> color);
	if (root -> left != NULL)
		printRBT(root -> left, start + 1);
	if (root -> right != NULL)
		printRBT(root -> right, start + 1);
}

	// 旋转红黑树的节点, sNode是被旋转的子节点
	// root为根节点,输出为旋转后的根节点
	rbNode* turnNode(rbNode* root, rbNode* sNode) {
		rbNode* pNode = sNode -> father;	// 被旋转的父节点
		if (sNode == pNode -> right) {		// sNode为右子节点
			if (sNode -> left != NULL) {
				sNode -> left -> father = pNode;	// sNode的左子节点过继给pNode
			pNode -> right = sNode -> left;		// pNode接收sNode的左子节点
			sNode -> left = pNode;		// pNode成为sNode的左子节点
			} else {
				if (sNode -> right != NULL)
					sNode -> right -> father = pNode;
					pNode -> left = sNode -> right;
					sNode -> right = pNode;
			}
			sNode -> father = pNode -> father;
			pNode -> father = sNode;

			if (sNode -> father == NULL) 
				return sNode;
			if (pNode == pNode -> father -> right) 
				sNode -> father -> right = sNode;
			else
				sNode -> father -> left = sNode;
			return root;	
		}

		// 红黑树的插入算法
		rbNode* insertRbNode(rbNode* root, int val) {
			rbNode* new = (rbNode*)malloc(sizeof(rbNode));
			new -> val = value;
			new -> left = NULL, new -> right = NULL;
			new -> color = RED;

			rbNode* tmpRoot = root;		// 保护root节点数据
			rbNode* temp;
			while (temp = root -> value < val ? root -> right : root -> left, temp != NULL)
				root = temp;
			new -> father = root;
			if (root -> value < val)
				root -> right = new;
			else
				root -> left = new;
			return adjustRBT(tmpRoot, new);
		}

// 红黑树插入算法
int main() {
	rbNode* Root = {NULL, NULL, NULL, 11, 1};
	rbNode* root = &Root;
	int init[7] = {2, 14, 1, 7, 15, 5, 8}
	for (int i = 0; i < 7; i ++) {
		root = insertRbNode(root, init[i]);
	}
	root = insertRbNode(root, 4);
	printRBT(root, 0);
	return 0;
}

// 红黑树查询, root为根节点,val为待查询值
// 返回值为节点的指针
rbNode* searchRBT(rbNode* root, int val) {
	if (root -> value == val) 
		return root;
	if (root -> value < val && root -> right != NULL)
		return searchRBT(root -> right, val);
	else if (root -> value > val && root -> left != NULL)
		return searchRBT(root -> left, val);
	else
		return false;
}

// 红黑树删除节点,输入为待删除的节点指针
void deleteRbNode(rbNode* dNode) {
	rbNode* pNode = dNode -> father;
	if (dNode -> left == NULL && dNode -> right == NULL) {
		if (dNode == pNode -> right)
			pNode -> right = NULL;
		else
			pNode -> left = NULL;
	} else {
		// 如果左子节点存在,则pNode为dNode的左子节点,否则为右子节点
		pNode = (dNode -> left == NULL) ? dNode -> right : dNode -> left;
		int val = dNode -> value;
		dNode -> value = pNode -> value;
		pNode -> value = val;
		deleteRbNode(pNode)
	}
}

// 主函数
int main() {
	rbNode Root = {NULL, NULL, NULL, 11, 1};
	rbNode* root = &Root;
	int init[10] = {2, 14, 1, 7, 15, 5, 8, 4, 13, 6}
	for (int i = 0; i < 10; i++) {
		root = insertRbNode(root, init[i]);
	}
	rbNode* delNode = searchRBT(root, 11);
	print(root, 0)
	deleteRbNode(delNode);
	printf("After delete node 11\n");
	printRBT(root, 0);
	return 0;
}

while (temp = root -> value < val ? root -> right : root -> left, temp != NULL) {
	root -> size += 1;
	root = temp;
}

if (dNode -> left == NULL && dNode -> right == NULL) {
	if (dNode == pNode -> right)
		pNode -> right = NULL;
	else
		pNode -> left = NULL;
	while (pNode.size -= 1, pNode -> father != NULL) {
		pNode = pNode -> father;
	}
}

rbNode* searchRBTN(rbNode* root, int n) {
	int low = 0;	// 左开右闭
	int high = root -> size;
	if (n > high)
		return NULL;
	
	while (1) {
		// 左子节点存在并且size < n - low
		if (root -> left != NULL && root -> left -> size < n-low) {
			root = root -> left;
			high = low + root -> size;
		} else {
			root = root -> right;
			low = high - root -> size;
		}
		if (root -> right != NULL && root -> right -> size == high - root -> size)
			return root;
		if (root -> left != NULL && root -> left -> size == low + root -> size - 1)
			return root;
	}
}