文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【C++】2.6 红黑树及其实现（附代码）

【C++】2.6 红黑树及其实现（附代码）

作者头像
用户11952558
发布于 2026-01-09 14:14:18
发布于 2026-01-09 14:14:18
1220
举报

1. 红黑树规则

红黑树：最长分支≤最短分支2倍的树

规则：

  1. 每个节点要么红，要么黑
  2. 根节点为黑
  3. 若一个节点为红，那么它接着的子节点为黑
  4. 任意节点到所有的空节点，均包含等量黑节点

通过这四条规则，即可实现最长分支≤最短分支2倍

为什么？ 由于第四条规则，因此极端情况下：

  1. 最短的路径由全黑构成
  2. 最长的路径由一半黑一半红构成（因为红后面必须接黑）
  3. 每条路径黑节点数相等

因此最长分支≤最短分支2倍

所以第3条规则控制最短的分支，第4条规则控制最长的分支

2. 实现

1. 枚举，红色和黑色
代码语言：javascript
复制
enum color
{
    red,
    black
};
2. 树节点，比AVL树多一个颜色变量
代码语言：javascript
复制
template<class K, class V>
struct rbtreenode
{
    std::pair<K, V> _kv;
    rbtreenode* _left;
    rbtreenode* _right;
    rbtreenode* _par;
    color _col;
    
    rbtreenode(const std::pair<K,V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _par(nullptr)
    { }
};
3. 插入

如果插入黑色节点，那么树必定会不符合红黑树规则 由于原先每条路径的黑节点数量都是一样的，插入黑节点就意味着一定会有一条路的黑节点不一样 因此插入统一插红节点

  1. 父节点为黑：可以直接结束，符合红黑树
  2. 父节点为红：由于规定红节点后必须为黑节点，因此需要变换 由于父节点为红，那么爷节点为黑，叔节点可能为红也可能为黑
代码语言：javascript
复制
bool insert(const std::pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new node(kv);
        _root->_col = black;
        return 1;
    }
    
    node* par = nullptr;
    node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            par = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            par = cur;
            cur = cur->_left;
        }
        else
        {
            return 0;
        }
    }
    
    cur = new node(kv);
    cur->_col = red;
    
    if (par->_kv.first < kv.first)
    {
        par->_right = cur;
    }
    else
    {
        par->_left = cur;
    }
    cur->_par = par;
    
    while (par && par->_col == red)
    {
        // 进行变换
    }
    
    _root->_col = black;
}

当父节点为黑时就停止，为红时就走while (par && par->_col == red)逻辑，直到父节点不为红为止 但是由于最后可能会一致变到root节点甚至root节点往上，因此就需要par &&以防野指针 此外由于可能会将根节点变红，因此最后要_root->_col = black;

为什么可以这么简单粗暴将root节点改为黑？ 由于任何路径都是根节点开始的，第四条规则（任意节点到所有的空节点，均包含等量黑节点）与root的颜色无关，因此可以直接改

4. 变换

首先，虽然图上面我们默认当前节点时左叶子节点，但实际上左右都有可能，因此我们要写两套逻辑

代码语言：javascript
复制
while (par && par->_col == red)
{
    node* grand = par->_par;
    if (par == grand->_left)
    {
        // 左子树情况
    }
    else
    {
        // 右子树情况
    }
}

下面我们讲的时候都默认第一套逻辑，即为左节点，par == grand->_left

1. 变色：叔节点为红

将爷节点变为红色，父节点和叔节点变为黑色 如果爷节点的父节点为红色，那么就继续往上更新，再继续分类讨论

代码语言：javascript
复制
node* uncle = par->_right;
if (uncle && uncle->_col == red)
{
    par->_col = black;
    uncle->_col = black;
    cur = grand;
    par = cur->_par;
}
2. 旋转：没有叔节点，或叔节点为黑

两个的共同点：插入节点后仅仅通过变色不能维持平衡 旋转方式与AVL树类似，按照要调整的节点与已有节点方向是否相同，分为单旋，双旋

