郑州郑州网站建设河南做网站公司,阜阳网站设计,河北建设网站公司,wordpress搭建ppt目录
一、红黑树概念 二、红黑树节点结构设计
三、插入操作 处理情况1 处理情况2
处理情况3 插入总结#xff1a; 四、插入操作源码
五、红黑树验证 一、红黑树概念 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0…目录
一、红黑树概念 二、红黑树节点结构设计
三、插入操作 处理情况1 处理情况2
处理情况3 插入总结 四、插入操作源码
五、红黑树验证 一、红黑树概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍由规则二三四来保证因而是接近平衡的。因为最长路径为一黑一红最短路径为全黑。 红黑树还必须满足以下规则 1. 每个结点不是红色就是黑色非红即黑 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的没有连续的红色 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每条路径上黑色节点的数量相等从这一规则也可以得出在插入一新节点时该节点必须为红才会满足该条件 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点 规则四演示 二、红黑树节点结构设计 因为红黑树节点非红即黑所以可以用枚举的思想来例举红节点和黑节点。因为在插入的过程中可能会存在翻转的情况所以就需要一个节点的父节点_parent,左孩子_left,右孩子_right。
enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{ RBTreeNodeK, V* _left; // 左孩子RBTreeNodeK, V* _right; // 右孩子RBTreeNodeK, V* _parent; // 红黑树需要旋转为了实现简单给出该字段pairK, V _kv; //值域Colour _col; //颜色RBTreeNode(const pairK, V kv) //初始化:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}
};
三、插入操作
根据规则4可以得出在插入一个新节点的时候这个节点一定是为红色的上已证。在插入红色节点的时候可能还是会造成红红节点的冲突违反规则3所以我们还需要进行变色旋转的处理方法 在插入新节点后因为新节点的默认颜色是红色因此如果其父亲节点的颜色是黑色没有违反红黑树任何规则则不需要调整但当新插入节点的父亲节点颜色为红色时就违反了规则3不能有连在一起的红色节点此时需要对红黑树分情况来讨论为方便我们进行变色和旋转的处理我们定义父亲节点为p叔叔节点为u祖父节点为g当前节点为cur新增。实际上根据红黑树的规则我们可以确定要发生变色或旋转操作时cur、p、g节点一定是红、红、黑如果不满足这种情况那么肯定这颗红黑树在次之前就违背的红黑树的规则。所以变化操作主要取决于叔叔节点u的颜色。如下抽象图表示s/b/c/de代表的是满足规则的子树。 处理情况1 cur为红p为红g为黑u存在且为红 处理方法叔叔u和父亲p变黑祖父g变红,再往上进行处理如果g是根节点需要把g再变黑因为根节点必须是黑规则2。再往上处理的过程中因为会存在当前g的父节点为红的情况又再次冲突所以要进行处理. 处理情况2 cur为红且在外侧p为红g为黑u不存在/u存在且为黑 u的两种情况 1.如果u节点不存在则cur一定是新插入节点因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色就不满足性质4:每条路径黑色节点个数相同。 ⒉.如果u节点存在则其一定是黑色的那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。 处理方法单旋变色。按p节点进行右旋此时p为红g为黑再将p和g的颜色进行交换即满足红黑树规则。若p为g的右孩子cur为p的右孩子则进行左单旋转p、g变色--p变黑g变红。处理完成后不需要再进行往上处理因为此时p为黑p的父亲节点为黑或红都不会对树产生影响。 处理情况3 cur为红且在内侧p为红g为黑u不存在/u存在且为黑 处理方法双旋变色
u不存在情况
若p在g的左侧cur在内侧则先对g的左子树进行左旋在对g这棵子树进行右旋反之p在g的右侧cur在内存就先右旋再左旋再交换cur和g的颜色。 u存在情况
像这种情况都是由情况一经过处理后得来的此时就需要先对g的左子树进行左单旋旋转后就会变为情况二此时再根据情况二的解决方法进行解决右旋变色旋转后将cur和g的颜色进行交换即可。如果最开始p是在右子树则操作相反先右旋再左旋变色。 插入总结 1.红黑树插入的节点一定为红色 2.处理三种可能的情况关键在于叔叔节点u 3.u存在且为红情况一将p和u节点变黑g节点变红若g为根节点就将g变为黑色 4.情况二和情况三都是由情况一经过变化后得来的 4.u不存在或存在且为黑插入的节点cur在p的外侧情况二若p是左子树就进行右旋交换p、g颜色若p是右子树反之左旋交换颜色。 5.u不存在或存在且为黑插入节点cur在p的内侧情况三若p是左子树就先进行左旋变为情况二再进行右旋交换颜色。反之p为右子树先进行右旋变为情况二在进行左旋交换颜色。 四、插入操作源码
插入源码 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) // parent为红色就需要变色处理因为插入的节点为红{Node* grandfater parent-_parent; //祖父节点assert(grandfater);assert(grandfater-_col BLACK);// 关键看叔叔if (parent grandfater-_left){Node* uncle grandfater-_right; //叔叔节点// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater; // 往上处理的时候把祖父当做插入的节点即curparent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return true;}旋转操作的源码解析可以参考这篇博文http://t.csdn.cn/iyMac
左旋 void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (_root parent){_root subR;subR-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}右旋 void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}五、红黑树验证
验证方法判断从根节点起的每一条子路径中的黑节点数是否相等规则4。利用递归的思想遍历每一条路径。再遍历第一条路径的时候设置一个benchmark记录黑色节点数量因为规则4所以后面每一条路径的黑节点数应该都要与之相等如果不等则不是红黑树。再遍历每一条路径的同时也可以寻找是否存在连续的红节点规则三存在则不满足为红黑树。依次递归每一条路径。
源码 bool IsBalance(){if (_root nullptr){return true;}if (_root-_col RED){cout 根节点不是黑色 endl;return false;}// 黑色节点数量基准值int benchmark 0;return PrevCheck(_root, 0, benchmark);}bool PrevCheck(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark 0) // 遍历第一条路径的时候记录他的黑节点数后面每一条路径的黑节点数一个都和他相等{benchmark blackNum;return true;}if (blackNum ! benchmark){cout 某条黑色节点的数量不相等 endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return PrevCheck(root-_left, blackNum, benchmark) PrevCheck(root-_right, blackNum, benchmark);}void TestRBTree()
{size_t N 1000;srand(time(0));RBTreeint, int t1;for (size_t i 0; i N; i){int x rand();cout Insert: x : i endl;t1.Insert(make_pair(x, i));}cout IsBalance: t1.IsBalance() endl; //打印1则是红黑树否则不是
}
