C++ 手撕红黑树（一）：插入操作

• C++ 手撕红黑树（一）：节点的插入
• • 1.红黑树简介
  • 2.红黑树的性质
  • 3.红黑树的插入
  • 4.红黑树的旋转
  • 5.红黑色插入测试
  • 6.整体代码：

红黑树的出现主要是用来解决AVL树旋转次数过多的问题:

AVL树在插入节点或者删除节点的过程中（每层递归完回溯时）都需要检查左子树或者右子树之间的高度差是否小于等于1，如果不平衡(大于1)的话需要旋转或者平衡操作来维持平衡，因此在数据量比较大的时候可能旋转了很多次（接近logn次），效率比较差。而红黑树在插入和删除的时候，最多分别做两次、三次旋转操作。因此旋转次数比较少。

然而，值得注意的是，红黑树是一颗BST树但并不是一颗平衡的树。但某个节点的左（右）子树深度最多只可能是右（左）子树深度的2倍，因此也不至于和BST树一样在某些极限情况下变成一条线性链表。

1. 每一个节点不是红色就一定是黑色。
2. 空节点被定义为黑色的。
3. 树的根节点一定强制为黑色。
4. 红色的节点不会连续出现（比如父子都是红色）。
5. 从根节点开始到任意叶子节点的路径中，黑色节点的数量一定是相等的。

在上面的5条性质中，最重要的其实是下面的三条性质。其中，第五条性质保证了某个节点的左（右）子树深度最多只可能是右（左）子树深度的2倍。在这种情况下，树的可视化如下：

对于插入操作，我们首先需要找到插入的位置。由于红黑树是一颗BST树，因此它的插入和BST、AVL树是完全一样的。都是通过分治的方式（对比插入值和左右子树的值）来找到一个空节点位置进行插入，这里我们讲不在赘述。假设找到插入的位置（空节点）后，我们按情况的复杂程度进行分析：

1.最简单的情况下就是树为空，那我们直接用插入的值new出一个新的节点作为根节点，并设置成黑色。

问题是：如果树不为空，那么我们插入的节点应该是什么颜色呢？
假设我们设置成黑色，那么从根节点到插入节点的路径中黑色节点的数量就多了一个。根据红黑树的规则5，这将导致所有路径中节点的颜色都需要变化，让其他的路径黑色节点都+1，这明显是很复杂的操作。因此，我们的结论出来了：所有新插入的节点，都将是红色才能尽量减少后续的操作。（如果设置成黑色，是一定要改变，但红色不一定），那么，问题又来了：

既然新插入的节点一定是红色，什么时候能不操作呢？
很简单，当它的父节点是黑色的时候，我们可以什么都不做。因为新插入红色节点没有增加任何黑色节点，所以跟“违背”规则5是毫不相干的。同时因为父节点是黑色，因此红色节点不会连续出现，也不会影响规则4。既然有父节点，新插入的节点也不会是根节点，因此不会违反规则3。所以，在这种情况下，直接插入就是了。下面我们开始考虑需要“后续操作”的情况。

需要后续操作的红黑树的局部情况（注意是局部情况！！！不是整棵树）一定是这个样子的：

也就是说，需要“后续操作”的情况，待插入节点的父节点一定是红色的。而既然父节点是红色的，那么爷爷节点一定是黑色的。

那么，根据叔叔的颜色不同和插入的节点在其父节点的左边或则右边（图里就是左边，右边没画），会出现四种情况：

2.对于情况1，插入的节点是1。此时，待插入节点1和其父节点2都是红色的，不符合规则4，因此，我们需要进行“操作”。我们能想到最简单的处理方式是什么？当然是让父节点变成黑色，然后让爷爷节点变成红色，再让叔叔节点8变成黑色。这样操作完，在局部的树中是满足所有条件的：

然而，假如爷爷节点5的父节点是红色的话，那就会造成祖父节点和爷爷节点都是红色的，有连续两个红色的出现了！这时我们的做法是：先这样做吧。然后需要迭代来检查爷爷节点是否满足红黑树的规则4，不满足我再调整！所以，对于情况1，处理方式是：

