[C++知识库]红黑树c++实现

红黑树c++实现

红黑树算法详解

红黑树算法详解

c++实现

c++实现参考

（一）使用示例：

#include <iostream>

using namespace rb_tree;
using namespace std;

int main() {
	red_black_tree<int, int> tree{};
	tree.insert(1, 100);
	tree.insert(45324, -1);
	tree.insert(-4324, 47845);
	tree.insert(424324, 214);
	tree.insert(7, -253456);
	tree.insert(6, 214);
	tree.remove(6);
	tree.remove(7);
	tree.remove(1);
	int res = 0;
	cout << static_cast<int>(tree.search(45324, res)) << endl;
	cout << res << endl;
}

（二）代码（关键代码已注释）：

namespace rb_tree {
	enum class node_color { black, red };

	enum class func_return { success, duplicate, not_found };

	template <typename K, typename V>
	class rb_tree_node {
	public:
		explicit rb_tree_node(const node_color color = node_color::black): color(color) {
		}

		rb_tree_node(const K& key, const V& value, const node_color color = node_color::black): key(key), value(value),
			color(color) {
		}

		rb_tree_node<K, V>* parent = nullptr;
		rb_tree_node<K, V>* l_child = nullptr;
		rb_tree_node<K, V>* r_child = nullptr;
		K key;
		V value;
		node_color color;
	};

	template <typename K, typename V>
	class red_black_tree {
	public:
		red_black_tree();
		~red_black_tree();
		red_black_tree(const red_black_tree&) = delete;
		red_black_tree operator=(const red_black_tree&) = delete;
		red_black_tree(const red_black_tree&&) = delete;
		red_black_tree operator=(const red_black_tree&&) = delete;

		func_return insert(const K& key, const V& value);
		func_return remove(const K& key);
		func_return search(const K& key, V& value);
	private:
		void destroy(rb_tree_node<K, V>* node);
		static rb_tree_node<K, V>* get_grandparent(rb_tree_node<K, V>* node);
		static rb_tree_node<K, V>* get_uncle(rb_tree_node<K, V>* node);
		rb_tree_node<K, V>* get_sibling(rb_tree_node<K, V>* node);

		void insert_fix_up(rb_tree_node<K, V>* node);
		void remove_fix_up(rb_tree_node<K, V>* node);
		void rotate_left(rb_tree_node<K, V>* node);
		void rotate_right(rb_tree_node<K, V>* node);

		rb_tree_node<K, V>* root_;
		rb_tree_node<K, V>* sentinel_;
	};

	template <typename K, typename V>
	red_black_tree<K, V>::red_black_tree() {
		sentinel_ = new rb_tree_node<K, V>();
		root_ = sentinel_;
	}

	template <typename K, typename V>
	red_black_tree<K, V>::~red_black_tree() {
		destroy(root_);
		delete sentinel_;
		sentinel_ = nullptr;
	}

	template <typename K, typename V>
	void red_black_tree<K, V>::destroy(rb_tree_node<K, V>* node) {
		if (node != nullptr && node != sentinel_) {
			destroy(node->l_child);
			destroy(node->r_child);
			delete node;
		}
	}

	template <typename K, typename V>
	rb_tree_node<K, V>* red_black_tree<K, V>::get_grandparent(rb_tree_node<K, V>* node) {
		if (node != nullptr && node->parent != nullptr)
			return node->parent->parent;
		return nullptr;
	}

	template <typename K, typename V>
	rb_tree_node<K, V>* red_black_tree<K, V>::get_uncle(rb_tree_node<K, V>* node) {
		auto g = get_grandparent(node);
		if (g != nullptr)
			return node->parent == g->l_child ? g->r_child : g->l_child;
		return nullptr;
	}

	template <typename K, typename V>
	rb_tree_node<K, V>* red_black_tree<K, V>::get_sibling(rb_tree_node<K, V>* node) {
		if (node != nullptr && node->parent != nullptr) {
			auto p = node->parent;
			return node == p->l_child ? p->r_child : p->l_child;
		}
		return nullptr;
	}

	template <typename K, typename V>
	void red_black_tree<K, V>::rotate_left(rb_tree_node<K, V>* node) {
		if (node == nullptr || node->r_child == nullptr)
			return;
		auto t = node->r_child;
		node->r_child = t->l_child;
		if (t->l_child)
			t->l_child->parent = node;
		if (node == root_) {
			root_ = t;
			t->parent = nullptr;
		}
		else {
			auto p = node->parent;
			t->parent = p;
			if (node == p->l_child)
				p->l_child = t;
			else
				p->r_child = t;
		}
		t->l_child = node;
		node->parent = t;
	}

