封装map和set所需第二步：红黑树

1.红黑树的规则1.每个结点只有黑或红色2.根结点只为黑色3.红节点的两孩子只为黑色4.所有节点的绝对路径的黑色节点数都相同绝对路径从根节点到每一个子节点的过程2.红黑树的一些特点1.设每一条路径有x个黑色结点有最短路径为x,最长路径为x*2。下图为最长下图为最短设N为该树的所有节点数x为最短路径有2^x-1 N2^(x1)-1.即nlogN.可得一次查找的效率还是为O(logN).下面开始代码实现1.结点和大框//枚举封装颜色 enum { RED, BLACK }; templateclass K, class V struct RBTreeNode { RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; pairK, V _val; int _col; RBTree(const pairK, V val) :_val(val) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) //结点颜色优先为红色 //因为违反条件4的代价很大 ,_col(RED) { } }; templateclass K, class V class RBTree { public: typedef RBTreeNodeK, V Node; private: Node* _root nullptr; };2.出现矛盾时的修改如上图出现矛盾时我们将新插的节点为cur,其父亲为parent,父亲的父亲为grandparent,grandparent的另一个孩子为uncle。当cur与parent的颜色出现矛盾时grandparent的颜色一定为黑色此时uncle的颜色就极为重要。1.uncle为红色解法cur可能是新节点也可能是从下面更新出来的这些情况下只需将parent和uncle更新为black,grandparent更新为red。然后将cur去到grandparent处向上更新即可。可能grandparent为红后与其的祖父又发生了矛盾代码说白了红黑树与AVL树的差别只有insert是不同的bool insert(const pairK, V val) { if (_root nullptr) { _root new Node(val); _root-_col BLACK; return true; } Node* cur _root; Node* parent nullptr; while (cur) { if (cur-_val.first val.first) { parent cur; cur cur-_right; } else if (cur-_val.first val.first) { parent cur; cur cur-_left; } else { return false; } } //此处走到空结点 cur new Node(val); //连接parent和cur if (parent-_val.first val.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; //parentnulptr代表走到_root了 while (parent parent-_col RED) { Node* grandparent parent-_parent; //这里核心是用于限定uncle在grandparent的左还是右的 if (grandparent-_left parent) { Node* uncle grandparent-_right; //unclenullptr为其它情况 if (uncle uncle-_col RED) { uncle-_col parent-_col BLACK; grandparent-_col RED; cur grandparent; parent grandparent-_parent; } else { if (parent-_left cur) { rotateR(grandparent); parent-_col BLACK; grandparent-_col RED; } else { rotateL(parent); rotateR(grandparent); cur-_col BLACK; grandparent-_col RED; } //修改完后就要break了不要再往上走了 break; } } else { Node* uncle grandparent-_left; //unclenullptr为其它情况 if (uncle uncle-_col RED) { uncle-_col parent-_col BLACK; grandparent-_col RED; cur grandparent; parent grandparent-_parent; } else { if (parent-_left cur) { rotateR(parent); rotateL(grandparent); cur-_col BLACK; grandparent-_col RED; } else { rotateL(grandparent); parent-_col BLACK; grandparent-_col RED; } break; } } } _root-_col BLACK; return true; }2.uncle为黑或uncle为空1.uncle为空此时cur一定为新插入结点不然左边一定有别的黑节点使黑节点数两边不相等。2.uncle为黑此时cur一定不为新插入结点不然左子树一定比右子树少至少一个黑节点。二者本质是一样的只有旋转才能解决此时又分两种情况。1.cur在parent的左子树,右单旋以grandparent为旋转点单右旋然后将grandparent改为红色parent改为黑色。2.cur在parent的右子树,左右双旋先以parent为旋转点单左旋,再以grandparent为旋转点单右旋grandparent改为红色,cur改为黑色.代码while (parent parent-_col RED) { Node* grandparent parent-_parent; //这里核心是用于限定uncle在grandparent的左还是右的 //此处uncle为右 if (grandparent-_left father) { Node* uncle grandparent-_right; //unclenullptr为其它情况 if (uncleuncle-_col RED) { uncle-_col parent-_col BLACK; grandparent-_col RED; cur grandparent; parent grandparent-_parent; } else if (parent-_left cur) { rotateR(grandparent); parent-_col BLACK; grandparent-_col RED; } else { rotateL(parent); rotateR(grandparent); cur-_col BLACK; grandparent-_col RED; } } //此处uncle为左 else { Node* uncle grandparent-_laft; //unclenullptr为其它情况 if (uncle uncle-_col RED) { uncle-_col parent-_col BLACK; grandparent-_col RED; cur grandparent; parent grandparent-_parent; } else if (parent-_left cur) { rotateR(parent); rotateL(grandparent); cur-_col BLACK; grandparent-_col RED; } else { rotateL(parent); parent-_col BLACK; grandparent-_col RED; } }3.检查是否为红黑树1.用孩子找是否与父亲都为红色2.计算每一条路径的黑色结点是否都相同bool isRBtree() { if (_root nullptr) return true; if (_root-_col RED) return false; Node* cur _root; int realheight 0; while (cur) { if (cur-_col BLACK)realheight; //随便找一条路径的黑色节点数即可 cur cur-_left; } return _isRBtree(_root, 0, realheight); } private: //num是形参找每一条的黑色结点个数realnum是外部传的一个一条路径的黑色节点数 bool _isRBtree(Node* _root, int num, const int realnum) { //说明遍历到头了 if (_root nullptr) { if (num ! realnum) { cout not real number endl; return false; } return true; } if (_root-_col BLACK) num; if (_root-_col RED _root-_parent-_col RED) { cout contrast colour endl; return false; } return _isRBtree(_root-_left, num, realnum) _isRBtree(_root-_right, num, realnum); }总结两次出的问题都在于在更新完后没有及时的break因此要注意在调整更新后要及时地break,部分情况除外。