对于情况2：最简单的处理就是让node节点（待插入节点，下同）的父节点2变成黑色，爷爷节点变成红色：

但是这样会出现一个问题，那就是原来从局部树顶（节点5）到节点8，有两个黑色节点。现在从5到8却只有一个了。怎么办，难道需要整个树颜色调整一遍？其实不需要，我们只要以爷爷节点5为轴进行右旋就行了：

此时，从新的局部树的树顶（节点2）到节点8，又变成2个黑色了，且其他规则都满足了！而且不需要进一步的迭代！因此，对于情况2，我们的处理方式是变色+旋转：

3. 对于情况3，其实处理的方式和情况1是完全一样的：

3. 对于情况4，我们尝试和情况2一样处理：变色+旋转，看看会发生什么：

行不通！节点3和节点5出现了连续的红色！那怎么办？其实我们只需要一个旋转操作，就可以把它变成情况2：

还记得情况2不：

一模一样。所以后续我们只需要按情况2对情况4进行处理即可。注意情况2处理完不需要后面任何操作，很香的！这也是我们要把情况4变成2的原因之一：

至此，大功告成！对于插入节点在爷爷的右子树的情况，完全镜像即可！

总结：在上面的操作中，再精简一下，其实只有3种情况。因为1、3的处理方式是完全一样的：变色+迭代检查。而情况4只需要旋转一下就变成2。

再精简一下，那就是插入看叔叔的颜色：同色（都是红色，那就变色+迭代）。异色（叔叔黑色）那就先掰成直线（第一次旋转可能出现的地方）统一成情况2，再变色+旋转（第二次旋转可能出现的地方）。

对于红黑树的左旋，操作如下：

• 代码如下

// 左旋
	void leftRoate(Node* node) {
		Node* child = node->right_;
		child->parent_ = node->parent_;
		if (node->parent_ == nullptr) { 
			// node本身是根节点 子节点转上去就会变成根节点
			root_ = child;
		} else {
			if (node->parent_->left_ == node) {
				// node是父节点的左孩子
				node->parent_->left_ = child;
			} else {
				// node是父节点的右孩子
				node->parent_->right_ = child;
			}
		}

		node->right_ = child->left_;
		if (child->left_ != nullptr) {
			child->left_->parent_ = node;
		}

		child->left_ = node;
		node->parent_ = child;
	}

对于右旋：

• 代码：

// 右旋操作
	void rightRoate(Node* node) {
		Node* child = node->left_;
		child->parent_ = node->parent_;
		if (node->parent_ == nullptr) {
			// node是根节点
			root_ = child;
		} else {
			if (node->parent_->left_ == node) {
				node->parent_->left_ = child;
			} else {
				node->parent_->right_ = child;
			}
		}

		node->left_ = child->right_;
		if (child->right_ != nullptr) {
			child->right_->parent_ = node;
		}

		child->right_ = node;
		node->parent_ = child;
	}

对于插入+调整操作：

