红黑树原理以及红黑树旋转和变色

一.红黑树规则

1. 每个节点要么是红色，要么是黑色
2. 根节点始终为黑色
3. 红色节点的子节点必须都是黑色（即不允许出现连续的红色节点）
4. 从任意节点到其所有空子节点的路径上，包含的黑色节点数量相同

二.红黑树效率

由于红黑树的性质，假设红黑树存在最长路径于最短路径，最长路径最大就是最短路径的2倍

所以N个节点的红黑树 节点数量 N 满足不等式：2^h - 1 ≤ N < 2^(h+1) - 1 h是最短路径长度

也就意味着时间复杂度是logN

三.红黑树结构

插入新节点

while(parent&&parent->_col==RED){ Node*grandfather=parent->_parent; if(grandfather->_left==parent){ //说明uncle在右边 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){ RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; //与父节点偏向相同只需要右旋 } else{ RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;//先左旋后右旋 } break; } } else{ Node*uncle=grandfather->_left; if(uncle&&uncle->_col==RED){ parent->_col=uncle->_col=BLACK; grandfather->_col=RED; cur=grandfather; parent=cur->_parent; } else{ if(cur==parent->_right){ RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; //与父节点偏向相同只需要左旋 } else{ RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;//先右旋后左旋 } break; } } }

情况一:当叔叔节点存在且是红色时

此时不需要旋转只需要将父节点和叔叔节点变成黑色即可，再将父节点的父节点变成红色向上继续调整

情况二:当叔叔节点不存在或存在且为黑色时

此时需要旋转，旋转逻辑分为两种单旋或是双旋。

如果此时插入的新节点在祖父节点的左树且是父节点的左侧，说明结构偏向一边只需要向右单旋即可，如果插入在祖父左侧却在父节点右侧，则需要左旋后右旋。反之一样。

旋转代码

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; } }