红黑树的验证
bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED)//检查根节点是否为黑 { cout << "根节点不是黑色" << endl; return false; } // 黑色节点数量基准值 int benchmark = 0; return PrevCheck(_root, 0, benchmark); }
返回值函数PrevCheck的实现
bool PrevCheck(Node* root, int blackNum, int& benchmark) { if (root == nullptr) { if (benchmark == 0) { benchmark = blackNum; return true; } if (blackNum != benchmark) { cout << "某条黑色节点的数量不相等" << endl; return false; } else { return true; } } if (root->_col == BLACK) { ++blackNum; } if (root->_col == RED && root->_parent->_col == RED) { cout << "存在连续的红色节点" << endl; return false; } return PrevCheck(root->_left, blackNum, benchmark) && PrevCheck(root->_right, blackNum, benchmark); }
- 黑高度相同性质检查：函数使用递归方式遍历树中的节点，并维护一个
blackNum变量，用于跟踪从根节点到当前节点经过的黑色节点数。在遍历过程中，它会检查每条从根到叶子节点的路径上的黑色节点数是否相同。如果路径上的黑色节点数不相同，说明违反了红黑树的性质。 - 连续红色节点检查：在遍历的过程中，代码还检查是否存在连续的红色节点。在红黑树中，不允许存在相邻的两个红色节点。如果存在连续的红色节点，也违反了红黑树的性质。
- 返回值：函数返回一个布尔值，用于指示红黑树是否满足性质。如果在遍历过程中发现任何性质被破坏，函数将返回
false，否则返回true。
这个函数是用于验证红黑树的一种常见方法，用于检查树是否保持了红黑树的性质，包括黑高度相同和不连续的红色节点。如果该函数返回 true，则表示树是一个有效的红黑树，否则表示树的结构违反了红黑树的性质。
红黑树的遍历输出和左旋右旋
1. 遍历输出
void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); }
这里的遍历是一种按照节点值的大小顺序遍历二叉搜索树（BST）的方法。在这里，红黑树也是一种BST，因此中序遍历可以用来按键的顺序输出树中的节点。
函数的主要逻辑包括：
- 如果输入的
root节点为空（即树为空），则直接返回，不执行任何操作。 - 否则，函数会递归地执行以下操作：
- 先递归调用
_InOrder函数来遍历左子树（左子节点）。 - 输出当前节点的键值对（这里假设键是整数，值是整数，根据需要调整输出格式）。
- 最后递归调用
_InOrder函数来遍历右子树（右子节点）。
2. 左单旋
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } }
- 首先，将
parent节点的右子节点subR和subR的左子节点subRL分别保存起来。subR将会成为新的根节点，而subRL将成为parent节点的右子节点。 - 接下来，将
parent节点的右子节点指针_right指向subRL，同时确保subRL的父指针_parent指向parent。这一步是将subRL与parent连接起来。 - 将
parent节点的父节点指针ppNode保存起来。这是为了在旋转后更新ppNode的左子节点或右子节点指向subR，以确保树的连接正确。 - 将
subR的左子节点指针_left指向parent，同时将parent的父节点指针_parent指向subR。这一步是将parent旋转到subR的位置上。 - 接下来，处理根节点的情况。如果
_root指向parent，那么现在_root应该指向subR，因此将_root更新为subR，并将subR的父指针设置为nullptr。 - 如果
_root不指向parent，则需要根据ppNode的情况来更新ppNode的左子节点或右子节点指向subR，以确保整棵树的连接正确。
左单旋和右单旋和我们之前的AVL树实现基本一致，若不能理解请看上一篇文章
3. 右单旋
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } Node* ppNode = parent->_parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } }
- 首先，将
parent节点的左子节点subL和subL的右子节点subLR分别保存起来。subL将会成为新的根节点，而subLR将成为parent节点的左子节点。 - 接下来，将
parent节点的左子节点指针_left指向subLR，同时确保subLR的父指针_parent指向parent。这一步是将subLR与parent连接起来。 - 将
parent节点的父节点指针ppNode保存起来。这是为了在旋转后更新ppNode的左子节点或右子节点指向subL，以确保树的连接正确。 - 将
subL的右子节点指针_right指向parent，同时将parent的父节点指针_parent指向subL。这一步是将parent旋转到subL的位置上。 - 接下来，处理根节点的情况。如果
_root指向parent，那么现在_root应该指向subL，因此将_root更新为subL，并将subL的父指针设置为nullptr。 - 如果
_root不指向parent，则需要根据ppNode的情况来更新ppNode的左子节点或右子节点指向subL，以确保整棵树的连接正确。
红黑树模拟实现全部代码
#pragma once #include<iostream> #include<assert.h> #include<time.h> using namespace std; enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) {} }; template<class K, class V> struct RBTree { typedef RBTreeNode<K,V> Node; public: 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; if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfater = parent->_parent; assert(grandfater); assert(grandfater->_col == BLACK); if (parent == grandfater->_left) { Node* uncle = grandfater->_right; // 情况一 : uncle存在且为红，变色+继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 继续往上处理 cur = grandfater; parent = cur->_parent; }// 情况二+三：uncle不存在 + 存在且为黑 else { // 情况二：右单旋+变色 if (cur == parent->_left) { RotateR(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情况三：左右单旋+变色 RotateL(parent); RotateR(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } else // (parent == grandfater->_right) { Node* uncle = grandfater->_left; // 情况一 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 继续往上处理 cur = grandfater; parent = cur->_parent; } else { // 情况二：左单旋+变色 if (cur == parent->_right) { RotateL(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情况三：右左单旋+变色 RotateR(parent); RotateL(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } } _root->_col = BLACK; return true; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED) { cout << "根节点不是黑色" << endl; return false; } // 黑色节点数量基准值 int benchmark = 0; return PrevCheck(_root, 0, benchmark); } private: bool PrevCheck(Node* root, int blackNum, int& benchmark) { if (root == nullptr) { if (benchmark == 0) { benchmark = blackNum; return true; } if (blackNum != benchmark) { cout << "某条黑色节点的数量不相等" << endl; return false; } else { return true; } } if (root->_col == BLACK) { ++blackNum; } if (root->_col == RED && root->_parent->_col == RED) { cout << "存在连续的红色节点" << endl; return false; } return PrevCheck(root->_left, blackNum, benchmark) && PrevCheck(root->_right, blackNum, benchmark); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } Node* ppNode = parent->_parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } } private: Node* _root = nullptr; };
红黑树的应用
红黑树是一种自平衡的二叉搜索树，由于其平衡性和高效性能，广泛用于各种计算机科学和软件工程领域。以下是一些红黑树的常见应用：
- C++ STL中的
std::map和std::set：C++标准模板库（STL）中的std::map和std::set通常使用红黑树实现。它们用于实现有序的关联容器，其中键值对被自动排序并保持平衡，以支持高效的查找、插入和删除操作。 - 数据库系统：红黑树常用于数据库系统中的索引结构，如B+树的实现中。数据库中的索引需要高效地支持查找、范围查询和排序等操作，而红黑树是一种性能良好的选择。
- 操作系统：红黑树在操作系统中用于进程调度、虚拟内存管理和文件系统的实现。在这些场景中，需要高效的数据结构来管理和操作各种系统资源。
- 网络路由表：红黑树被广泛用于路由表的实现，以支持网络路由器和交换机等网络设备的高效路由查找。
- 编译器：编译器可以使用红黑树来管理符号表，以便进行语法分析、类型检查和代码生成。
- 计算机图形学：在计算机图形学中，红黑树可用于空间分割数据结构，如八叉树和四叉树的实现，以支持高效的图形渲染和碰撞检测。
- 高性能库和框架：红黑树常被用作高性能库和框架中的核心数据结构，以提供高效的数据管理和操作功能。
- 实时系统：实时系统需要高效的数据结构来管理任务和事件，红黑树可以用于实现定时器和调度器。
总的来说，红黑树是一种多功能的数据结构，适用于需要高效的自平衡二叉搜索树的任何领域，特别是需要高效的插入、删除和查找操作的场景。其平衡性和性能使其成为各种应用中的重要工具。
红黑树与AVL树的比较
红黑树（Red-Black Tree）和AVL树（Adelson-Velsky and Landis Tree）都是自平衡二叉搜索树，它们在维护平衡性和支持高效的插入、删除和查找操作方面有很多相似之处，但也有一些关键的区别。以下是红黑树和AVL树之间的比较：
- 平衡性要求：
- 红黑树：红黑树放宽了平衡性要求，它保证了树的高度最多是其2倍。
- AVL树：AVL树要求更为严格，它保证树的高度差不超过1，因此AVL树的平衡性更强。
- 性能：
- 红黑树：由于平衡性要求相对较低，插入和删除操作在平均情况下可能比AVL树更快，因此在那些需要频繁插入和删除操作的场景中，红黑树可能更适合。
- AVL树：AVL树在查找操作上可能稍微快一些，因为它的平衡性更严格，但它的插入和删除操作可能更慢，因为它需要更频繁地执行旋转操作来保持平衡。
- 旋转操作：
- 红黑树：红黑树的旋转操作相对较少，因为它放宽了平衡性要求。通常，红黑树的旋转操作较少，但需要更多的颜色变换操作来保持平衡。
- AVL树：AVL树的旋转操作更频繁，因为它要求更严格的平衡性。这可能导致在插入和删除操作中执行更多的旋转。
- 内存消耗：
- 红黑树：由于红黑树的平衡性要求较低，通常会消耗更少的内存，因为不需要额外的平衡因子来跟踪节点的高度差。
- AVL树：AVL树需要为每个节点存储平衡因子，这可能会导致更多的内存消耗。
- 应用场景：
- 红黑树：适用于需要高效的插入和删除操作，而对查找操作的性能要求相对较低的场景，如C++的STL中的
std::map和std::set。 - AVL树：适用于对查找操作有更高性能要求的场景，但可以容忍较慢的插入和删除操作的情况，如数据库索引。
总的来说，选择使用红黑树还是AVL树取决于应用的需求和性能要求，在C++的map和set的实现中，底层调用的就是红黑树，但在实际的面试和工作中，红黑树的应用可能更为广泛。
