STL详解 - 红黑树模拟实现map与set-EW帮帮网

一、改造红黑树

1. 模板参数

2. 节点的存储内容

3. 仿函数的设计

3. 迭代器的难点：++ 和 -- 运算符的重载

4. 迭代器的 begin 和 end 方法

一、改造红黑树

1. 模板参数

红黑树是一种常用于实现有序容器的数据结构，其模板参数的设计对于实现 map 和 set 容器至关重要。但是在容器设计中，set基于K模型（键值型），而map采用KV模型（键值对型），那如何通过单一红黑树架构同时支撑两种容器呢？

我们可以定义一个通用的红黑树模板类，其中第一个模板参数 K 表示键的类型，第二个模板参数 T 表示存储的值的类型。这种设计允许我们通过不同的 T 参数来实现不同类型的容器。

template<typename K, typename T>
class RBTree
{}

set 容器存储的是唯一的键值，因此其底层红黑树存储的值类型 T 可以直接使用键类型 K。这样，每个节点存储的值就是键本身。

template<typename K>
class Set 
{
private:
    RBTree<K, K> tree;

public:
    //......
};

map 容器存储的是键值对，因此其底层红黑树存储的值类型 T 应该是 std::pair<K, V>。这样，每个节点存储的是键值对，键用于排序，值用于存储关联数据。

template<typename K, typename V>
class Map 
{
private:
    RBTree<K, std::pair<K, V>> tree;

public:
    //......
};

有人可能会问，红黑树的第二个模板参数 T 是否可以代替第一个参数 K，从而省略第一个参数。从理论上讲，T 中确实包含了键的类型信息，但省略第一个参数会导致以下问题：

对于 set 容器：set 的键值类型一致，这种情况下省略第一个参数似乎可行。然而，这会破坏代码的可读性和一致性。
对于 map 容器：map 提供的接口中，如 find 和 erase，仅需要键值 K 即可操作。省略第一个参数会导致这些接口无法正常工作，因为键值类型在逻辑上是独立需要明确指定的。

2. 节点的存储内容

在底层红黑树中，节点存储的是 T 类型的数据。这种设计的优势在于它能够根据上层容器的具体需求进行灵活调整：

对于 set 容器：K 和 T 都代表键值 Key。因此，红黑树节点中存储的 T 就是键值本身。这种设计使得 set 容器可以高效地管理唯一键值，而无需额外的复杂操作。
对于 map 容器：K 是键值 Key，而 T 是由键值 Key 和值 Value 组成的键值对（std::pair<K, V>）。在这种情况下，红黑树节点存储的是完整的键值对。这种设计使得 map 容器可以通过键值快速访问关联的值，同时保持高效的操作性能。

由于底层红黑树并不知道上层容器到底是 map 还是 set，因此直接存储 T 类型的数据是最合理的。这样，当上层容器是 set 时，节点存储的是键值 Key；而当上层容器是 map 时，节点存储的是键值对 <Key, Value>。

红黑树节点定义代码实现：

// 红黑树节点的定义
template<typename T>
struct RBTreeNode
{
    // 三叉链
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;

    // 存储的数据
    T _data;

    // 节点的颜色
    int _col; // 红色或黑色

    // 构造函数
    RBTreeNode(const T& data)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(data)
        , _col(1) // 假设 1 表示红色，0 表示黑色
    {}
};

3. 仿函数的设计

在设计红黑树作为底层数据结构时，我们需要灵活地处理节点中的键值比较问题。由于节点中存储的数据类型 T 可能是键值 Key 本身，也可能是 Key 和 Value 构成的键值对，因此我们需要一种通用的方式来获取键值以进行比较。这就引出了仿函数的使用。

仿函数的作用

仿函数是一种特殊的类，它通过重载 operator() 使得类的对象能够像函数一样被调用。在红黑树的场景中，仿函数的作用是提取节点数据 T 中的键值 Key，以便进行比较操作。

对于 set 容器：T 就是键值 Key，所以仿函数可以直接返回传入的 Key 值。
对于 map 容器：T 是键值对 <Key, Value>，仿函数需要从键值对中提取出 Key 用于比较。

仿函数的实现

在 map 容器中，我们定义一个仿函数来提取键值对中的 Key：

