1. Toy模板网首页
  2. > Toy博客

C++手撕红黑树

7月前 作者：栖林_ 分类：Toy博客 阅读(42) 违法举报

这篇具有很好参考价值的文章主要介绍了C++手撕红黑树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

红黑树

概念

和AVL树一样，红黑树也是一种二叉搜索树，是解决二叉搜索树不平衡的另一种方案，他在每个节点上增加一个存储位，用于表示节点的颜色，是Red或者Black

红黑树的核心思想是通过一些着色的条件限制，达到一种最长路径不超过最短路径的两倍的状态

所以说红黑树并不是严格平衡的树，而是一种近似平衡

例如

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

性质（条件限制）

红黑树一共有五条性质，由此来保证最长路径不超过最短路径的两倍

  1. 每个节点都有颜色，不是黑色就是红色
  2. 根节点是黑色的
  3. 如果一共节点是红色，那么他的子节点一定是黑色（不会出现两个红色节点连接的情况）
  4. 对于每个节点，以这个节点到所有后代的任意路径上，均包含相同数目的黑色节点
  5. 每个叶子节点（空节点）是黑色的（为了满足第四条性质，某些情况下如果没有第五条第四条会失效）

节点的定义

// 颜色
enum Color {
	RED,
	BLACK
};

template<class T>
struct RBTreeNode {
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;

	Color _col;

	RBTreeNode(const T& data) 
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)
	{}
};

我们定义颜色时，使用枚举类型，可以方便且明了的看到颜色

除此之外我们默认插入节点是红色的，因为一旦插入节点是黑色，就会违反第四条规则，如果要满足的话，就要走到每一条路径上插入对应的黑色节点，代价巨大

当插入节点是红色时，有可能会违反第三条规则，但是我们可以通过变色，旋转等操作在局部进行改变，这样就能使之仍然满足条件

红黑树的结构

为了后续利用红黑树封装map和set，我们对红黑树增加一个头节点，为了和根节点进行区分，我们将头节点赋为黑色，并且让头节点的parent指向根节点，left指向红黑树的最小节点，right指向最大节点，如图

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

红黑树的插入

红黑树插入时也是按照二叉搜索树的规则进行插入，并在此基础上加上平衡条件，因此插入也就分为两步

  1. 按照二叉搜索树的规则插入新节点
  2. 插入节点后检测规则是否被破坏

因为插入红节点时只有可能破坏第三条规则，因此我们只需要判断父节点是否为红色即可

然后我们分情况讨论

为了方便叙述，我们约定cur为插入节点，p为父节点，g为祖父节点，u为叔叔节点

cur为红，p为红，g为黑，u存在且为红

画出来是这样的

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

这时我们需要将g改为红色，p和u改为黑色即可，这样既能保证红色不连续，黑色数量一致，如图

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

但是如果g是是子树，那么g一定有父节点，当g的父节点也是红色时，也就同样需要向上调整了

cur为红，p为红，g为黑，u不存在或u为黑，插入到p对应的一边

画出来是这样的

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

u的情况有两种

  1. u节点不存在，说明cur一定是新插入的节点，因为要保证左右两个路径的黑色节点的数量相同
  2. u节点存在，说明cur节点是由下至上调整的红色，原因也是左右路径的黑色节点要相同

对于这两种情况的调整方法是相同的，如果p是g的左节点，cur为p的左节点，则右单旋，如果p是g的右节点，cur为p的右节点，则左单旋

同时p要变成黑色，g要变成红色

变成如下状态

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

那么因为最上面的根节点颜色没有变化，也就不需要继续向上调整了

cur为红，p为红，g为黑，u不存在或u存在且为黑，插入到与p相反的一边

如图

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

这种情况需要针对p进行单旋，如果p为g的左节点，cur为p的右节点，则对p左单旋，反之则为右单旋，此时就会变成第二种情况，再继续处理即可

第一次处理的结果如下

C++手撕红黑树,C++,c++,开发语言,红黑树,数据结构

