广东手机网站建设价格,长沙网站 建设推广世云网络,网络推广优化品牌公司,网站建设和网站设计区别红黑树的性质#xff1a;
性质1#xff1a;每个节点要么是黑色#xff0c;要么是红色。
性质2#xff1a;根节点是黑色。性质3#xff1a;每个叶子节点#xff08;NIL#xff09;是黑色。性质4#xff1a;每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相…红黑树的性质
性质1每个节点要么是黑色要么是红色。
性质2根节点是黑色。性质3每个叶子节点NIL是黑色。性质4每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。性质5任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称黑高从性质5又可以推出性质5.1如果一个节点存在黑子节点那么该结点肯定有两个子节点
总结 根节点必黑新增是红色只能黑连黑不能红连红
红黑树的操作
红黑树能自平衡它靠的三种操作左旋、右旋和变色。 1.变色结点的颜色由红变黑或由黑变红。 2.左旋以某个结点作为支点(旋转结点)其右子结点变为旋转结点的父结点右子结点的左子结点变为旋转结点的右子结点左子结点保持不变。 3.右旋以某个结点作为支点(旋转结点)其左子结点变为旋转结点的父结点左子结点的右子结点变为旋转结点的左子结点右子结点保持不变
红黑树插入节点情景分析 情景1红黑树为空树 最简单的一种情景直接把插入结点作为根结点就行 注意根据红黑树性质2根节点是黑色。还需要把插入结点设为黑色。
情景2插入结点的Key已存在 处理更新当前节点的值为插入节点的值
情景3插入结点的父结点为黑结点 由于插入的结点是红色的当插入结点的黑色时并不会影响红黑树的平衡直接插入即可无需做自平衡。
情景4插入节点的父节点为红色 再次回想下红黑树的性质2根结点是黑色。如果插入节点的父结点为红结点那么该父结点不可能为根结点所以插入结点总是存在祖父结点。 这一点很关键因为后续的旋转操作肯定需要祖父结点的参与
插入情景4.1叔叔结点存在并且为红结点 依据红黑树性质4可知红色节点不能相连 祖父结点肯定为黑结点 因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是黑红红。显然最简单的处理方式是把其改为红黑红 处理 1.将P和U节点改为黑色 2.将PP改为红色 3.将PP设置为当前节点进行后续处理
插入情景4.2叔叔结点不存在或为黑结点并且插入结点的父亲结点是祖父结点的左子结点 注意单纯从插入前来看叔叔节点非红即空NIL节点否则的话破坏了红黑树性质5此路径会比其它路径多一个黑色节点。
插入情景4.2.1新插入节点为其父节点的左子节点LL红色情况 处理 1.变颜色将P设置为黑色将PP设置为红色 2.对PP节点进行右旋
插入情景4.2.2新插入节点为其父节点的右子节点LR红色情况 处理 1.对P进行左旋 2.将P设置为当前节点得到LL红色情况 3.按照LL红色情况处理1.变颜色 2.右旋PP
插入情景4.3叔叔结点不存在或为黑结点并且插入结点的父亲结点是祖父结点的右子结点 处理 1.变颜色将P设置为黑色将PP设置为红色 2.对PP节点进行左旋
插入情景4.3.2新插入节点为其父节点的左子节点RL红色情况 处理 1.对P进行右旋 2.将P设置为当前节点得到RR红色情况 3.按照RR红色情况处理1.变颜色 2.左旋PP
总结
爸叔通红就变色爸红叔黑就旋转哪边黑往哪边转。
