RBTree(红黑树)--C++-创新互联
红黑树是满足下面性质的二叉搜索树
专业从事网站设计、成都网站制作,高端网站制作设计,小程序开发,网站推广的成都做网站的公司。优秀技术团队竭力真诚服务,采用H5响应式网站+CSS3前端渲染技术,成都响应式网站建设公司,让网站在手机、平板、PC、微信下都能呈现。建站过程建立专项小组,与您实时在线互动,随时提供解决方案,畅聊想法和感受。1. 每个节点,不是红色就是黑色的
2. 根节点是黑色的
3. 如果一个节点是红色的,则它的两个子节点是黑色的
4. 对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。
#pragma once enum Color{ RED, BLACK }; templatestruct RBtreeNode { RBtreeNode(const K& key, const V& v, Color col = RED) :_left(NULL) , _right(NULL) , _parent(NULL) , _key(key) , _vlaue(v) , _col(col) {} RBtreeNode * _left; RBtreeNode * _right; RBtreeNode * _parent; K _key; V _vlaue; Color _col; }; template class RBtree { typedef RBtreeNode Node; public: RBtree() :_root(NULL) {} bool Insert(const K& key, const V& v) { if (_root == NULL) { _root = new Node(key, v, BLACK); return true; } Node* parent = NULL; Node* cur = _root; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(key, v, RED); if (key < parent->_key) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } //调色 while (cur != _root && parent->_col == RED) { Node* GrandParent = parent->_parent; if (parent == GrandParent->_left)//往左子树插 { Node* uncle = GrandParent->_right; if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; GrandParent->_col = RED; cur = GrandParent; parent = cur->_parent; } else { if (cur == parent->_right) { _RotateL(parent); swap(cur, parent); } _RotateR(GrandParent); parent->_col = BLACK; GrandParent->_col = RED; } } else//往右子树插 { Node*uncle = GrandParent->_left; if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; GrandParent->_col = RED; cur = GrandParent; parent = cur->_parent; } else { if (cur == parent->_left) { _RotateR(parent); swap(cur, parent); } _RotateL(GrandParent); parent->_col = BLACK; GrandParent->_col = RED; } } } _root->_col = BLACK; return true; } bool IsBalanceTree() { return _IsBalance(_root); } void InOrder() { _InOrder(_root); cout << endl; } protected: int _Height(Node* root) { if (root == NULL) { return 0; } int left = _Height(root->_left) + 1; int right = _Height(root->_right) + 1; return (left > right) ? left : right; } bool _IsBalance(Node* root) { if (root == NULL) { return true; } int left = _Height(root->_left); int right = _Height(root->_right); int bf = abs(left - right); if (bf > 1) { return false; } return _IsBalance(root->_left) && _IsBalance(root->_right); } void _RotateL(Node* parent) { Node *subR = parent->_right; Node *subRL = subR->_left; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } subR->_left = parent; subR->_parent = parent->_parent; parent->_parent = subR; parent = subR; //连爸爸:) if (parent->_parent == NULL) { _root = parent; } else { if (parent->_parent->_key < parent->_key) { parent->_parent->_right = parent; } else { parent->_parent->_left = parent; } } } void _RotateR(Node* parent) { Node *subL = parent->_left; Node *subLR = subL->_right; parent->_left = subLR; if (subLR != NULL) { subLR->_parent = parent; } subL->_right = parent; subL->_parent = parent->_parent; parent->_parent = subL; parent = subL; if (parent->_parent == NULL) { _root = parent; } else { if (parent->_parent->_key < parent->_key) { parent->_parent->_right = parent; } else { parent->_parent->_left = parent; } } } void _InOrder(Node*& root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } protected: Node* _root; }; void TestRBTree1() { RBtree t1; int a[10] = { 5, 2, 9, 6, 7, 3, 4, 0, 1, 8 }; for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i) { t1.Insert(a[i], i); t1.InOrder(); } cout << "IsBalanceTree ? "<< t1.IsBalanceTree() << endl; }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前文章:RBTree(红黑树)--C++-创新互联
分享网址:http://pwwzsj.com/article/ijipi.html