重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
红黑树是满足下面性质的二叉搜索树
创新互联公司是一家专注于成都做网站、成都网站建设与策划设计,宜秀网站建设哪家好?创新互联公司做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:宜秀等地区。宜秀做网站价格咨询:18982081108
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; }