template<class K, class V>
class map 
{
    // 仿函数，用于从键值对中提取键值
    struct MapKeyOfT 
    {
        const K& operator()(const std::pair<K, V>& kv) 
        {
            return kv.first;
        }
    };

public:
    // ...

private:
    RBTree<K, std::pair<K, V>, MapKeyOfT> tree;
};

同样地，在 set 容器中，我们也需要一个仿函数，尽管它看起来很简单：

template<class K>
class set 
{
    // 仿函数，直接返回键值本身
    struct SetKeyOfT 
    {
        const K& operator()(const K& key) 
        {
            return key;
        }
    };

public:
    // ...

private:
    RBTree<K, K, SetKeyOfT> tree;
};

底层红黑树的处理方式

底层红黑树并不关心上层容器是 set 还是 map，它只需要通过传入的仿函数来获取键值。在红黑树的查找函数中，仿函数的使用如下：

iterator Find(const K& key) 
{
    KeyOfT kot; // 仿函数对象
    Node* cur = _root;
    while (cur) 
    {
        if (key < kot(cur->_data)) 
        {
            cur = cur->_left;
        } 
        else if (key > kot(cur->_data)) 
        {
            cur = cur->_right;
        } 
        else 
        {
            return iterator(cur);
        }
    }

    return end();
}

在红黑树的所有需要比较节点键值的地方，都会通过传入的仿函数来获取节点的键值，然后再进行比较。这样，无论是 set 还是 map 容器，底层红黑树都能以统一的方式处理键值比较。

二、红黑树的迭代器

迭代器是访问红黑树中数据的重要工具。通过迭代器，我们可以遍历红黑树中的所有节点。

1. 迭代器的基本结构

红黑树的迭代器主要封装了一个节点指针，通过这个指针来访问红黑树中的节点。

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
    typedef RBTreeNode<T> Node; // 节点的类型
    typedef __TreeIterator<T, Ref, Ptr> Self; // 迭代器的类型

    Node* _node; // 迭代器所封装节点的指针

    // 构造函数
    __TreeIterator(Node* node)
         : _node(node) 
         {}
};

2. 迭代器的操作

迭代器需要支持一些基本操作，比如解引用、箭头操作符以及比较运算符。

解引用操作符 (operator*): 返回当前节点数据的引用

Ref operator*()
{
    return _node->_data; // 返回节点数据的引用
}

箭头操作符 (operator->): 返回当前节点数据的指针

Ptr operator->()
{
    return &_node->_data; // 返回节点数据的指针
}

比较运算符 (operator== 和 operator!=): 比较两个迭代器是否指向同一个节点

bool operator!=(const Self& s) const
{
    return _node != s._node; // 判断两个迭代器所封装的节点是否是同一个
}

bool operator==(const Self& s) const
{
    return _node == s._node; // 判断两个迭代器所封装的节点是否是同一个
}

3. 迭代器的难点：++ 和 -- 运算符的重载

实现红黑树的迭代器时，真正的难点在于 ++ 和 -- 运算符的重载。这些操作符需要根据中序遍历的顺序来找到当前节点的前驱或后继节点。

前置 ++ 运算符: 找到当前节点的中序后继节点

Self operator++()
{
    if (_node->_right) // 如果当前节点的右子树不为空
    {
        // 寻找右子树中的最左节点
        Node* left = _node->_right;
        while (left->_left)
        {
            left = left->_left;
        }
        _node = left; // 迭代器指向该节点
    }
    else // 如果当前节点的右子树为空
    {
        // 寻找祖先节点中第一个不是其右子节点的节点
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right)
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent; // 迭代器指向该节点
    }
    return *this;
}

前置 -- 运算符: 找到当前节点的中序前驱节点

Self operator--()
{
    if (_node->_left) // 如果当前节点的左子树不为空
    {
        // 寻找左子树中的最右节点
        Node* right = _node->_left;
        while (right->_right)
        {
            right = right->_right;
        }
        _node = right; // 迭代器指向该节点
    }
    else // 如果当前节点的左子树为空
    {
        // 寻找祖先节点中第一个不是其左子节点的节点
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left)
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent; // 迭代器指向该节点
    }
    return *this;
}

4. 迭代器的 `begin` 和 `end` 方法

为了让红黑树支持范围遍历，我们需要实现 begin 和 end 方法。

begin 方法: 返回红黑树中最左节点的迭代器

iterator begin()
{
    Node* left = _root;
    while (left && left->_left)
    {
        left = left->_left;
    }
    return iterator(left);
}

