红黑树insert操作

一、红黑树的insert理论

1. 当前树为空树时，插入的节点是根节点，即黑色
2. 当前树非空时，插入节点为叶子节点，若插入的叶子节点为黑色，那每次插入都会破坏性质5。为了避免每次插入都要进行相应的旋转维持红黑树性质，插入的所有叶子节点都是红色。由于不能出现连续的红色节点，所以需要检查父节点的颜色。若父节点为黑色，则插入完成，否则出现连续的红色节点需要做相应的调整：

---

这样就保持了局部和原来一样的红黑树的性质，所以全局也是保持了性质，调整完成！！！

---

在情况3中，使用交换颜色和右旋转的方法，也会产生连续两个红色节点的问题

其实这种情况很好解决，把B和C旋转到一条线上，就可以使用情况2的方法解决了

插入情况总结：

• 情况1中叔叔是红色，插入到叶子节点的左侧或右侧；需要把父亲和叔叔置为黑色，爷爷置为红色，当前node指向爷爷，然后接着向上调整祖先节点
• 情况2中叔叔是黑色，插入到叶子节点的左侧；交换父亲和爷爷的颜色，然后以父亲为轴右旋转
• 情况3中叔叔是黑色，插入到叶子节点的右侧；以父亲为轴进行左旋转，将父亲、爷爷、叶子节点掰到同一侧，然后用情况2的方式处理

二、insert代码实现

void insert(const T& val) {
	if (root_ == nullptr) {
		root_ = new Node(val);
		return;
	}
	Node* parent = nullptr;
	Node* cur = root_;
	while (cur != nullptr) {
		if (cur->data_ > val) {
			parent = cur;
			cur = cur->right_;
		}
		else if (cur->data_ < val) {
			parent = cur;
			cur = cur->right_;
		}
		else {
			return;
		}
	}
	// 设置当前节点的parent和color
	Node* node = new Node(val, parent, nullptr, nullptr, Color::RED);
	if (parent->data_ > val) {
		parent->left_ = node;
	}
	else {
		parent->right_ = node;
	}

	// 插入节点的父节点也是红色，则出现连续的红色，需要调整
	if (Color::RED == color(parent)) {
		fixAfterInsert(node);
	}
}

void fixAfterInsert(Node* node) {
	// 父节点的颜色是红色，当前节点也是红色，不断调整
	while (color(parent(node)) == Color::RED) {
		// 父节点是爷爷的左孩子，插入的节点node在左子树
		if (parent(node) == left(parent(parent(node)))) {
			// 父亲是爷爷的左孩子，叔叔是爷爷的右孩子
			Node* uncle = right(parent(parent(node)));
			// 情况1：叔叔是红色（无论在父亲左侧或右侧）
			if (Color::RED == color(uncle)) {
				// 因为叔叔和父亲原来都是RED，爷爷原来必然是BLACK，上两代互换颜色
				setColor(parent(node), Color::BLACK);
				setColor(uncle, Color::BLACK);
				setColor(parent(parent(node)), Color::RED);
				// 上两代互换颜色后，爷爷变成RED，由于爷爷以前是BLACK，也许爷爷的父亲是RED，现在爷爷变RED后，可能连续出现两个RED，需要继续向上调整
				node = parent(parent(node));
			}
			else {
				// 情况2/3：叔叔是BLACK
				// 先处理叔叔是BLACK，插到叶子节点右侧的情况3
				if (node == right(parent(node))) {
					// 让node指向父亲，以node为轴旋转后，node才能成为情况2中刚插入的节点，进而统一情况2、3
					node = parent(node);
					leftRotate(node);
				}
				// 统一成情况2，叔叔是BLACK，插到叶子节点左侧
				setColor(parent(node), Color::BLACK);
				setColor(parent(parent(node)), Color::RED);
				rightRotate(parent(parent(node)));
				// 情况2、3保证了局部没有出现连续的RED，且保证了修改的局部支路中黑色节点数量没变，即全局也没有改变
				// 情况1只是修改颜色，情况2、3最多旋转两次，至此红黑树调整完成
				break;
			}
		}
		else {
			// 父节点是爷爷的右孩子，插入的节点node在右子树
			// 父亲是爷爷的右孩子，叔叔是爷爷的左孩子
			Node* uncle = left(parent(parent(node)));
			// 情况1：叔叔是红色（无论在父亲左侧或右侧）
			if (Color::RED == color(uncle)) {
				// 因为叔叔和父亲原来都是RED，爷爷原来必然是BLACK，上两代互换颜色
				setColor(parent(node), Color::BLACK);
				setColor(uncle, Color::BLACK);
				setColor(parent(parent(node)), Color::RED);
				// 上两代互换颜色后，爷爷变成RED，由于爷爷以前是BLACK，也许爷爷的父亲是RED，现在爷爷变RED后，可能连续出现两个RED，需要继续向上调整
				node = parent(parent(node));
			}
			else {
				// 情况2/3：叔叔是BLACK
				// 先处理叔叔是BLACK，插到叶子节点左侧的情况3
				if (node == left(parent(node))) {
					// 让node指向父亲，以node为轴旋转后，node才能成为情况2中刚插入的节点，进而统一情况2、3
					node = parent(node);
					rightRotate(node);
				}
				// 统一成情况2，叔叔是BLACK，插到叶子节点右侧
				setColor(parent(node), Color::BLACK);
				setColor(parent(parent(node)), Color::RED);
				leftRotate(parent(parent(node)));
				// 情况2、3保证了局部没有出现连续的RED，且保证了修改的局部支路中黑色节点数量没变，即全局也没有改变
				// 情况1只是修改颜色，情况2、3最多旋转两次，至此红黑树调整完成
				break;
			}
		}
	}
	// 此处需要将root_置为黑色
	setColor(root_, Color::BLACK);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

红黑树插入1…10的过程如下：

插入红色节点3，交换红色父亲2和黑色爷爷1的颜色后，以爷爷1为轴左旋转

---

叔叔为红色，将父亲和叔叔的颜色置为黑色，爷爷置为红色，当前节点node指向爷爷，继续向上调整

---

---

---

---

---

---

---

红黑树插入1…39的结果如下：