• 中级C++：红黑树

    文章目录

    红黑树的特征

    • 也是对二叉搜索树高度的控制，但没有AVL树（也叫高度平衡二叉搜索树）那么严格；红黑树：最长路径不超过最短路径的两倍。
      • 在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
      • 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
    • 红黑树的性质
      • 每个结点不是红色就是黑色；
      • 根节点是黑色的；
      • 如果一个节点是红色的，则它的两个孩子结点是黑色的；（不能有连续的红色）
      • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点；
      • 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，用来确定有多少条路经的)。
        在这里插入图片描述
    • 时间复杂度：
      • 接近平衡，按满二叉树的节点总数来算，h层一共有 2^h-1 个节点，又是搜索二叉树，因此查找一个值只需要查找高度次：
      • 2^h-1 = N ; h = log2 (N+1) ; h = log2 N…
      • 最坏情况：最长路径是最短的2倍，则： h = 2log2 N ,当 N 是10亿时，h 是 30；对于现在的cpu来说，2倍找60 次可以忽略。
    • 红黑树与AVL树的比较：
      • 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( log2 N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍。
      • 相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
    • 课外阅读：

    红黑树节点的定义

    #include<iostream>
using namespace std;
enum Colour
{
	RED,
	BLACK
};

	template<class K,class V>
	struct RBTreeNode
	{
		RBTreeNode* _left;
		RBTreeNode* _right;
		RBTreeNode* _parent;
		pair<K, V> _kv;
		Colour _col;

		RBTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_kv(kv)
			,_col(RED)
		{

		}
	};

    • 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

    红黑树的插入

    • 插入新节点的颜色
      • 根据上述几点性质可知，新插入节点的颜色是红色合适，如果节点父亲是红色，那么影响的只有某个子树的某格子数的某一条边…；
      • 如果节点父亲是黑色，新插入的也是黑色，那么每条路径的黑色节点个数就不一样了，影响的是整个树。
    • 插入新节点的父亲节点是红色时，那么必然有祖父结点且为黑；此时看叔叔结点：分两种情况（变色/旋转加变色）
      • （情况一）叔叔节点存在且为红，则父亲和叔叔变红色，祖父结点变红色，继续往上处理；
        • 如果祖父就是根，那么祖父也变黑。
        • 不是根就会变成情况二的情况：因为祖父节点原来是黑色，变成了红色；
        • 对于祖父上面的那一条路径来说，祖父的父亲可能是红，就不满足红黑树的性质了；
        • 所以情况二的 新插入节点 也可能是变了色的祖父节点更新过来的…
      • （情况二）叔叔节点不存在 或 存在且为黑，那么看情况进行单旋变色，或双璇变色；
        • 如果新插入节点是在 父亲 的 左边，父亲也是在 祖父 的 左边，那么进行 右单旋；之后，父亲变黑，祖父变红。
        • 如果新插入节点是在 父亲 的 右边，父亲也是在 祖父 的 右边，那么进行 左单旋；之后，父亲变黑，祖父变红。
        • 如果新插入节点是在 父亲 的 右边，父亲也是在 祖父 的 左边，那么进行 左单旋，再进行右单旋；之后，新插入节点变黑，祖父变红。
        • 如果新插入节点是在 父亲 的 左边，父亲也是在 祖父 的 右边，那么进行 右单旋，再进行左单旋；之后，新插入节点变黑，祖父变红。
          在这里插入图片描述
          在这里插入图片描述
    • 插入还是二叉搜索树的插入，这里只展示对节点颜色的处理：
    • 旋转和AVL树的旋转一样：看这里
    template<class K, class V>
		class RBTree
		{
			typedef RBTreeNode<K, V> Node;
		public:
			RBTree()
				:_root(nullptr)
			{
			}
			..../insert...
		private:
			Node* _root;
		}
          bool Insert(const pair<K, V>& kv)
			{
				if (_root ==nullptr)
				{
					_root = new Node(kv);
					_root->_col = BLACK;//根节点必须是黑色
					return true;
				}
				Node* parent = nullptr;
				Node* cur = _root;
				while (cur)
				{
					if (cur->_kv.first<kv.first)
					{
						parent = cur;
						cur = cur->_right;
					}
					else if (cur->_kv.first > kv.first)
					{
						parent = cur;
						cur = cur->_left;
					}
					else
					{
						return false;//不允许冗余
					}
				}
				cur = new Node(kv);
				cur->_col = RED;  //如果添加的是黑色，则对整个树都有影响，红色只对一个子树的一个路径有影响
				cur->_parent = parent;
				if (parent->_kv.first<cur->_kv.first)
				{
					parent->_right = cur;
				}
				else
				{
					parent->_left = cur;
				}
				//1，叔叔存在且为红，变色往上继续处理；2，叔叔不存在或存在且为黑：旋转+变色
				//若插入节点双亲的颜色是黑色便不需要处理
				while (parent&&parent->_col==RED)
				{
					Node* grandf = parent->_parent;//根不能是黑色，那么必定有个黑色的父亲
					if (grandf->_left==parent)
					{
						Node* uncle = grandf->_right;
						if (uncle && uncle->_col == RED)
						{
							parent->_col = uncle->_col = BLACK;//每条路径上的黑色节点个数保持不变
							grandf->_col = RED;

							cur = grandf;//祖父变红以后迭代往上更新，看没有连续的红色
							parent = cur->_parent;
						}
						else//叔不存在或黑 旋转变色
						{
							//祖父为节点进行右单旋或双旋
							if (cur=parent->_left)
							{
								//右单旋
								RotateR(grandf);
								grandf->_col = RED;
								parent->_col = BLACK;
							}
							else//先左旋 ，再右旋
							{
								RotateL(parent);
								RotateR(grandf);
								cur->_col = BLACK;
								grandf->_col = RED;								
							}
							break;
						}
					}
					else//(grandf->_right==parent)  叔叔存在为红，或不存在为黑
					{
						Node* uncle = grandf->_left;
						if (uncle && uncle->_col == RED)
						{
							parent->_col = uncle->_col = BLACK;
							grandf->_col = RED;

							cur = grandf;//祖父变红以后迭代往上更新，看没有连续的红色
							parent = cur->_parent;
						}
						else
						{
							if (cur=parent->_right)//左单旋
							{
								RotateL(grandf);
								parent->_col = BLACK;
								grandf->_col = RED;
							}
							else//先右旋，再左旋
							{
								RotateR(parent);
								RotateL(grandf);
								cur->_col = BLACK;
								grandf->_col = RED;
							}
							break;
						}
					}

				}
				_root->_col = BLACK;//当叔叔存在且为红，祖父就是根，上面变完色出来把祖父的颜色改为黑色。
				return true;
			}

    • 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
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121

    验证是否是红黑树

    • 一、中序遍历是否有序
    • 二、是否满足红黑树的性质
      • 每一条路径都和我基准值一样则满足每条路径的黑色个数相等
      • 不能有连续的红色：红色节点的两个孩子节点必须是黑色，转换成看红色节点的父亲是不是黑色；因孩子节点可能为空，不好处理。
               bool IsRBTree()
			{
				return _IsRBTree(_root);//包一层，方便外面对象调用
			}
           bool _IsRBTree(Node* cur)
			{
				if (cur==nullptr)
				{
					return true;//空树也是红黑树
				}
				if (cur->_col==RED)
				{
					cout << "根节点不是黑色，不是红黑树" << endl;
					return false;
				}
				int Benchmark = 0;//基准值
				Node* countcur = cur;
				while (countcur)
				{
					if (countcur->_col==BLACK)//每一条路径都和我基准值一样则满足每条路径的黑色个数相等
					{
						++Benchmark;
					}
					countcur = countcur->_left;//任选一条路径作为基准值。
				}
				int layer_black = 0;//递归调用再传一个参数：记录一下每一层到上面总共有的黑色节点个数，这样就方便很多了
				return red_node_is_black(cur)&&
					black_num_is_same(cur, layer_black, Benchmark);
			}
			
           bool red_node_is_black(Node* cur)//看红色节点孩子是不是黑色等于是看有没有连续的红色。
			{
				if (cur==nullptr)
				{
					return true;
				}
				if (cur->_col == RED && cur->_parent->_col != BLACK)
				{
					return false;//当前节点是红，那么必有双亲节点是黑色。
				}

				return red_node_is_black(cur->_left) &&
					red_node_is_black(cur->_right);
			}
			
		bool black_num_is_same(Node* cur, int layer_black, int Benchmark)
			{
				if (cur==nullptr)
				{
					if (layer_black==Benchmark)//路径走完，与基准值比较
					{
						return true;
					}
					else
					{
						return false;
					}
				}
				if (cur->_col==BLACK)
				{
					++layer_black;
				}
				return black_num_is_same(cur->_left, layer_black, Benchmark) &&
					black_num_is_same(cur->_right, layer_black, Benchmark);
			}

    • 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
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65

    G.

    下一篇是，将红黑树改造成 map和set 的 底层，模板参数再度来袭，红黑树的迭代器…

  • 相关阅读:
    空间变形网络——STN
    技术问题整理01
    重装系统后打印机状态已暂停如何恢复
    unity 手写板 截取游戏画面 识别手写文字 全家桶
    蓝桥杯嵌入式国赛笔记(4):多路AD采集
    电脑入门：路由器常见问题排错步骤
    多角度了解ABeam（德硕）技术架构
    Mybiosource丨Mybiosource兔抗人磷脂酶 A2 多克隆抗体
    C++模板编程（21）---C++实例化实现方案implementation Schemes
    Gazebo 控制实例
  • 原文地址：https://blog.csdn.net/WTFamer/article/details/125469405