红黑树概念和旋转实现

一、红黑树的概念

不是一颗平衡树，节点的左右子树高度大的不超过高度小的两倍。在满足红黑树性质的前提下，旋转的次数要远小于AVL树，虽然红黑树不想AVL树那样平衡，也不会像BST树一样，有序插入会形成一个链表

而AVL树是平衡树，任意节点左右子树高度差不超过1，从根节点到任意叶子节点的距离都是相当的，即 查询效率高。然后AVL树旋转的次数和高度相关，有可能从失衡节点往根节点回溯的过程中有很多失衡节点，这都需要进行旋转，时间复杂度为$O(lo{g}_{2}n)$。而红黑树remove后最多旋转3次

红黑树特点：

• 树的每一个节点不是黑色就是红色
• root是黑色
• null是黑色
• 从根节点到每一个叶子节点的所有路径上，不能出现连续的红色节点。即父亲是红色，孩子一定全是黑色；如果孩子有红色，父亲一定是黑色
• 从任一节点到其每个叶子节点的所有路径上，黑色节点的数量是相同的

如果remove的场景少，可以考虑使用AVL树，如果多，就使用红黑树。C++的map、multimap、set、multiset的底层数据结构就是红黑树，这是因为我们使用容器的时候，增删改查都需要用到，而且频率相当

思考题：在红黑树中，节点的左右子树的高度差最多不能超过多少？

左右子树高度差最多不超过两倍

二、红黑树的定义代码

在红黑树中，访问节点的时候，要访问到它的父亲，爷爷和叔叔，需要方便的访问到父节点

在递归的过程中就不方便了，而且对于红黑树来说，插入操作最多旋转2次，局部解决完之后，局部没有改变红黑树的性质，全局自然就维护了红黑树的性质，局部解决好了，就不用向上回溯了，所以我们不需要使用递归，递归的话要从插入的地方回溯到根节点，效率低

template<typename T>
class RBTree {
public:
	RBTree():root_(nullptr){}


private:
	enum Color {
		RED,
		BLACK
	};

	struct Node {
		Node(T data=T(), Color color=BLACK, Node* parent=nullptr, Node* left=nullptr, Node* right=nullptr)
			: data_(data)
			, color_(color)
			, parent_(parent)
			, left_(left)
			, right_(right)
		{}

		T data_;
		Color color_;
		Node* left_;
		Node* right_;
		Node* parent_;  // 用于向上访问
	};
	
	Node* root_;
};
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

三、红黑树的左旋转和右旋转代码

AVL树的左旋转代码

AVL树的旋转代码只改了孩子域，父亲域是回溯时利用返回值改的，我们写红黑树代码是非递归形式的，所以需要手动改6个地址域

红黑树的旋转和AVL树的旋转一样的，只是多了一个parent，代码基于AVL树改即可

void leftRotate(Node* node) {
	Node* child = node->right_;
	// 1
	child->parent_ = node->parent_;
	if (node->parent_ == nullptr) {
		// node的父节点为空，说明node为root，此时child转上来，child成为root
		root_ = child;
	}
	else {
		// node不是root
		if (node->parent_->left_ == node) {
			// node是左孩子  2
			node->parent_->left_ = child;
		}
		else {
			// node是右孩子
			node->parent_->right_ = child;
		}
	}

	// 3
	node->right_ = child->left_;
	if (child->left_ != nullptr) {
		// 4
		child->left_->parent_ = node;
	}
	// 5
	child->left_ = node;
	// 6
	node->parent_ = child;
}
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

AVL树的右旋转代码

// 以node为轴进行右旋
void rightRotate(Node* node) {
	Node* child = node->left_;
	child->parent_ = node->parent_;        // 1
	if (node->parent_ == nullptr) {
		// node就是root
		root_ = child;
	}
	else {
		// node不是root
		if (node->parent_->left_ == node) {
			// node是左孩子
			node->parent_->left_ = child;   // 2
		}
		else {
			// node是右孩子
			node->parent_->right_ = child;
		}
	}

	node->left_ = child->right_;           // 3
	if (child->right_ != nullptr) {
		child->right_->parent_ = node;     // 4
	}
	child->right_ = node;                  // 5
	node->parent_ = child;                 // 6
}
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

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

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