2.1 单旋：
  • 叔节点不存在 此时只需要转父节点，再将两个节点变红
  • 叔节点为黑 此时，先确定颜色：
    1. 爷节点为黑：这种情况在x插入之前也是不符合红黑树规则的，因此不存在
    2. 爷为红节点：此时，本来就可以平衡

因此，这种叔节点为黑的情况不会出现在插入新节点时，只会存在于向上调整节点时

真实情况： 爷节点为黑，父节点为红，叔节点为黑，当前节点为黑 看似是平衡的，但是定量分析就出现破绽了 设父节点的子树的黑节点高度为h 那么4个子树在原来平衡时黑节点高度分别为h，h+1，h，h 但是当前由于调整上来的，因此当前节点的子树黑高度加了1 因此，这种情况需要旋转不是局部高度的问题，而是子树的黑节点多了一个

处理方法： 和前面一样，可以直接用AVL树的旋转 变色方法：最后爷节点变为黑色，父和叔节点变为红色即可

2.2 双旋

原理和AVL树一模一样

逻辑
代码语言：javascript
复制
if (uncle && uncle->_col == red)
{
    // 上文变色逻辑
}
else
{
    if (par->_left == cur) // 单旋
    {
        rotateR(grand);
        par->_col = black;
        grand->_col = red;
    }
    else // 双旋
    {
        rotateL(par);
        rotateR(grand);
        cur->_col = black;
        grand->_col = red;
    }
    break;
}
旋转代码（同AVL树）
代码语言：javascript
复制
void rotateR(node* par)
{
    node* subL = par->_left;
    node* subLR = subL->_right;
    
    par->_left = subLR;
    if (subLR) subLR->_par = par;
    
    node* grand = par->_par;
    subL->_right = par;
    par->_par = subL;
    
    if (grand)
    {
        if (grand->_left == par)
        {
            grand->_left = subL;
        }
        else
        {
            grand->_right = subL;
        }
    }
    else
    {
        _root = subL;
    }
}

void rotateL(node* par)
{
    node* subR = par->_right;
    node* subRL = subR->_left;
    
    par->_right = subRL;
    if (subRL) subRL->_par = par;
    
    subR->_left = par;
    node* grand = par->_par;
    par->_par = subR;
    
    if (grand)
    {
        if (grand->_left == par)
        {
            grand->_left = subR;
        }
        else
        {
            grand->_right = subR;
        }
        subR->_par = grand;
    }
    else
    {
        _root = subR;
        subR->_par = nullptr;
    }
}

3. 测试红黑树

需要测试点：1.根节点为黑 2.红后面只能接黑 3.每条路黑节点一样多

第一点很简单

第二三点可以递归+回溯做： 先在公有里定义一个公有测试函数，任务是1.遍历取出最左边分支黑节点个数 2.取出根节点

代码语言：javascript
复制
bool check()
{
    if (_root->_col != black) return 0;
    
    node* cur = _root;
    int cnt = 0;
    while (cur)
    {
        if (cur->_col == black)
        {
            cnt++;
        }
        cur = cur->_left;
    }
    
    int pos = 1;
    return _check(_root->_left, cnt, pos) && _check(_root->_right, cnt, pos);
}

再定义一个私有，进行递归：

代码语言：javascript
复制
bool _check(node* root, int cnt, int pos)
{
    if (root == nullptr) return cnt == pos;
    
    if (root->_col == black) pos++;
    
    if (root->_col == red)
    {
        int fl = 1;
        if (root->_left)
        {
            if (root->_left->_col != black) fl = 0;
        }
        if (root->_right)
        {
            if (root->_right->_col != black) fl = 0;
        }
        if (fl == 0) return 0;
    }
    
    return _check(root->_left, cnt, pos) && _check(root->_right, cnt, pos);
}

4. Set和map实现

4.1 源代码实现

由于map和set的主要程序一模一样，区别只有里面传的是key还是pair 因此库里面没有实现2次，而是用了模板

在stl_map和stl_set里，类的private里共同有以下语句：

代码语言：javascript
复制
typedef _Rb_tree<key_type, value_type,
                 _Identity<value_type>, key_compare, _Alloc> _Rep_type;

在这个上文中 不论是在map里还是在set里，都有

代码语言：javascript
复制
typedef _Key key_type;