end 方法: 返回一个指向空节点的迭代器。
```
iterator end()
{
    return iterator(nullptr);
}
```

三、map的模拟实现

1. `map` 的定义

// 模板类 map，用于存储键值对（K 为键类型，V 为值类型）
template<class K, class V>
class map
{
	// 内部辅助结构，用于从值键对中提取键（红黑树要求的 KeyOfValue 函数对象）
	struct MapKeyOfT
	{
		// 从键值对中返回键（pair 的 first 成员）
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};

public:
	// 定义迭代器类型（非 const），指向键值对
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
	// 定义常量迭代器类型，指向键值对
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;

	// 返回指向容器起始元素的常量迭代器
	const_iterator begin() const
		{
	return _t.Begin();
	}

	// 返回指向容器结束位置的常量迭代器
	const_iterator end() const
	{
		return _t.End();
	}

	// 返回指向容器起始元素的迭代器
	iterator begin()
	{
		return _t.Begin();
	}

	// 返回指向容器结束位置的迭代器
	iterator end()
	{
		return _t.End();
	}

	// 查找指定键值，返回对应键值对的迭代器（未找到则返回 end()）
	iterator find(const K& key)
		{
	return _t.Find(key);
	}

	// 插入键值对，返回 pair 包含：
	// - 迭代器指向插入位置（若键已存在则指向已有元素）
	// - bool 值表示是否新插入（true=新插入，false=键已存在）
	std::pair<iterator, bool> insert(const pair<K, V>& kv)
	{
		return _t.Insert(kv);
	}

	// 重载 [] 运算符，按键访问值：
	// - 若键存在，返回对应值的引用
	// - 若键不存在，插入默认构造的值并返回其引用
	V& operator[](const K& key)
	{
		// 插入键值对（值为默认构造的 V）
		std::pair<iterator, bool> ret = _t.Insert(std::make_pair(key, V()));
		// 返回值的引用
		return ret.first->second;
	}

private:
	// 内部使用红黑树存储键值对
	// 模板参数说明：
	// - K: 键类型（红黑树的键类型）
	// - pair<const K, V>: 存储的键值对类型（值类型）
	// - MapKeyOfT: 从存储的值中提取键的函数对象
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

2. `map` 的使用示例

map<string, int> m;
m.insert({ "苹果", 1 });
m.insert({ "香蕉", 1 });
m.insert({ "菠萝", 1 });
m.insert({ "香蕉", 3 });

for (auto& kv : m)
{
    cout << kv.first << ":" << kv.second << endl;
}

通过红黑树，map 的插入和查找操作的时间复杂度为 O(log n)。

四、set的模拟实现

1. `set` 的定义

template<class K>
class set
{
	// 内部辅助结构，用于从存储的数据中提取键值（set中键即为存储值本身）
	struct SetKeyOfT
	{
		// 返回传入的键值本身，符合RBTree对KeyOfValue的要求
		const K& operator()(const K& key) const
		{
			return key;
		}
	};

public:
	// 定义迭代器类型，基于红黑树的迭代器（非const版本）
	typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
	// 定义常量迭代器类型（const版本）
	typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

	// 返回指向容器起始元素的常量迭代器
	const_iterator begin() const
	{
		return _t.Begin();
	}

	// 返回指向容器结束位置的常量迭代器
	const_iterator end() const
	{
		return _t.Endt();
	}

	// 返回指向容器起始元素的迭代器
	iterator begin()
	{
		return _t.Begin();
	}

	// 返回指向容器结束位置的迭代器
	iterator end()
	{
		return _t.End();
	}

	// 查找指定键值，返回对应元素的迭代器（未找到则返回end()）
	iterator find(const K& key)
	{
		return _t.Find(key);
	}

