C++数据结构复习(三)一一红黑树

因为红黑树还是自己画出来比较好理解，所以基本都是图辣

（其实就是懒得打字😂）

红黑树

想要更好地理解红黑树，可以先理解二叉查找树和 2-3 树。为何呢?首先，二叉查找树中的结点 是 2-结点(一个键两条链)，引入 3-结点(两个键三条链)，即成 2-3 树;然后将 2-3 树中 3- 结点分解，即成红黑树，故结合二叉查找树易查找和 2-3 树易插入的特点，便成了红黑二叉查找 树，简称红黑树。

五大性质

• 1)每个结点要么是红的，要么是黑的。

• 2)根结点是黑的。

• 3)每个叶结点(叶结点即指树尾端 NIL 指针或 NULL 结点)是黑的。

• 4)如果一个结点是红的，那么它的俩个儿子都是黑的。

• 5)对于任一结点而言，其到叶结点树尾端 NIL 指针的每一条路径都包含相同数目的黑结点

二叉查找树

二叉查找树的性质就不多说了，很基本的树结构

二叉树的插入

根据BST的性质就可以知道，其实就是比较，然后找到插入的位置。

树的旋转

红黑树的插入

插入修复

分为三种情况，总的来说还是比较好理解的：

红黑树的删除

删除修复

对于红黑树的删除，还是有点复杂的，但是只要理解了红黑树的五大性质，还是很好掌握的：

其实主要就是考虑红生两黑子，每个结点到叶节点各个路径黑色数量一致两个性质的保证。

红黑树的C++实现

RBTree.h:

#ifndef RB_TREE_H
#define RB_TREE_H
#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
using namespace std;

template<class KEY, class U>
class RB_Tree {
private:
	RB_Tree(const RB_Tree& input) {}
	const RB_Tree& operator=(const RB_Tree& input) {}
private:
	enum COLOR {
		RED,
		BLACK
	};
	class RB_Node {
	public:
		RB_Node() {
			right = NULL;
			left = NULL;
			parent = NULL;
		}
		COLOR RB_COLOR;
		RB_Node* right;
		RB_Node* left;
		RB_Node* parent;
		KEY key;
		U data;
	};
public:
	RB_Tree() {
		this->m_nullNode = new RB_Node();
		this->m_root = m_nullNode;
		this->m_nullNode->right = this->m_root;
		this->m_nullNode->left = this->m_root;
		this->m_nullNode->parent = this->m_root;
		this->m_nullNode->RB_COLOR = BLACK;
	}

	bool Empty() {
		if (this->m_root == this->m_nullNode) {
			return true;
		} else {
			return false;
		}
	}

	//查找key
	RB_Node* find(KEY key) {
		RB_Node* index = m_root;
		while (index != m_nullNode) {
			if (key < index->key) {
				index = index->left; // 比当前的小，往左
			} else if (key > index->key) {
				index = index->right; // 比当前的大，往右
			} else {
				break;
			}
		}
		return index;
	}

	bool Insert(KEY key, U data) {
		RB_Node* insert_point = m_nullNode;
		RB_Node* index = m_root;
		while (index != m_nullNode) {
			insert_point = index;
			if (key < index->key) {
				index = index->left;
			} else if (key > index->key) {
				index = index->right;
			} else {
				break;
			}
		}
		RB_Node* insert_node = new RB_Node();
		insert_node->key = key;
		insert_node->data = data;
		insert_node->RB_COLOR = RED;
		insert_node->right = m_nullNode;
		insert_node->left = m_nullNode;
		//如果插入一棵空树
		if (insert_point == m_nullNode) {
			m_root = insert_node;
			m_root->parent = m_nullNode;
			m_nullNode->left = m_root;
			m_nullNode->right = m_root;
			m_nullNode->parent = m_root;
		} else {
			if (key < insert_point->key) {
				insert_point->left = insert_node;
			} else {
				insert_point->right = insert_node;
			}
			insert_node->parent = insert_point;
		}
		InsertFixUp(insert_node); // 恢复红黑树性质
	}