意味着key_type就是我们模板里的第一个参数 map<string,int>里的string或者set<string>里的string 因此key_type就是我们的key，就是我们数值的key支持比较

不同的地方在于value_type的定义：

  • Map：typedef pair<const _Key, _Tp> value_type;
  • Set：typedef _Key value_type; 就是map中代表pair<string,int>，set中代表string

那_Value是干什么的？ 在stl_tree中，有

代码语言：javascript
复制
typedef _Rb_tree_node<_Value> _Rb_tree_node;

因此_Value就是节点类型的定义

因此就明白了：

  • _Key存数据时用
  • _Value节点定义时用
4.2 仿照库里的map，set成员

由于key，val作为模板对象会和key-val对搞混，因此就命名为K（key）和T

Map：

代码语言：javascript
复制
template<class K, class V>
class map
{
private:
    RBTree<K, std::pair<K, V>> _t;
};

Set：

代码语言：javascript
复制
template<class K>
class set
{
private:
    RBTree<K, K> _t;
};
4.3 取出key的仿函数

由于插入值是要比较的 在正常的map里，因为我们知道是个pair类型，因此是这么写的

代码语言：javascript
复制
if (cur->_kv.first < kv.first)

在正常的set里，因为我们知道是个单独的类型，因此就不用first

代码语言：javascript
复制
if (cur->_kv < kv)

但是，我们在泛型的tree里，是不知道有没有first的，因此需要一个函数取出key的值 分别在map和set里写一下对应仿函数 这样就可以在template里和模板一起传过去了

代码语言：javascript
复制
// Set的仿函数
struct setkeyoft
{
    const K& operator()(const K& k)
    {
        return k;
    }
};

// Map的仿函数
struct mapkeyoft
{
    const K& operator()(const std::pair<K,V>& kv)
    {
        return kv.first;
    }
};

因此，比较逻辑就可以这么写

代码语言：javascript
复制
if (kot(cur->_data) < kot(data))
4.4 迭代器声明

同样，const版本和非const版本可以合成一份

代码语言：javascript
复制
template<class T, class Ref, class Ptr>
struct tree_iterator
{
    typedef rbtreenode<T> node;
    typedef tree_iterator<T, Ref, Ptr> self;
    node* _node;
    
    tree_iterator(node* node)
        : _node(node)
    { }
};

由于我们不知道传的是const还是非const 因此ref可能是const &或& Ptr可能是const 或

4.5 简单成员函数
代码语言：javascript
复制
Ref operator*()
{
    return _node->_data;
}

Ptr operator->()
{
    return &_node->_data;
}

bool operator==(const self& it) const
{
    return _node == it._node;
}

bool operator!=(const self& it) const
{
    return _node != it._node;
}

注意，->重载，注意运算符顺序，返回的是_node->_data的地址

4.6 迭代器++的实现

看整体不看部分 中序遍历为：左，中，右，只需要看当前在哪一步即可

  1. 当前节点有右节点 说明当前在遍历中节点，下一步要到左，即是右子树的最左节点
  2. 没有右节点 可能当前节点在父节点左边或者右边
    • 在左边：说明此时在遍历左，可以直接跳到父节点
    • 在右边：说明此时父节点，当前节点都遍历过了，要一直向上找，找到在左边的节点
代码语言：javascript
复制
self operator++()
{
    if (_node->_right)
    {
        node* down = _node->_right;
        while (down->_left)
        {
            down = down->_left;
        }
        _node = down;
    }
    else
    {
        node* cur = _node;
        node* par = cur->_par;
        while (par && par->_right == cur)
        {
            cur = par;
            par = par->_par;
        }
        _node = par;
    }
    return *this;
}
4.7 迭代器--

与++类似 但是，我们将end设计成空节点，而end迭代器--我们应该返回最右边节点 但是，如果没有_root节点我们将找不到最右边节点，因此需要在迭代器中新增成员，_root

代码语言：javascript
复制
node* _node;
node* _root;

tree_iterator(node* node, node* root)
    : _node(node)
    , _root(root)
{ }

其余，只要将++的左右反过来就可以了

