红黑树insert笔记

贴的代码还是有点“小问题”，比如insert里的比较是直接和kv比较，用pair的内置比较，即用到了key，也用到了value，这是不合“红黑树key，value逻辑”的，总之就这样了，能用就行。

ps：博主在写insert的时候，vs2022也是狂出毛病，然后博主调试分析不出错误，问豆包也是一本正经的胡说八道。。。。。。

贴个代码水一下

R_B_T.hpp

#pragma once
#include <iostream>
#include <set>// 枚举值表示颜色
enum Colour
{RED,BLACK
};
// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针std::pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const std::pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const std::pair<K, V>& kv) {if (!_root) {_root = new Node(kv);_root->_col = BLACK;return true;}// 先找到要插入的位置Node* pcur = _root, * pPrev = nullptr;while (pcur) {pPrev = pcur;if (kv < pcur->_kv) {pcur = pcur->_left;}else if (kv > pcur->_kv) {pcur = pcur->_right;}else {return false;}}// 插入pcur = new Node(kv);pcur->_col = RED;if (kv < pPrev->_kv) {pPrev->_left = pcur;}else {pPrev->_right = pcur;}pcur->_parent = pPrev;// 向上检查更新，pcur仍是新插入结点，而pPrev是pcur的父结点while (pPrev != nullptr) {//直接合格if (pPrev->_col == BLACK) {break;}else {// 分1，2，3，4种情况，每种情况又有uncle结点为红/空与黑的区别// cur(son), pPrev(father), grandfatherNode* pGF = pPrev->_parent; // grandfatherif (pPrev == pGF->_left) {// uncle为红if (pGF->_right != nullptr && pGF->_right->_col == RED) {pGF->_col = RED;pGF->_right->_col = pPrev->_col = BLACK;// 更新， pGF不改变pcur = pGF;pPrev = pcur->_parent;}// uncle为黑或空的旋转else {// 两种情况，cur(son), pPrev(father), grandfather为左右左/左左左if (pcur == pPrev->_left) {RotateR(pGF);// pGF改变pcur = pPrev;pPrev = pcur->_parent;}else {RotateLR(pGF);pcur = pcur;pcur = pcur->_parent;}}}else {if (pGF->_left != nullptr && pGF->_left->_col == RED) {pGF->_col = RED;pGF->_left->_col = pPrev->_col = BLACK;// 更新， pGF不改变pcur = pGF;pPrev = pcur->_parent;}else {if (pcur == pPrev->_left) {RotateRL(pGF);// 旋转里考虑了pGF为_root的情况并进行了处理pcur = pcur;pPrev = pcur->_parent;}else {RotateL(pGF);pcur = pPrev;pPrev = pcur->_parent;}}}}// 无脑一点，uncle为红的时候pGF可能为_root，uncle为黑或null的时候左旋右旋处理了// 就顺便的放这里了，放uncle为红那里可能会更好_root->_col = BLACK;}return true;}void InOrder() {_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_kv.first << " ";_InOrder(root->_right);}// 前序递归遍历bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历走到空时，意味着一条路径走完了//cout << blackNum << endl;if (refNum != blackNum){std::cout << "存在黑色结点的数量不相等的路径" << std::endl;return false;}return true;}// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了if (root->_col == RED && root->_parent && root->_parent->_col == RED){std::cout << root->_kv.first << "存在连续的红色结点" << std::endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}bool IsBalanceTree(){if (_root == nullptr)return true;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:void RotateR(Node* pcur) { //复用，这里是连续两个红结点的父结点if (!pcur) return;Node* pPL = pcur->_left;if (pcur->_parent) {if (pcur->_parent->_right == pcur) {pcur->_parent->_right = pPL;}else if (pcur->_parent->_left == pcur) {pcur->_parent->_left = pPL;}}// 利用根节点的父节点是nullptr判断了pcur是否是根节点else {_root = pPL;}pPL->_parent = pcur->_parent;pcur->_left = pPL->_right;if (pPL->_right)pPL->_right->_parent = pcur;pPL->_right = pcur;pcur->_parent = pPL;// bf// pcur->_bf = pPL->_bf = 0;// _colpPL->_col = BLACK;pcur->_col = RED;}// 左单旋void RotateL(Node* pcur) { //pParent  if (!pcur) return;Node* pPR = pcur->_right;if (pcur->_parent) {if (pcur->_parent->_right == pcur) {pcur->_parent->_right = pPR;}else if (pcur->_parent->_left == pcur) {pcur->_parent->_left = pPR;}}else {_root = pPR;}pPR->_parent = pcur->_parent;pcur->_right = pPR->_left;if (pPR->_left)pPR->_left->_parent = pcur;pPR->_left = pcur;pcur->_parent = pPR;// bf// pcur->_bf = pPR->_bf = 0;pPR->_col = BLACK;pcur->_col = RED;}// 右左双旋, 先右再左void RotateRL(Node* pParent) {Node* pPR = pParent->_right;Node* pPRL = pPR->_left;RotateR(pParent->_right);RotateL(pParent);}// 左右双旋void RotateLR(Node* pParent) {Node* pPL = pParent->_left;Node* pPLR = pPL->_right;RotateL(pParent->_left);RotateR(pParent);}
private:Node* _root = nullptr;
};

main.cpp(简单的测试代码)

#include "Red_Black_Tree.hpp"void test() {RBTree<int, int> rbt;// 插入一些键值对rbt.Insert(std::make_pair(10, 10));rbt.Insert(std::make_pair(20, 20));rbt.Insert(std::make_pair(30, 30));rbt.Insert(std::make_pair(15, 15));rbt.Insert(std::make_pair(25, 25));// 中序遍历std::cout << "中序遍历结果: ";rbt.InOrder();std::cout << std::endl;// 检查红黑树的平衡性if (rbt.IsBalanceTree()) {std::cout << "红黑树是平衡的。" << std::endl;}else {std::cout << "红黑树不是平衡的。" << std::endl;}
}
int main() {test();return 0;
}