红黑树------插入结点

大耗子 2020年07月04日 186次浏览

红黑树的优势

  1. 首先红黑树是不符合AVL树的平衡条件的,即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色,红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多,所以红黑树的插入效率更高。

  2. 红黑树能够以O(log2 (n)) 的时间复杂度进行搜索、插入、删除操作

  3. 简单来说红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

为什么会有红黑树的存在

在二叉树中,如果是顺序插入,会变成一个链表,查找效率直线下降。

红黑树的性质

  1. 每个结点是红的或者黑的。
  2. 根结点是黑的。
  3. 每个叶子结点是黑的。
  4. 如果一个结点是红的,则它的两个儿子都是黑的。
  5. 对每个结点,从该结点到其子孙结点的所有路径上的包含相同数目的黑结点。

红黑树的旋转

旋转
左旋:
leftRotate

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {

	rbtree_node *y = x->right;  
	
	// 1.变换x的右子树上的指针和要指它的指针
	x->right = y->left; //1
	if (y->left != T->nil) { //2
		y->left->parent = x;
	}
	
	// 2.变换y父结点的指针和要指它的指针
	y->parent = x->parent; //3
	if (x->parent == T->nil) { //4
		T->root = y; // 树根
	} else if (x == x->parent->left) { // 判断x所处位置
		x->parent->left = y; 
	} else {
		x->parent->right = y;
	}
	
	// 3.变换y的左子树上的指针和要指它的指针
	y->left = x; //5
	x->parent = y; //6
}

右旋:
rightRotate

void rbtree_right_rotate(rbtree *T, rbtree_node *y) {

	rbtree_node *x = y->left;

	y->left = x->right;
	if (x->right != T->nil) {
		x->right->parent = y;
	}

	x->parent = y->parent;
	if (y->parent == T->nil) {
		T->root = x;
	} else if (y == y->parent->right) {
		y->parent->right = x;
	} else {
		y->parent->left = x;
	}

	x->right = y;
	y->parent = x;
}

红黑树的插入

(如果父亲是在祖父的左子树,那么叔叔方向就是右子树,父亲方向就是左子树)

  1. 如果父亲是红色,叔叔是红色。
    情况1
    变换方法
    (1)把父节点设为黑色。
    (2)把叔叔也设为黑色。
    (3)把祖父设置为红色。
    (4)把祖父设为当前结点(用以检测上面的结点)。
    (5)判断是情况几,继续调整。
    变色原因:因为父亲和叔叔同时变黑,祖父变红,相当于黑色下沉,但每条路线的黑高不会变化。但是祖父变红可能和上层继续不匹配,所以要将当前结点指针指向祖父位置,然后继续调整。

  2. 如果父亲是红色,叔叔是黑色,且当前结点在父亲兄弟(叔叔)方向子树。
    情况2
    变换方法
    (1)将当前结点指针指向父亲。
    (2)然后绕当前结点旋转(旋转方向根据父结点所处的子树方向,例子中是左)。

  3. 如果父亲是红色,叔叔是黑色,且当前结点在父亲的父亲方向子树。(有点绕口哈)
    情况3
    变换方法
    (1)把父节点设为黑色。
    (2)把祖父结点设为红色。
    (3)然后绕祖父结点旋转(旋转方向根据叔叔结点所处的子树方向,例子中是右)。
    变色原因:之前的推论已经知道叔叔为黑色,父亲的旋转方向子树也为黑色(此树要给祖父),因为当前结点红色和祖父旋转下来的结点黑色会在同一层(祖父那边黑高会多了一层),所以祖父结点要变红(此情况不用担心双红,因为叔叔和转过去的结点都是黑色),因为父亲结点因为要替换祖父位置,所以要变黑(保持原先的平衡)。

  4. 如果父亲是黑色,直接完成插入,无需调整。

void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {

	while (z->parent->color == RED) { //z ---> RED
		if (z->parent == z->parent->parent->left) {
			// 获取叔叔结点
			rbtree_node *y = z->parent->parent->right;
			if (y->color == RED) {
				// 情况1
				// 父亲与叔叔都变黑,祖父变红(黑色分叉,但黑高不变)
				// 由之前的父亲为红,可以推断出祖父一定是黑
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;
				// 祖父下面都已经平衡,查看由于祖父的变动是否产生双红
				z = z->parent->parent; //z --> RED
			} else { // 叔叔颜色是黑色
				// 情况2
				// 判断当前结点与父亲的关系(是否和父亲同一方向)
				if (z == z->parent->right) {
					// 因为旋转后当前结点要指向之前的父亲(转后变孩子)
					z = z->parent;
					// 此时父亲在左边,所以要向左旋转
					rbtree_left_rotate(T, z);
				}
				// 情况3
				// 之前的推论已经知道叔叔为黑色
				// 父亲的旋转方向子树也为黑色(此树要给祖父)
				// 为当前结点红色和祖父旋转下来的结点黑色会在同一层(祖父那边黑高会多了一层)
				// 所以祖父结点要变红
				// 因为父亲结点因为要替换祖父位置,所以变黑(保持原先的平衡)
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				rbtree_right_rotate(T, z->parent->parent);
			}
		}else {
			rbtree_node *y = z->parent->parent->left;
			if (y->color == RED) {
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;

				z = z->parent->parent; //z --> RED
			} else {
				if (z == z->parent->left) {
					z = z->parent;
					rbtree_right_rotate(T, z);
				}

				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				rbtree_left_rotate(T, z->parent->parent);
			}
		}
		
	}

	T->root->color = BLACK;
}