	// 插入元素，返回pair包含：
	// - 插入位置的迭代器（若已存在则指向已有元素）
	// - bool值表示是否成功插入（true=新插入，false=已存在）
	std::pair<iterator, bool> insert(const K& key)
	{
		return _t.Insert(key);
	}

private:
	// 内部使用红黑树存储元素，模板参数说明：
	// - K: 存储的数据类型（即键类型）
	// - const K: 红黑树中存储的值类型（集合元素不可）
	// - SetKeyOfT: 从值中提取键的函数对象（此处键即值本身）
	RBTree<K, const K, SetKeyOfT> _t;
};

2. `set` 的使用示例

set<int> s;
s.insert(4);
s.insert(2);
s.insert(5);
s.insert(15);
s.insert(7);
s.insert(1);
s.insert(5);
s.insert(7);

for (auto e : s)
{
    cout << e << endl;
}

通过红黑树，set 的插入和查找操作的时间复杂度为 O(log n)。

五、红黑树代码

#pragma once
#include<vector>
#include <iostream>
using namespace std;

// 定义红黑树节点的颜色枚举
enum Colour
{
	RED,   // 红色
	BLACK  // 黑色
};

// 红黑树节点结构模板
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;   // 左子节点指针
	RBTreeNode<T>* _right;  // 右子节点指针
	RBTreeNode<T>* _parent; // 父节点指针

	T _data;   // 存储的数据
	Colour _col; // 节点颜色

	// 构造函数，初始化节点
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED) // 新节点默认为红色
	{}
};

// 红黑树迭代器结构模板
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node; // 节点类型
	typedef __RBTreeIterator<T, Ref, Ptr> Self; // 自引用类型
	Node* _node; // 当前节点指针

	// 构造函数，初始化迭代器指向的节点
	__RBTreeIterator(Node* node)
		:_node(node)
	{}

	// 解引用操作符，返回当前节点的数据引用
	Ref operator*()
	{
		return _node->_data;
	}

	// 成员访问操作符，返回当前节点数据的指针
	Ptr operator->()
	{
		return &_node->_data;
	}

	// 不等于操作符，比较两个迭代器是否指向不同节点
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	// 前缀递增操作符，用于迭代器遍历下一个元素
	Self& operator++()
	{
		if (_node->_right)
		{
			// 如果当前节点有右子树，找到右子树的最左节点
			Node* leftMin = _node->_right;
			while (leftMin->_left)
			{
				leftMin = leftMin->_left;
			}

			_node = leftMin;
		}
		else
		{
			// 如果没有右子树，向上查找直到找到一个节点是其父节点的左子节点
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
};

// 红黑树类模板
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node; // 节点类型

public:
	// 迭代器类型定义
	typedef __RBTreeIterator<T, T&, T*> Iterator;
	typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;

	RBTree() = default; // 默认构造函数

	// 拷贝构造函数，深拷贝树结构
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}

	// 赋值操作符，使用复制交换惯用法
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}

	// 析构函数，销毁树中所有节点
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}

	// 返回指向树起始元素的迭代器
	Iterator Begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left) // 查找最左节点
		{
			leftMin = leftMin->_left;
		}

		return Iterator(leftMin);
	}

	// 返回指向树起始元素的常量迭代器
	ConstIterator Begin() const
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return ConstIterator(leftMin);
	}

	// 返回指向树末尾的迭代器（空指针）
	Iterator End()
	{
		return Iterator(nullptr);
	}

	// 返回指向树末尾的常量迭代器（空指针）
	ConstIterator End() const
	{
		return ConstIterator(nullptr);
	}

	// 按键查找元素，返回找到的迭代器或末尾迭代器
	Iterator Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (KeyOfT()(cur->_data) < key)
			{
				cur = cur->_right; // 如果当前键小于目标键，向右查找
			}
			else if (KeyOfT()(cur->_data) > key)
			{
				cur = cur->_left; // 如果当前键大于目标键，向左查找
			}
			else
			{
				return Iterator(cur); // 找到匹配的节点
			}
		}

		return End(); // 未找到返回末尾迭代器
	}

	// 插入新元素到树中
	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			// 树为空，创建根节点
			_root = new Node(data);
			_root->_col = BLACK; // 根节点设为黑色
			return make_pair(Iterator(_root), true);
		}

		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		// 查找插入位置
		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
			{
				// 键已存在，返回迭代器和false
				return make_pair(Iterator(cur), false);
			}
		}

		// 创建新节点
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED; // 新节点设为红色
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur; // 插入到父节点右侧
		}
		else
		{
			parent->_left = cur; // 插入到父节点左侧
		}
		cur->_parent = parent;

		// 进行红黑树平衡调整
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 情况1：叔叔节点存在且为红色，进行颜色调整
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2和3：叔叔节点不存在或为黑色，进行旋转和颜色调整
				{
					if (cur == parent->_left)
					{
						// 情况2：新节点是父节点的左子节点，进行右旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						// 情况3：新节点是父节点的右子节点，进行左旋后右旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				// 情况1：叔叔节点存在且为红色，进行颜色调整
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2和3：叔叔节点不存在或为黑色，进行旋转和颜色调整
				{
					// 情况二：叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					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(Iterator(newnode), true);
	}

	// 右旋操作，用于树的平衡调整
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left; // 左子节点
		Node* subLR = subL->_right; // 左子节点的右子节点

		parent->_left = subLR; // 父节点的左子节点指向左子节点的右子节点
		if (subLR)
			subLR->_parent = parent; // 更新左子节点的右子节点的父指针

		subL->_right = parent; // 左子节点的右子节点指向父节点

		Node* ppNode = parent->_parent; // 父节点的父节点
		parent->_parent = subL; // 父节点的父指针更新为左子节点

		if (parent == _root) // 如果父节点是根节点
		{
			_root = subL; // 更新根节点为左子节点
			_root->_parent = nullptr; // 根节点无父节点
		}
		else
		{
			// 更新父节点的父节点的子节点指针
			if (ppNode->_right == parent)
			{
				ppNode->_right = subL;
			}
			else
			{
				ppNode->_left = subL;
			}
			subL->_parent = ppNode; // 更新左子节点的父指针
		}
	}

	// 左旋操作，用于树的平衡调整
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right; // 右子节点
		Node* subRL = subR->_left; // 右子节点的左子节点

		parent->_right = subRL; // 父节点的右子节点指向右子节点的左子节点
		if (subRL)
			subRL->_parent = parent; // 更新右子节点的左子节点的父指针

		subR->_left = parent; // 右子节点的左子节点指向父节点
		Node* ppNode = parent->_parent; // 父节点的父节点
		parent->_parent = subR; // 父节点的父指针更新为右子节点

		if (parent == _root) // 如果父节点是根节点
		{
			_root = subR; // 更新根节点为右子节点
			_root->_parent = nullptr; // 根节点无父节点
		}
		else
		{
			// 更新父节点的父节点的子节点指针
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode; // 更新右子节点的父指针
		}
	}

	// 中序遍历函数，用于调试输出
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	// 检查树是否满足红黑树性质
	bool IsBalance()
	{
		if (_root->_col == RED)
		{
			return false; // 根节点必须为黑色
		}

		int refNum = 0; // 记录黑色节点数量
		Node* cur = _root;
		// 沿最左路径计算黑色节点数量
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}

			cur = cur->_left;
		}

		// 检查所有路径的黑色节点数量是否相同，且无连续红色节点
		return Check(_root, 0, refNum);
	}