	template <typename K, typename V>
	void red_black_tree<K, V>::rotate_right(rb_tree_node<K, V>* node) {
		if (node == nullptr || node->l_child == nullptr)
			return;
		auto t = node->l_child;
		node->l_child = t->r_child;
		if (t->r_child)
			t->r_child->parent = node;
		if (node == root_) {
			root_ = t;
			t->parent = nullptr;
		}
		else {
			auto p = node->parent;
			t->parent = p;
			if (node == p->l_child)
				p->l_child = t;
			else
				p->r_child = t;
		}
		t->r_child = node;
		node->parent = t;
	}

	template <typename K, typename V>
	func_return red_black_tree<K, V>::insert(const K& key, const V& value) {
		auto t = root_;
		decltype(t) p = nullptr;
		// 找到要插入的位置，如果可以插入，那么插入位置一定在哨兵节点
		while (t != sentinel_) {
			p = t;
			if (t->key == key)
				return func_return::duplicate;
			t = t->key < key ? t->r_child : t->l_child;
		}
		// 新插入的节点颜色一定为红色
		auto new_node = new rb_tree_node<K, V>(key, value, node_color::red);
		new_node->l_child = sentinel_;
		new_node->r_child = sentinel_;
		[[unlikely]]if (root_ == sentinel_) {
			root_ = new_node;
		}
		else {
			new_node->parent = p;
			if (p->key > key)
				p->l_child = new_node;
			else
				p->r_child = new_node;
		}
		// 插入后进行调整
		insert_fix_up(new_node);
		// 可能会改变根节点颜色，这里要改回去
		root_->color = node_color::black;
		// 可能让哨兵节点的父节点不为空，这里要改回去
		sentinel_->parent = nullptr;
		return func_return::success;
	}

	template <typename K, typename V>
	void red_black_tree<K, V>::insert_fix_up(rb_tree_node<K, V>* node) {
		decltype(node) u = nullptr;
		decltype(node) g = nullptr;
		// 如果到达根节点||父节点的颜色为黑色（因为新节点为红，所以已经平衡）就不需要处理
		while (node != root_ && node->parent->color == node_color::red) {
			u = get_uncle(node);
			g = get_grandparent(node);
			// 如果父红叔红，则将父节点和叔叔节点都变为黑色，祖父节点变为红色，然后对祖父节点递归处理
			if (u->color == node_color::red) {
				node->parent->color = node_color::black;
				u->color = node_color::black;
				g->color = node_color::red;
				node = g;
			}
			else {
				// 如果父红叔黑，则需要判断新节点-父节点-祖父节点是否三点一线
				auto p = node->parent;
				if (g->l_child == p) {
					// 如果新节点-父节点-祖父节点不为三点一线，则需要对父节点旋转让它变为三点一线的情况
					if (node == p->r_child) {
						node = p;
						rotate_left(node);
						p = node->parent;
					}
					// 祖父变红，父变黑，对祖父节点旋转
					g->color = node_color::red;
					p->color = node_color::black;
					rotate_right(g);
				}
				else {
					// 如果新节点-父节点-祖父节点不为三点一线，则需要对父节点旋转让它变为三点一线的情况
					if (node == p->l_child) {
						node = p;
						rotate_right(node);
						p = node->parent;
					}
					// 祖父变红，父变黑，对祖父节点旋转
					g->color = node_color::red;
					p->color = node_color::black;
					rotate_left(g);
				}
				break;
			}
		}
	}

	template <typename K, typename V>
	func_return red_black_tree<K, V>::remove(const K& key) {
		auto d = root_;
		// 找到要删除的位置
		while (d != sentinel_) {
			if (d->key == key)
				break;
			d = d->key < key ? d->r_child : d->l_child;
		}
		if (d == sentinel_)
			return func_return::not_found;
		decltype(d) sub = nullptr;
		if (d->l_child == sentinel_ && d->r_child == sentinel_)
			// 如果没有左右孩子，那么需要真正删除的sub节点就是找到的d节点
			sub = d;
		else if (d->l_child == sentinel_)
			// 如果只有一个孩子，那么需要真正删除的sub节点就是那个孩子节点，孩子节点的内容需要移动到d节点
			sub = d->r_child;
		else if (d->r_child == sentinel_)
			sub = d->l_child;
		else {
			// 如果有两个孩子，那么需要真正删除的sub节点就是d节点的前驱节点（后继节点也行），孩子节点的内容需要移动到d节点
			sub = d->l_child;
			while (sub->r_child != sentinel_)
				sub = sub->r_child;
		}
		if (d != sub) {
			d->key = sub->key;
			d->value = sub->value;
		}
		decltype(d) sub_child = sub->l_child;
		if (auto p = sub->parent) {
			if (sub == p->l_child)
				p->l_child = sub_child;
			else
				p->r_child = sub_child;
		}
		else
			root_ = sub_child;
		// 这里的sub_child可能是哨兵节点，会让哨兵节点的父节点不为空，不过没关系，最后会改回去
		sub_child->parent = sub->parent;
		if (sub->color == node_color::black)
			remove_fix_up(sub_child);
		delete sub;
		sentinel_->parent = nullptr;
		return func_return::success;
	}