代码语言：javascript
复制
self operator--()
{
    if (_node == nullptr)
    {
        node* down = _root;
        while (down && down->_right)
        {
            down = down->_right;
        }
        _node = down;
    }
    else if (_node->_left)
    {
        node* down = _node->_left;
        while(down->_right)
        {
            down = down->_right;
        }
        _node = down;
    }
    else
    {
        node* cur = _node;
        node* par = cur->_par;
        while (par && cur == par->_left)
        {
            cur = par;
            par = par->_par;
        }
        _node = par;
    }
    return *this;
}
4.8 begin和end函数
代码语言：javascript
复制
typedef tree_iterator<T, T&, T*> Iterator;
typedef tree_iterator<T, const T&, const T*> const_Iterator;

Iterator Begin()
{
    node* cur = _root;
    while (cur && cur->_left)
    {
        cur = cur->_left;
    }
    return Iterator(cur, _root);
}

Iterator End()
{
    return Iterator(nullptr, _root);
}

const_Iterator Begin() const
{
    node* cur = _root;
    while (cur && cur->_left)
    {
        cur = cur->_left;
    }
    return const_Iterator(cur, _root);
}

const_Iterator End() const
{
    return const_Iterator(nullptr, _root);
}

注意，由于迭代器可能是由map或set传的，因此这只是函数，不是正式迭代器 因此命名第一个字母大写用来区分

4.9 键值防修改

上面代码写完，就支持范围for了 但是关键点是first可以被修改 因此就需要将k改为const的

代码语言：javascript
复制
rbtree<K, std::pair<const K, V>, mapkeyoft> _t;

只需要在第二个模板定为const，即可 修改，就会报错：左值指定 const 对象

4.10 []重载和insert复用

map，set插入返回的是（迭代器，是否成功）的pair 因此在返回的地方修改即可 但是，注意，由于cur会被我们不断向上，因此要提前存下cur的位置

代码语言：javascript
复制
std::pair<Iterator, bool> insert(const T& data)
{
    // ......
}

Map和set的配套修改

代码语言：javascript
复制
// Map的insert
std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
{
    return _t.insert(kv);
}

// Set的insert
std::pair<iterator, bool> insert(const K& k)
{
    return _t.insert(k);
}

// Map的[]重载
V& operator[](const K& k)
{
    std::pair<iterator, bool> ret = insert({k, V()});
    return ret.first->second;
}
4.11 源码实现

在end迭代器上，源码是先用一个没有意义的哨兵节点 左指向最左边的节点，右指向最右边的节点 好处是取begin节点时可以直接哨兵节点左边即可 但是插入值需要维护哨兵节点的指向

代码