	void InsertFixUp(RB_Node* node) {
		while (node->parent->RB_COLOR == RED) {
			// Z的父亲为祖父的左孩子
			if (node->parent == node->parent->parent->left) {
				RB_Node* uncle = node->parent->parent->right;
				//case①: Z的叔叔Y是红色的
				if (uncle->RB_COLOR == RED) {
					node->parent->RB_COLOR = BLACK;
					uncle->RB_COLOR = BLACK; //1.把父->黑、叔->黑
					node->parent->parent->RB_COLOR = RED; //2.祖->红
					node = node->parent->parent; //3.祖->当前结点
				} 
				//case②: Z的叔叔是黑色的
				else if (uncle->RB_COLOR == BLACK) {
					//case②.1: Z是右孩子
					if (node == node->parent->right) {
						node = node->parent; // 1.父->当前结点
						RotateLeft(node); // 2.左旋
					}
					//case②.2: Z是左孩子
					node->parent->RB_COLOR = BLACK; // 1.父->黑
					node->parent->parent->RB_COLOR = RED; // 2.祖父->红
					RotateRight(node->parent->parent); // 3.祖父为Pivot右旋
				}
			} 
			// Z的父亲为祖父的右孩子，对称
			else {
				RB_Node* uncle = node->parent->parent->left;
				if (uncle->RB_COLOR == RED) {
					node->parent->RB_COLOR = BLACK;
					uncle->RB_COLOR = BLACK; 
					node->parent->parent->RB_COLOR = RED; 
					node = node->parent->parent; 
				} 
				else if (uncle->RB_COLOR == BLACK) {
					if (node == node->parent->right) {
						node = node->parent; 
						RotateRight(node); // 左旋改为右旋
					}
					node->parent->RB_COLOR = BLACK; 
					node->parent->parent->RB_COLOR = RED; 
					RotateLeft(node->parent->parent); // 右旋改为左旋
				}
			}
		}
		m_root->RB_COLOR = BLACK; // 最后把根结点涂黑即可
	}

	//左旋代码实现
	bool RotateLeft(RB_Node* node) {
		if (node == m_nullNode || node->right == m_nullNode) {
			return false;
		}
		RB_Node* lower_right = node->right;
		lower_right->parent = node->parent;
		node->right = lower_right->left;
		if (lower_right->left != m_nullNode) {
			lower_right->left->parent = node;
		}
		// 旋转及结点为根结点
		if (node->parent == m_nullNode) {
			m_root = lower_right;
			m_nullNode->left = m_root;
			m_nullNode->right = m_root;
		} else {
			if (node == node->parent->left) {
				node->parent->left = lower_right;
			} else {
				node->parent->right = lower_right;
			}
		}
		node->parent = lower_right;
		lower_right->left = node;
	}

	// 右旋代码实现
	bool RotateRight(RB_Node* node) {
		if (node == m_nullNode || node->left == m_nullNode) {
			return false;
		}
		RB_Node* lower_left = node->left;
		node->left = lower_left->right;
		lower_left->parent = node->parent;
		if (lower_left->right != m_nullNode) {
			lower_left->right->parent = node;
		}
		if (node->parent == m_nullNode) {
			m_root = lower_left;
			m_nullNode->left = m_root;
			m_nullNode->right = m_root;
		} else {
			if (node == node->parent->right) {
				node->parent->right = lower_left;
			} else {
				node->parent->left = lower_left;
			}
		}
		node->parent = lower_left;
		lower_left->right = node;
	}

	bool Delete(KEY key) {
		RB_Node* delete_point = find(key);
		if (delete_point == m_nullNode) {
			return false;
		}
		// 删除结点 有两个儿子 
		if (delete_point->left != m_nullNode && delete_point->right != m_nullNode) {
			RB_Node* successor = InOrderSuccessor(delete_point);
			delete_point->data = successor->data;
			delete_point->key = successor->key;
			delete_point = successor;
		}
		RB_Node* delete_point_child;
		if (delete_point->right != m_nullNode) {
			delete_point_child = delete_point->right;
		} else if (delete_point->left != m_nullNode) {
			delete_point_child = delete_point->left;
		} else {
			delete_point_child = m_nullNode;
		}
		delete_point_child->parent = delete_point->parent;
		// 删除的是根节点
		if (delete_point->parent == m_nullNode) {
			m_root = delete_point_child;
			m_nullNode->parent = m_root;
			m_nullNode->left = m_root;
			m_nullNode->right = m_root;
		} else if (delete_point == delete_point->parent->right) {
			delete_point->parent->right = delete_point_child;
		} else {
			delete_point->parent->left = delete_point_child;
		}
		// 如果删除的是黑色结点 + 不是倒数第二个结点且父结点不为空
		if (delete_point->RB_COLOR == BLACK && !(delete_point_child == m_nullNode &&
			delete_point_child->parent == m_nullNode)) {
			DeleteFixUp(delete_point_child);
		}
		delete delete_point;
		return true;
	}