void insert(const int& val) {
		// 如果为空树的话 new一个结点出来即可
		if (root_ == nullptr) {
			root_ = new Node(val);
			return;
		}
		//std::cout << val << std::endl;

		Node* parent = nullptr;
		Node* cur = root_;
		while (cur != nullptr) {
			if (cur->val_ > val) {
				parent = cur;
				cur = cur->left_;
			} else if (cur->val_ < val) {
				parent = cur;
				cur = cur->right_;
			} else {
				// 树里面已经有该值了 直接返回即可
				return;
			}
		}

		Node* newNode = new Node(val, nullptr, nullptr, parent, RED);
		if (parent->val_ > val) {
			parent->left_ = newNode;
		} else {
			parent->right_ = newNode;
		}
		// 插入的节点一定是红色
		// 如果父节点的颜色是红色，那么在插入之后需要进行调整
		if (RED == color(parent)) {
			fixAfterInsert(newNode);
		}
	}

	void fixAfterInsert(Node* node) {
		// 判断是否需要迭代检查
		while (RED == color(parent(node))) {
			// 如果插入节点node的父亲是爷爷节点的左孩子
			if (left(parent(parent(node))) == node) {
				// 那么叔叔节点就是爷爷节点的右孩子
				Node* uncle = right(parent(parent(node)));
				if (RED == color(uncle)) { // 情况1和情况3：叔叔节点是红色的
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					setColor(uncle, BLACK);
					node = parent(parent(node)); // 检查节点从插入节点->爷爷节点（因为爷爷的父亲可能是红色）
				} else {
					// 先判断是不是情况三 如果是的话 把情况三调整为情况2 再后续处理
					if (right(parent(node)) == node) {
						leftRoate(parent(node)); // 对插入节点node的父左旋，掰到同一直线
					}

					// 处理情况2
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					rightRoate(parent(parent(node)));
				}
			} else { // 如果插入节点node的父亲是爷爷节点的右孩子,处理完全镜像，所有left改成right即可
				// 那么叔叔节点就是爷爷节点的右孩子
				Node* uncle = left(parent(parent(node)));
				if (RED == color(uncle)) { // 情况1和情况3：叔叔节点是红色的
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					setColor(uncle, BLACK);
					node = parent(parent(node)); // 检查节点从插入节点->爷爷节点（因为爷爷的父亲可能是红色）
				} else {
					// 先判断是不是情况三 如果是的话 把情况三调整为情况2 再后续处理
					if (left(parent(node)) == node) {
						rightRoate(parent(node)); // 对插入节点node的父左旋，掰到同一直线
					}

					// 处理情况2
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					leftRoate(parent(parent(node)));
				}
			}
		}

		setColor(root_, BLACK); // 强制设置根节点为黑色
	}

插入1、2、3、4、5、6：

• 插入1、2
  
• 插入3：
  
• 插入4：
  
• 插入5：
  
• 插入6：
  

#include 
#include 

enum Color {
	BLACK,
	RED
};

struct Node
{
	int val_;
	Node* left_;
	Node* right_;
	Node* parent_;
	Color color_;
	Node(int val = INT_MAX, Node* left = nullptr, Node* right = nullptr,
		Node* parent = nullptr, Color color = BLACK) :
		val_(val), left_(left), right_(right), parent_(parent), color_(color) {
	};
};

class RB_tree {	

public:
	RB_tree() : root_(nullptr) {}

	// 返回节点的颜色
	Color color(Node* node) {
		return nullptr == node ? BLACK : node->color_;
	}
	// 返回节点的左孩子
	Node* left(Node* node) {
		return node->left_;
	}
	// 返回节点的右孩子
	Node* right(Node* node) {
		return node->right_;
	}
	// 返回节点的父节点
	Node* parent(Node* node) {
		return node->parent_;
	}
	// 设置颜色
	void setColor(Node* node, Color color) {
		node->color_ = color;
	}
	// 左旋
	void leftRoate(Node* node) {
		Node* child = node->right_;
		child->parent_ = node->parent_;
		if (node->parent_ == nullptr) { 
			// node本身是根节点 子节点转上去就会变成根节点
			root_ = child;
		} else {
			if (node->parent_->left_ == node) {
				// node是父节点的左孩子
				node->parent_->left_ = child;
			} else {
				// node是父节点的右孩子
				node->parent_->right_ = child;
			}
		}

		node->right_ = child->left_;
		if (child->left_ != nullptr) {
			child->left_->parent_ = node;
		}

		child->left_ = node;
		node->parent_ = child;
	}
	// 右旋操作
	void rightRoate(Node* node) {
		Node* child = node->left_;
		child->parent_ = node->parent_;
		if (node->parent_ == nullptr) {
			// node是根节点
			root_ = child;
		} else {
			if (node->parent_->left_ == node) {
				node->parent_->left_ = child;
			} else {
				node->parent_->right_ = child;
			}
		}

		node->left_ = child->right_;
		if (child->right_ != nullptr) {
			child->right_->parent_ = node;
		}

		child->right_ = node;
		node->parent_ = child;
	}
	void insert(const int& val) {
		// 如果为空树的话 new一个结点出来即可
		if (root_ == nullptr) {
			root_ = new Node(val);
			return;
		}
		//std::cout << val << std::endl;

		Node* parent = nullptr;
		Node* cur = root_;
		while (cur != nullptr) {
			if (cur->val_ > val) {
				parent = cur;
				cur = cur->left_;
			} else if (cur->val_ < val) {
				parent = cur;
				cur = cur->right_;
			} else {
				// 树里面已经有该值了 直接返回即可
				return;
			}
		}

		Node* newNode = new Node(val, nullptr, nullptr, parent, RED);
		if (parent->val_ > val) {
			parent->left_ = newNode;
		} else {
			parent->right_ = newNode;
		}
		// 插入的节点一定是红色
		// 如果父节点的颜色是红色，那么在插入之后需要进行调整
		if (RED == color(parent)) {
			fixAfterInsert(newNode);
		}
	}