tree.h
代码语言：javascript
复制
#pragma once
#include<iostream>
#include<assert.h>
namespace my
{
	enum color
	{
		red,
		black
	};
	template<class T>
	struct rbtreenode
	{
		T _data;
		rbtreenode* _left;
		rbtreenode* _right;
		rbtreenode* _par;
		color _col;
		rbtreenode(const T& data)
			:_data(data)
			, _left(nullptr)
			, _right(nullptr)
			, _par(nullptr)
		{
		}
	};
	template<class T,class ref,class ptr>
	struct tree_iterator
	{
		typedef rbtreenode<T> node;
		typedef tree_iterator<T, ref, ptr> self;
		node* _node;
		node* _root;
		tree_iterator(node* n,node* root)
			:_node(n)
			,_root(root)
		{ }
		ref operator*()
		{
			return _node->_data;
		}
		ptr operator->()
		{
			return &_node->_data;
		}
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}
		self operator++()
		{
			if (_node->_right)
			{
				node* down = _node->_right;
				while (down->_left)
				{
					down = down->_left;
				}
				_node = down;
			}
			else
			{
				node* cur = _node;
				node* par = cur->_par;
				while (par && par->_right == cur)
				{
					cur = par;
					par = par->_par;
				}
				_node = par;
			}
			return *this;
		}
		self operator--()
		{
			if (_node == nullptr)
			{
				node* down = _root;
				while (down && down->_right)
				{
					down = down->_right;
				}
				_node = down;
			}
			else if (_node->_left)
			{
				node* down = _node->_left;
				while(down->_right)
				{
					down = down->_right;
				}
				_node = down;
			}
			else
			{
				node* cur = _node;
				node* par = cur->_par;
				while (par && cur == par->_left)
				{
					cur = par;
					par = par->_par;
				}
				_node = par;
			}
			return *this;
		}
	};
	template<class K, class T,class keyoft>
	class rbtree
	{
		typedef rbtreenode<T> node;
	public:
		typedef tree_iterator<T, T&, T*>Iterator;
		typedef tree_iterator<T, const T&, const T*> const_Iterator;
		Iterator Begin()
		{
			node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return Iterator(cur,_root);
		}
		Iterator End()
		{
			return Iterator(nullptr,_root);
		}
		const_Iterator Begin() const
		{
			node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return Iterator(cur,_root);
		}
		const_Iterator End() const
		{
			return Iterator(nullptr,_root);
		}
		std::pair<Iterator,bool> insert(const T& data)
		{
			if (_root == nullptr)
			{
				_root = new node(data);
				_root->_col = black;
				return {Iterator(_root,_root),1};
			}
			keyoft kot;
			node* par = nullptr;
			node* cur = _root;
			while (cur)
			{
				if (kot(cur->_data) < kot(data))
				{
					par = cur;
					cur = cur->_right;
				}
				else if (kot(cur->_data) > kot(data))
				{
					par = cur;
					cur = cur->_left;
				}
				else
				{
					return {Iterator(cur,_root),0};
				}
			}
			node* ret = cur;//存下
			cur = new node(data);
			cur->_col = red;
			if (kot(par->_data) < kot(data))
			{
				par->_right = cur;
			}
			else
			{
				par->_left = cur;
			}
			cur->_par = par;
			while (par && par->_col == red)
			{
				node* grand = par->_par;
				if (par == grand->_left)
				{
					node* uncle = grand->_right;
					if (uncle && uncle->_col == red)
					{
						par->_col = black;
						uncle->_col = black;
						grand->_col = red;
						cur = grand;
						par = cur->_par;
					}
					else
					{
						if (par->_left == cur)
						{
							rotateR(grand);
							par->_col = black;
							grand->_col = red;
						}
						else
						{
							rotateL(par);
							rotateR(grand);
							cur->_col = black;
							grand->_col = red;
						}
						break;
					}
				}
				else
				{
					node* uncle = grand->_left;
					if (uncle && uncle->_col == red)
					{
						par->_col = black;
						uncle->_col = black;
						grand->_col = red;
						cur = grand;
						par = cur->_par;
					}
					else
					{
						if (par->_right == cur)
						{
							rotateL(grand);
							par->_col = black;
							grand->_col = red;
						}
						else
						{
							rotateR(par);
							rotateL(grand);
							cur->_col = black;
							grand->_col = red;
						}
						break;
					}
				}
			}
			_root->_col = black;
			return {Iterator(ret,_root),1};
		}
		void rotateR(node* par)
		{
			node* subL = par->_left;
			node* subLR = subL->_right;
			par->_left = subLR;
			if (subLR)subLR->_par = par;
			node* grand = par->_par;
			subL->_right = par;
			par->_par = subL;
			if (grand)
			{
				if (grand->_left == par)
				{
					grand->_left = subL;
				}
				else
				{
					grand->_right = subL;
				}
				subL->_par = grand;
			}
			else
			{
				_root = subL;
				subL->_par = nullptr;
			}
		}
		void rotateL(node* par)
		{
			node* subR = par->_right;
			node* subRL = subR->_left;
			par->_right = subRL;
			if (subRL) subRL->_par = par;
			subR->_left = par;
			node* grand = par->_par;
			par->_par = subR;
			if (grand)
			{
				if (grand->_left == par)
				{
					grand->_left = subR;
				}
				else
				{
					grand->_right = subR;
				}
				subR->_par = grand;
			}
			else
			{
				_root = subR;
				subR->_par = nullptr;
			}
		}
		//void InOrder()
		//{
		//	_InOrder(_root);
		//	std::cout << std::endl;
		//}

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

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

		node* Find(const K& key)
		{
			node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first < key)
				{
					cur = cur->_right;
				}
				else if (cur->_kv.first > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}

			return nullptr;
		}
		bool ckeck()
		{
			if (_root->_col != black)return 0;
			node* cur = _root;
			int cnt = 0;
			while (cur)
			{
				if (cur->_col == black)
				{
					cnt++;
				}
				cur = cur->_left;
			}
			int pos = 1;
			return _check(_root->_left, cnt, pos) && _check(_root->_right, cnt, pos);
		}

	private:
		//void _InOrder(node* root)
		//{
		//	if (root == nullptr)
		//	{
		//		return;
		//	}

		//	_InOrder(root->_left);
		//	//std::cout << root->_kv.first << ":" << root->_kv.second << root->_col << std::endl;
		//	_InOrder(root->_right);
		//}

		int _Height(node* root)
		{
			if (root == nullptr)
				return 0;
			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);
			return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
		}

		int _Size(node* root)
		{
			if (root == nullptr)
				return 0;

			return _Size(root->_left) + _Size(root->_right) + 1;
		}
		bool _check(node* root, int cnt, int pos)
		{
			if (root == nullptr)return cnt == pos;
			if (root->_col == black)pos++;
			if (root->_col == red)
			{
				int fl = 1;
				if (root->_left)
				{
					if (root->_left->_col != black)fl = 0;
				}
				if (root->_right)
				{
					if (root->_right->_col != black)fl = 0;
				}
				if (fl == 0)return 0;
			}
			return _check(root->_left, cnt, pos) && _check(root->_right, cnt, pos);
		}
		node* _root = nullptr;
	};
}
set.h
代码语言：javascript
复制
#pragma once
#include"tree.h"
namespace my
{
	template<class K>
	class set
	{
	public:
		struct setkeyoft
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
		typedef typename rbtree<K, const K, setkeyoft>::Iterator iterator;
		typedef typename rbtree<K, const K, setkeyoft>::const_Iterator const_iterator;
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator begin() const
		{
			return _t.Begin();
		}
		const_iterator end() const
		{
			return _t.End();
		}
		std::pair<iterator, bool> insert(const K& k)
		{
			return _t.insert(k);
		}
	private:
		rbtree<K, const K, setkeyoft> _t;
	};
}
map.h
代码语言：javascript
复制
#pragma once
#include"tree.h"
namespace my
{
	template<class K,class V>
	class map
	{
	public:
		struct mapkeyoft
		{
			const K& operator()(const std::pair<K,V>& kv)
			{
				return kv.first;
			}
		};
		typedef typename rbtree<K, std::pair<const K, V>, mapkeyoft>::Iterator iterator;
		typedef typename rbtree<K, std::pair<const K, V>, mapkeyoft>::const_Iterator const_iterator;
		iterator begin()
		{
			return _t.Begin();
		}