private:
	// 深拷贝树函数
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newroot = new Node(root->_data);
		newroot->_col = root->_col; // 拷贝颜色

		newroot->_left = Copy(root->_left); // 拷贝左子树
		if (newroot->_left)
			newroot->_left->_parent = newroot; // 更新左子节点的父指针

		newroot->_right = Copy(root->_right); // 拷贝右子树
		if (newroot->_right)
			newroot->_right->_parent = newroot; // 更新右子节点的父指针

		return newroot;
	}

	// 销毁树函数
	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left); // 递归销毁左子树
		Destroy(root->_right); // 递归销毁右子树
		delete root; // 删除当前节点
		root = nullptr;
	}

	// 检查树性质的辅助函数
	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 到达叶子节点（空节点），检查黑色节点数量是否符合预期
			if (refNum != blackNum)
			{
				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, refNum)
			&& Check(root->_right, blackNum, refNum);
	}

	// 中序遍历辅助函数
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left); // 遍历左子树
		cout << root->_data << endl; // 输出当前节点数据
		_InOrder(root->_right); // 遍历右子树
	}

private:
	Node* _root = nullptr; // 根节点指针
	//size_t _size = 0; // 树的大小（未使用）
};

STL详解 - 红黑树模拟实现map与set

一、改造红黑树

1. 模板参数

2. 节点的存储内容

3. 仿函数的设计

仿函数的作用

仿函数的实现

底层红黑树的处理方式

二、红黑树的迭代器

1. 迭代器的基本结构

2. 迭代器的操作

3. 迭代器的难点：++ 和 -- 运算符的重载

4. 迭代器的 `begin` 和 `end` 方法

三、map的模拟实现

1. `map` 的定义

2. `map` 的使用示例

四、set的模拟实现

1. `set` 的定义

2. `set` 的使用示例

五、红黑树代码

网站公告

今日签到

热门文章

最新发布