1. 红黑树规则红黑树最长分支≤最短分支2倍的树规则每个节点要么红要么黑根节点为黑若一个节点为红那么它接着的子节点为黑任意节点到所有的空节点均包含等量黑节点通过这四条规则即可实现最长分支≤最短分支2倍为什么 由于第四条规则因此极端情况下最短的路径由全黑构成最长的路径由一半黑一半红构成因为红后面必须接黑每条路径黑节点数相等因此最长分支≤最短分支2倍所以第3条规则控制最短的分支第4条规则控制最长的分支2. 实现1. 枚举红色和黑色代码语言javascriptAI代码解释enum color { red, black };2. 树节点比AVL树多一个颜色变量代码语言javascriptAI代码解释templateclass K, class V struct rbtreenode { std::pairK, V _kv; rbtreenode* _left; rbtreenode* _right; rbtreenode* _par; color _col; rbtreenode(const std::pairK,V kv) : _kv(kv) , _left(nullptr) , _right(nullptr) , _par(nullptr) { } };3. 插入如果插入黑色节点那么树必定会不符合红黑树规则 由于原先每条路径的黑节点数量都是一样的插入黑节点就意味着一定会有一条路的黑节点不一样 因此插入统一插红节点父节点为黑可以直接结束符合红黑树父节点为红由于规定红节点后必须为黑节点因此需要变换 由于父节点为红那么爷节点为黑叔节点可能为红也可能为黑代码语言javascriptAI代码解释bool insert(const std::pairK, 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. 变换首先虽然图上面我们默认当前节点时左叶子节点但实际上左右都有可能因此我们要写两套逻辑代码语言javascriptAI代码解释while (par par-_col red) { node* grand par-_par; if (par grand-_left) { // 左子树情况 } else { // 右子树情况 } }下面我们讲的时候都默认第一套逻辑即为左节点par grand-_left1. 变色叔节点为红将爷节点变为红色父节点和叔节点变为黑色 如果爷节点的父节点为红色那么就继续往上更新再继续分类讨论代码语言javascriptAI代码解释node* uncle par-_right; if (uncle uncle-_col red) { par-_col black; uncle-_col black; cur grand; par cur-_par; }2. 旋转没有叔节点或叔节点为黑两个的共同点插入节点后仅仅通过变色不能维持平衡 旋转方式与AVL树类似按照要调整的节点与已有节点方向是否相同分为单旋双旋2.1 单旋叔节点不存在此时只需要转父节点再将两个节点变红叔节点为黑此时先确定颜色爷节点为黑这种情况在x插入之前也是不符合红黑树规则的因此不存在爷为红节点此时本来就可以平衡因此这种叔节点为黑的情况不会出现在插入新节点时只会存在于向上调整节点时真实情况 爷节点为黑父节点为红叔节点为黑当前节点为黑 看似是平衡的但是定量分析就出现破绽了 设父节点的子树的黑节点高度为h 那么4个子树在原来平衡时黑节点高度分别为hh1hh 但是当前由于调整上来的因此当前节点的子树黑高度加了1 因此这种情况需要旋转不是局部高度的问题而是子树的黑节点多了一个处理方法 和前面一样可以直接用AVL树的旋转变色方法最后爷节点变为黑色父和叔节点变为红色即可2.2 双旋原理和AVL树一模一样逻辑代码语言javascriptAI代码解释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树代码语言javascriptAI代码解释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.取出根节点