	void fixAfterInsert(Node* node) {
		// 判断是否需要迭代检查
		while (RED == color(parent(node))) {
			// 如果插入节点node的父亲是爷爷节点的左孩子
			if (left(parent(parent(node))) == node) {
				// 那么叔叔节点就是爷爷节点的右孩子
				Node* uncle = right(parent(parent(node)));
				if (RED == color(uncle)) { // 情况1和情况3：叔叔节点是红色的
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					setColor(uncle, BLACK);
					node = parent(parent(node)); // 检查节点从插入节点->爷爷节点（因为爷爷的父亲可能是红色）
				} else {
					// 先判断是不是情况三 如果是的话 把情况三调整为情况2 再后续处理
					if (right(parent(node)) == node) {
						leftRoate(parent(node)); // 对插入节点node的父左旋，掰到同一直线
					}

					// 处理情况2
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					rightRoate(parent(parent(node)));
				}
			} else { // 如果插入节点node的父亲是爷爷节点的右孩子,处理完全镜像，所有left改成right即可
				// 那么叔叔节点就是爷爷节点的右孩子
				Node* uncle = left(parent(parent(node)));
				if (RED == color(uncle)) { // 情况1和情况3：叔叔节点是红色的
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					setColor(uncle, BLACK);
					node = parent(parent(node)); // 检查节点从插入节点->爷爷节点（因为爷爷的父亲可能是红色）
				} else {
					// 先判断是不是情况三 如果是的话 把情况三调整为情况2 再后续处理
					if (left(parent(node)) == node) {
						rightRoate(parent(node)); // 对插入节点node的父左旋，掰到同一直线
					}

					// 处理情况2
					setColor(parent(node), BLACK);
					setColor(parent(parent(node)), RED);
					leftRoate(parent(parent(node)));
				}
			}
		}

		setColor(root_, BLACK); // 强制设置根节点为黑色
	}

	// 返回根节点
	Node* getRoot() {
		return root_;
	}

private:
	Node* root_;
};


void printTree(Node* root) {
	std::queue que;
	if (root) que.push(root);

	while (!que.empty()) {
		int size = que.size();

		for (int i = 0; i < size; ++i) {
			Node* cur = que.front(); que.pop();
			std::cout << cur->val_ << "(" << (cur->color_ == 0 ? "B" : "R") << ")" << " ";

			if (cur->left_) que.push(cur->left_);
			if (cur->right_) que.push(cur->right_);
		}
		std::cout << std::endl;
	}
}

int main() {

	RB_tree rbTree;
	for (int i = 1; i <= 6; ++i) {
		rbTree.insert(i);
	}

	printTree(rbTree.getRoot());
	return 0;
}

• 运行结果：
  

大功告成！！！！！！