莱芜摩托车网站网站做扫一扫

莱芜摩托车网站,网站做扫一扫,十大装修公司排名哪家最好,舆情网站入口网址大全名字双旋:8左边分给6右边#xff0c;8右边给10左边#xff0c;8作为根。这样才能单旋这种不行#xff0c;这还分单旋双旋问题#xff0c;单旋情况#xff0c;g变成黑#xff0c;不需要往上处理#xff0c;黑色上面红黑都行直接break#xff1b;else 就是复刻一下#xff0…双旋:8左边分给6右边8右边给10左边8作为根。这样才能单旋这种不行这还分单旋双旋问题单旋情况g变成黑不需要往上处理黑色上面红黑都行直接breakelse 就是复刻一下换一下方向。模版是类型的复用继承是实现的复用逻辑类似类型不同搞成模版实现继承设置基类派生类继承。#pragma once enum Colour { RED, BLACK }; templateclass K, class V struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 pairK, V _kv; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; Colour _col; RBTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} }; templateclass K, class V class RBTree { typedef RBTreeNodeK, V Node; public: bool Insert(const pairK, 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* grandfather parent-_parent; if (parent grandfather-_left) { // g // p u Node* uncle grandfather-_right; if (uncle uncle-_col RED) { // 变色 parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else { if (cur parent-_left) { // g // p u // c RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } else { // g // p u // c RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } else { // g // u p Node* uncle grandfather-_left; // 叔叔存在且为红-》变色即可 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else // 叔叔不存在或者存在且为黑 { // 情况二叔叔不存在或者存在且为黑 // 旋转变色 // g // u p // c if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_col BLACK; return true; } void RotateR(Node * parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* pParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (pParent-_left parent) { pParent-_left subL; } else { pParent-_right subL; } subL-_parent pParent; } } void RotateL(Node * parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parentParent nullptr) { _root subR; subR-_parent nullptr; } else { if (parent parentParent-_left) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } } void InOrder() { _InOrder(_root); cout 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 IsBalance() { 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: bool Check(Node* root, int blackNum, const int refNum) { if (root nullptr) { // 前序遍历走到空时意味着一条路径走完了 //cout blackNum endl; if (refNum ! blackNum) { cout 存在黑色结点的数量不相等的路径 endl; return false; } return true; } // 检查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲就方便多了 if (root-_col RED root-_parent-_col RED) { cout root-_kv.first 存在连续的红色结点 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-_kv.first : root-_kv.second 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; } private: Node* _root nullptr; };#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream using namespace std; #includeRBTree.h void TestRBTree1() { RBTreeint, int t; // 常规的测试用例 //int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 特殊的带有双旋场景的测试用例 int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { t.Insert({ e, e }); } t.InOrder(); cout t.IsBalance() endl; } int main() { TestRBTree1(); return 0; }基本编过了怎么判平衡第一点不用检查用的枚举第二点直接检查就行第三点第四点怎么检查检查孩子要检查两个还不一定存在我检查父亲就很方便父亲一定存在。跟是黑色形参下一层 不影响上一层怎么比较路径方式一给个容器遍历容器比较每个值或者跟个基准值进行比较跟某一条路径进行比较