	template <typename K, typename V>
	void red_black_tree<K, V>::remove_fix_up(rb_tree_node<K, V>* node) {
		decltype(node) s = nullptr;
		// 如果到达根节点||当前节点为红（因为删去路径上的红色节点不会影响二叉树的性质）就不需要处理
		while (node != root_ && node->color == node_color::black) {
			s = get_sibling(node);
			// 区分兄弟节点在左边还是在右边
			if (s == s->parent->l_child) {
				// 如果兄红，则交换兄弟节点和父节点颜色，父节点旋转（新的兄弟节点为现在的兄弟节点的子节点，一定为黑，相当于转换为兄黑的情况）
				if (s->color == node_color::red) {
					s->color = node_color::black;
					s->parent->color = node_color::red;
					rotate_right(s->parent);
					s = node->parent->l_child;
				}
				// 兄弟节点为黑，且兄弟节点的两个子节点都为黑（哨兵节点也为黑）
				if (s->l_child->color == node_color::black && s->r_child->color == node_color::black) {
					// 兄变红
					s->color = node_color::red;
					// 父节点为红，就把父节点变黑，并退出循环
					if (node->parent->color == node_color::red) {
						node->parent->color = node_color::black;
						break;
					}
					// 如果父节点也为黑就需要递归判断
					node = node->parent;
				}
				else {
					// 如果兄弟节点在左且兄弟节点的左子节点为黑，就要交换兄弟节点和兄弟节点的右子节点颜色（相当于转换为左子节点为红的情况）
					if (s->l_child->color == node_color::black) {
						s->color = node_color::red;
						s->r_child->color = node_color::black;
						rotate_left(s);
						s = node->parent->l_child;
					}
					// 兄弟节点的左子节点为红色
					s->color = s->parent->color;
					s->parent->color = node_color::black;
					s->l_child->color = node_color::black;
					rotate_right(s->parent);
					break;
				}
			}
			else {
				// 如果兄红，则交换兄弟节点和父节点颜色，父节点旋转（新的兄弟节点为现在的兄弟节点的子节点，一定为黑，相当于转换为兄黑的情况）
				if (s->color == node_color::red) {
					s->color = node_color::black;
					s->parent->color = node_color::red;
					rotate_left(s->parent);
					s = node->parent->r_child;
				}
				// 兄弟节点为黑，且兄弟节点的两个子节点都为黑（哨兵节点也为黑）
				if (s->l_child->color == node_color::black && s->r_child->color == node_color::black) {
					// 兄变红
					s->color = node_color::red;
					// 父节点为红，就把父节点变黑，并退出循环
					if (node->parent->color == node_color::red) {
						node->parent->color = node_color::black;
						break;
					}
					// 如果父节点也为黑就需要递归判断
					node = node->parent;
				}
				else {
					// 如果兄弟节点在右且兄弟节点的右子节点为黑，就要交换兄弟节点和兄弟节点的左子节点颜色（相当于转换为右子节点为红的情况）
					if (s->r_child->color == node_color::black) {
						s->color = node_color::red;
						s->l_child->color = node_color::black;
						rotate_right(s);
						s = node->parent->r_child;
					}
					// 兄弟节点的右子节点为红色
					s->color = s->parent->color;
					s->parent->color = node_color::black;
					s->r_child->color = node_color::black;
					rotate_left(s->parent);
					break;
				}
			}
		}
	}

	template <typename K, typename V>
	func_return red_black_tree<K, V>::search(const K& key, V& value) {
		auto t = root_;
		while (t != sentinel_) {
			if (t->key == key) {
				value = t->value;
				return func_return::success;
			}
			t = t->key > key ? t->l_child : t->r_child;
		}
		return func_return::not_found;
	}
}