		iterator end()
		{
			return _t.End();
		}

		const_iterator begin() const
		{
			return _t.Begin();
		}

		const_iterator end()  const
		{
			return _t.End();
		}
		std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
		{
			return _t.insert(kv);
		}
		V& operator[](const K&k)
		{
			std::pair<iterator, bool>ret = insert({ k,V() });
			return ret.first->second;
		}
	private:
		rbtree<K, std::pair<const K,V>, mapkeyoft> _t;
	};
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除
函数
c++
return
root
遍历

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

函数
c++
return
root
遍历
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 1. 红黑树规则
  • 2. 实现
    • 1. 枚举，红色和黑色
    • 2. 树节点，比AVL树多一个颜色变量
    • 3. 插入
    • 4. 变换
      • 1. 变色：叔节点为红
      • 2. 旋转：没有叔节点，或叔节点为黑
      • 逻辑
    • 旋转代码（同AVL树）
  • 3. 测试红黑树
  • 4. Set和map实现
    • 4.1 源代码实现
    • 4.2 仿照库里的map，set成员
    • 4.3 取出key的仿函数
    • 4.4 迭代器声明
    • 4.5 简单成员函数
    • 4.6 迭代器++的实现
    • 4.7 迭代器--
    • 4.8 begin和end函数
    • 4.9 键值防修改
    • 4.10 []重载和insert复用
    • 4.11 源码实现
  • 代码
    • tree.h
    • set.h
    • map.h
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论