	// 删除修复
	void DeleteFixUp(RB_Node* node) {
		while (node != m_root && node->RB_COLOR == BLACK) {
			// 同样先考虑是父结点的左结点的情况
			if (node == node->parent->left) {
				RB_Node* brother = node->parent->right;
				// case①: X 的兄弟结点 W 是红色的
				if (brother->RB_COLOR == RED) {
					brother->RB_COLOR = BLACK; //1.兄->红
					node->parent->RB_COLOR = RED; //2.父->红
					RotateLeft(node->parent); //3.父为Pivot左旋
				}
				// case②: X 的兄弟结点 W 是黑色的
				else {
					// case②.1: 且 W 两个孩子都是黑的
					if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK) {
						brother->RB_COLOR = RED; //1. 兄->红
						node = node->parent; //2.父->当前结点
					}
					// case②.2: W 的孩子 左红右黑
					else if (brother->right->RB_COLOR == BLACK) {
						brother->RB_COLOR = RED; //1.兄->红
						brother->left->RB_COLOR = BLACK; //2.兄左子->黑
						RotateRight(brother); //3.父为Pivot右旋
					}
					// case②.3: W 的孩子 左黑右红
					brother->RB_COLOR = node->parent->RB_COLOR; //1. 兄->父色
					node->parent->RB_COLOR = BLACK; //2. 父->黑
					brother->right->RB_COLOR = BLACK; //3.兄右子->黑
					RotateLeft(node->parent); //4.父为Pivot左旋
					node = m_root;
				}
			}
			else {
				// 同样的考虑是父节点的右子节点的情况，也是只改变旋转
				RB_Node* brother = node->parent->left;
				// case①: X 的兄弟结点 W 是红色的
				if (brother->RB_COLOR == RED) {
					brother->RB_COLOR = BLACK; //1.兄->红
					node->parent->RB_COLOR = RED; //2.父->红
					RotateRight(node->parent); //3.父为Pivot左旋
				}
				// case②: X 的兄弟结点 W 是黑色的
				else {
					// case②.1: 且 W 两个孩子都是黑的
					if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK) {
						brother->RB_COLOR = RED; //1. 兄->红
						node = node->parent; //2.父->当前结点
					}
					// case②.2: W 的孩子 左红右黑
					else if (brother->right->RB_COLOR == BLACK) {
						brother->RB_COLOR = RED; //1.兄->红
						brother->left->RB_COLOR = BLACK; //2.兄左子->黑
						RotateLeft(brother); //3.父为Pivot右旋
					}
					// case②.3: W 的孩子 左黑右红
					brother->RB_COLOR = node->parent->RB_COLOR; //1. 兄->父色
					node->parent->RB_COLOR = BLACK; //2. 父->黑
					brother->right->RB_COLOR = BLACK; //3.兄右子->黑
					RotateRight(node->parent); //4.父为Pivot右旋
					node = m_root;
				}	
			}
		}
		m_nullNode->parent = m_root; // 最后将node置为根结点
		node->RB_COLOR = BLACK; // 并改为黑色
	}

	inline RB_Node* InOrderPredecessor(RB_Node* node) {
		// 空结点 没有 predecessor 前驱
		if (node == m_nullNode) {
			return m_nullNode;
		}
		RB_Node* result = node->left;
		//找到左子树的最大（右）结点
		while (result != m_nullNode) {
			if (result->right != m_nullNode) {
				result = result->right;
			} else {
				break;
			}
		}
		// 循环结束时意味着 result==null 或者result 的右子节点 == null
		if (result == m_nullNode) {
			RB_Node* index = node->parent;
			result = node;
			while (index != m_nullNode && result == index->left) {
				result = index;
				index = index->parent;
			}
			result = index; // 第一个parent 的右结点 或者 null
		}
		return result;
	}

	inline RB_Node* InOrderSuccessor(RB_Node* node) {
		if (node == m_nullNode) {
			return m_nullNode;
		}
		RB_Node* result = node->right;
		// 找到node 的右子树的最小（左）结点
		while (result != m_nullNode) {
			if (result->left != m_nullNode) {
				result = result->left;
			} else {
				break;
			}
		}
		// 循环结束时意味着 result==null 或者result 的左子节点 == null
		if (result == m_nullNode) {
			RB_Node* index = node->parent;
			result = node;
			while (index != m_nullNode && result == index->right) {
				result = index;
				index = index->parent;
			}
			result = index; // 第一个parent 的左结点 或者 null
		}
		return result;
	}

	// debug
	void InOrderTraverse() {
		InOrderTraverse(m_root);
	}
	void CreateGraph(string filename) {

	}
	void InOrderCreate(ofstream& file, RB_Node* node) {

	}
	void InOrderTraverse(RB_Node* node) {
		if (node == m_nullNode) {
			return;
		} else {
			InOrderTraverse(node->left);
			cout << node->key << endl;
			InOrderTraverse(node->right);
		}
	}

	~RB_Tree() {
		clear(m_root);
		delete m_nullNode;
	}

private:
	// utility function for destructor to destruct object
	void clear(RB_Node* node) {
		if (node == m_nullNode) {
			return;
		} else {
			clear(node->left);
			clear(node->right);
			delete node;
		}
	}
private:
	RB_Node *m_nullNode;
	RB_Node *m_root;
};
#endif

---

测试文件RBTree.cpp:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <sstream>
#include "RBTree.h"
using namespace std;

int main() {
	RB_Tree<int, int> tree;
	vector<int> v;

	for (int i = 0; i < 20; i++) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	stringstream sstr;
	for (int i = 0; i < v.size(); ++i) {
		tree.Insert(v[i], i);
		cout << "Insert:" << v[i] << endl; 
	}
	for (int i = 0; i < v.size(); ++i) {
		cout << "Delete:" << v[i] << endl;
		tree.Delete(v[i]);
		tree.InOrderTraverse();
	}
	cout << endl;
	tree.InOrderTraverse();
	return 0;
}

---

测试结果

……