示例代码
template<class K, class T, class KeyOfT>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	pair<Node*, bool> Insert(const T& data) {
		// 插入根节点直接返回
		if (_root == nullptr) {
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}

		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;

		// 平衡二叉树找到插入位置
		while (cur) {
			if (kot(cur->_data) < kot(data)) {
				parent = cur;
				cur = cur->_right;
			} else if (kot(cur->_data) > kot(data)) {
				parent = cur;
				cur = cur->_left;
			} else {
				return make_pair(cur, false);
			}
		}

		// 新建节点
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;

		// 连接父节点
		if (kot(parent->_data) < kot(data)) {
			parent->_right = cur;
			cur->_parent = parent;
		} else {
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 如果父节点存在且父节点为红色则需要调整
		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left) {
				//     g
				//   p   u
				// c 
				// 判断u是否存在和他的颜色
				Node* uncle = grandfather->_right;
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 向上调整
					cur = grandfather;
					parent = cur->_parent;
				} else {
					// 如果不存在或u为黑色，需要判断同侧还是异侧
					// 如果是同侧
					if (cur == parent->_left) {
						//     g
						//   p
						// c
						RotateR(grandfather); // 右旋

						// 调整颜色
						parent->_col = BLACK;
						grandfather->_col = RED;
					} else {
						//    g
						//  p
						//    c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}

			} else { // p = g->r
				Node* uncle = grandfather->_left;
				//     g
				//   u   p
				//         c
				// 判断u是否存在和他的颜色
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 向上调整
					cur = grandfather;
					parent = cur->_parent;
				} else {
					if (cur == parent->_right) {
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					} else {
						//     g
						//   u   p 
						//     c
						//
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}

		_root->_col = BLACK;

		return make_pair(newnode, true);


	}

	void RotateL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = subR;
			} else {
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (_root == parent) {
			_root = subL;
			subL->_parent = nullptr;
		} else {
			if (parentParent->_left == parent) {
				parentParent->_left = subL;
			} else {
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}
	}
private:
	Node* _root = nullptr;
};

红黑树的验证

红黑树要验证需要验证两个部分

  1. 检测是否中序遍历是有序序列
  2. 检测是否满足红黑树的性质

这里我们就不讲红黑树的删除了，完成红黑树的验证之后就算作已经完成了任务，接下来会使用红黑树模拟实现map和set

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，但是红黑树不追求绝对的平衡，降低了插入和旋转的次数，因此性能比AVL更优，而且红黑树比AVL树的实现更加简单，所以实际中运用红黑树更多文章来源地址https://www.toymoban.com/news/detail-848473.html

完整代码

#pragma once
#include<utility>
#include<iostream>
using namespace std;
// 颜色
enum Color {
	RED,
	BLACK
};

template<class T>
struct RBTreeNode {
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;

	Color _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED) {}
};


template<class K, class T, class KeyOfT>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	pair<Node*, bool> Insert(const T& data) {
		
		if (_root == nullptr) {
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}

		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;

		// 平衡二叉树找到插入位置
		while (cur) {
			if (kot(cur->_data) < kot(data)) {
				parent = cur;
				cur = cur->_right;
			} else if (kot(cur->_data) > kot(data)) {
				parent = cur;
				cur = cur->_left;
			} else {
				return make_pair(cur, false);
			}
		}

		// 新建节点
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;

		// 连接父节点
		if (kot(parent->_data) < kot(data)) {
			parent->_right = cur;
			cur->_parent = parent;
		} else {
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 如果父节点存在且父节点为红色则需要调整
		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left) {
				//     g
				//   p   u
				// c 
				// 判断u是否存在和他的颜色
				Node* uncle = grandfather->_right;
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 向上调整
					cur = grandfather;
					parent = cur->_parent;
				} else {
					// 如果不存在或u为黑色，需要判断同侧还是异侧
					// 如果是同侧
					if (cur == parent->_left) {
						//     g
						//   p
						// c
						RotateR(grandfather); // 右旋

						// 调整颜色
						parent->_col = BLACK;
						grandfather->_col = RED;
					} else {
						//    g
						//  p
						//    c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}

			} else { // p = g->r
				Node* uncle = grandfather->_left;
				//     g
				//   u   p
				//         c
				// 判断u是否存在和他的颜色
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 向上调整
					cur = grandfather;
					parent = cur->_parent;
				} else {
					if (cur == parent->_right) {
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					} else {
						//     g
						//   u   p 
						//     c
						//
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}

		_root->_col = BLACK;

		return make_pair(newnode, true);


	}

	void RotateL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = subR;
			} else {
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (_root == parent) {
			_root = subL;
			subL->_parent = nullptr;
		} else {
			if (parentParent->_left == parent) {
				parentParent->_left = subL;
			} else {
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}
	}

	void InOrder() {
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root) {
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_data << ' ';
		_InOrder(root->_right);
	}

	bool Check(Node* root, int blacknum, const int refVal) {
		if (root == nullptr) {
			if (blacknum != refVal) {
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED) {
			cout << "存在连续的红节点" << endl;
			return false;
		}

		if (root->_col == BLACK) {
			++blacknum;
		}
		
		return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);
	}

	bool IsBalance() {
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		int refVal = 0; // 参考值
		Node* cur = _root;
		while (cur) {
			if (cur->_col == BLACK) {
				++refVal;
			}
			cur = cur->_left;
		}

		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}

	int Height() {
		return _Height(_root);
	}

	int _Height(Node* root) {
		if (root == nullptr)
			return 0;

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH + rightH;
	}

	size_t Size() {
		return _Size(_root);
	}

	size_t _Size(Node* root) {
		if (root == nullptr)
			return 0;
		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	Node* Find(const K& key) {
		Node* cur = _root;
		while (cur) {
			if (cur->_data < key) {
				cur = cur->_right;
			}
			else if (cur->_data > key) {
				cur = cur->_left;
			}
			else {
				return cur;
			}
		}
		return nullptr;
	}

private:
	Node* _root = nullptr;
};

到了这里，关于C++手撕红黑树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 手撕红黑树

    手撕红黑树

    由于AVL对于平衡的要求过于严格，这就导致了AVL的调整操作会被大量的进行，别看单词的时间消耗短，由于AVL树对于平衡要求的苛刻，这就会积累大量的旋转操作，这一累加起来就是不小的时间消耗； 为了减少AVL树的旋转操作，红黑树不就诞生了！ 红黑树:红黑树不是一颗严

    2024年02月04日
    浏览(51)
  • 【手撕红黑树】

    【手撕红黑树】

    相信很多人初学者听到了红黑树后心中不免有些心慌，那你看到了这篇文章后相信会有所收获，我其实刚开始也是对红黑树抱着一种害怕甚至是恐惧，但是在老师的帮助下也终于慢慢的不在恐惧了，你想知道为什么的话就继续往下看吧。（注意本篇博客只讲解了红黑树的插入

    2024年02月05日
    浏览(34)
  • 史上最详细的红黑树讲解(一篇文章教你手撕红黑树)

    史上最详细的红黑树讲解(一篇文章教你手撕红黑树)

           🔥🔥 欢迎来到小林的博客！！       🛰️博客主页：✈️小林爱敲代码       🛰️博客专栏：✈️数据结构与算法       🛰️欢迎关注：👍点赞🙌收藏✍️留言       今天给大家讲解红黑树，和AVL树一样，这章暂且不讲删除。

    2024年01月16日
    浏览(40)
  • C++数据结构--红黑树

    C++数据结构--红黑树

    红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍，因而是接近平衡的。如图所示： 每个结点不是红色就是黑色。

    2024年02月09日
    浏览(46)
  • 【数据结构】—红黑树（C++实现）

    【数据结构】—红黑树（C++实现）

                                                            🎬 慕斯主页 ： 修仙—别有洞天                                                  💜 本文前置知识：  AVL树                                                       ♈️ 今日夜电波 ：

    2024年02月05日
    浏览(50)
  • 【数据结构】红黑树（C++实现）

    【数据结构】红黑树（C++实现）

    👀 樊梓慕： 个人主页  🎥 个人专栏： 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子，都是对生命的辜负 目录 前言 1.概念 2.性质 3.节点的定义  4.插入 4.1情况1：叔叔u存在且为红 4.2情况2：

    2024年03月13日
    浏览(53)
  • 数据结构：红黑树讲解（C++）

    数据结构：红黑树讲解（C++）

    本文旨在 理解红黑树基本概念以及变色旋转规则 ，以理解C++ map 和 set 的底层原理，不会讲红黑树的删除操作。 对于基本的旋转操作(单旋和双旋)，本文不会展开讲，详细讲解在这里： AVL树旋转讲解。 2.1概念 红黑树，是一种二叉搜索树，但在每个结点上 增加一个存储位表示

    2024年02月05日
    浏览(42)
  • [数据结构 - C++] 红黑树RBTree

    [数据结构 - C++] 红黑树RBTree

    我们在学习了二叉搜索树后，在它的基础上又学习了AVL树，知道了AVL树是靠平衡因子来调节左右高度差，从而让树变得平衡的。本篇我们再来学习一个依靠另一种平衡规则来控制的二叉搜索树——红黑树。 红黑树 ，是一种 二叉搜索树 ， 但在每个结点上增加一个存储位表示

    2024年01月23日
    浏览(45)
  • 【高阶数据结构】红黑树 {概念及性质；红黑树的结构；红黑树的实现；红黑树插入操作详细解释；红黑树的验证}

    【高阶数据结构】红黑树 {概念及性质；红黑树的结构；红黑树的实现；红黑树插入操作详细解释；红黑树的验证}

    红黑树（Red Black Tree） 是一种自平衡二叉查找树，在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 AVL树 VS 红黑树 红黑树是

    2024年02月09日
    浏览(47)
  • 红黑树数据结构

    红黑树数据结构

    现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的，然后很多地方也是用到红黑树，这里单独对红黑树数据结构进行简单的介绍。 目录 红黑树概念 红黑树的性质 自平衡规则 代码   红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可

    2024年02月01日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包