旅游网站建设解决方案,重庆做网站推广,网线制作工具,学校网站群建设必要欢迎点赞评论关注~~~~~~~如上图#xff0c;二叉查找树极端情况下可能会变成一个单链表#xff0c;这种查询时间复杂度就变成O(n)了#xff0c;红黑树在二叉查找树的基础上进行了自平衡。1.原理分析如上图#xff0c;红黑树具有以下特征#xff1a;1. 每个节点要么是黑色关注~~~~~~~如上图二叉查找树极端情况下可能会变成一个单链表这种查询时间复杂度就变成O(n)了红黑树在二叉查找树的基础上进行了自平衡。1.原理分析如上图红黑树具有以下特征1. 每个节点要么是黑色要么是红色2. 根节点是黑色3. 每个叶子节点都是黑色的空结点(NIL结点)4. 如果一个节点是红色的则它的子节点必须是黑色的5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点6.新插入节点默认为红色插入后需要校验红黑树是否符合规则不符合则需要进行平衡红黑树节点的增加删除都需要保证满足以上特征红黑树采取多种方式来维护这些特征从而维持平衡。主要包括左旋转、右旋转、颜色反转1.1左旋(RotateLeft )逆时针旋转红黑树的两个结点使得父结点被自己的右孩子取代而自己成为自己的左孩子。如图所示以X为基点逆时针旋转X的父节点被x原来的右孩子Y取代c保持不变 Y节点原来的左孩子c变成X的右孩子这样的旋转仍然保证了二叉查找树的特征左节点比父节点小右节点仍然比父节点大,即a1.2 右旋(RotateRight)顺时针旋转红黑树的两个结点使得父结点被自己的左孩子取代而自己成为自己的右孩子。如图所示以X为基点顺时针旋转 X的父节点被x原来的左孩子Y取代 b保持不变 Y节点原来的右孩子c变成X的左孩子 。这样的旋转仍然保证了二叉查找树的特征左节点比父节点小右节点仍然比父节点大,即b1.3颜色反转新增节点默认为红色而父节点和叔叔节点也为红色这种情况就违反了红黑树的规则(父与子不能同时为红色)需要将红色往祖辈上传父节点和叔叔节点变为黑色这样来保证每条叶子结点到根节点的黑色节点数量并未发生变化。插入新节点的时候存在如下几种情况1.插入节点位于树根没有父节点这种情况直接让新结点变色为黑色.2.插入节点的父节点是黑色,新插入的红色节点并没有打破红黑树的规则所以不需要做任何调整3.插入节点的父节点和叔叔节点是红色此种情况不满足父子节点不能同时为红色的规则先让B变成黑色这样又不满足某一个节点到每个叶子节点经过的黑色节点数相同的规则先让A变成红色此时A、C父子节点又变成了红色所以将C调整为黑色来使这一局部满足红黑树的规则4.插入节点的父节点是红色叔叔节点是黑色或者没有叔叔且插入节点是父节点的右孩子父节点是祖父节点点的左孩子以结点B为轴做一次左旋转使得新结点D成为父结点原来的父结点B成为D的左孩子 变成父节点是红色叔叔节点是黑色或者没有叔叔新插入节点是父结点的左孩子父节点是祖父节点的左孩子以结点A为轴做一次右旋转使得结点B成为祖父结点结点A成为结点B的右孩子接着将B变成黑色A变成红色就局部满足红黑树的规则了。小结旋转和颜色反转都是为了是树满足红黑树的5个特性从而达到自平衡的效果。变化规律总结根节点必黑新增是红色只能黑连黑不能红连红 爸叔通红就变色爸红叔黑就旋转哪边黑往哪边转。2.代码实现2.1 红黑树节点结构class RBTreeNode{private int value;//数据 private boolean isBlack;//红黑标记 private RBTreeNode left;//左节点 private RBTreeNode right;//右边节点 private RBTreeNode parent;//父节点 public RBTreeNode(int value) { this.isBlackfalse;//默认节点为红色 this.value value; } setter,getter....}2.2 遍历节点方法为了方便获取节点数据编写一个遍历树的方法,使用递归的方式实现在树中递归很常用。public void traverse(RBTreeNode node){ if (nodenull) return; //递归终止条件 if (node.getLeft()null node.getRight()null){ //叶子节点 System.out.println(node.getValue()); return ; } //先遍历左节点,后遍历右节点 traverse(node.getLeft()); traverse(node.getRight()); }2.3 新增节点主要是从根节点依次对比 data和node.getValue的大小一直找到被挂载得节点在进行挂载。public void insert(int data){ RBTreeNode nodenew RBTreeNode(data); if (rootnull){ //插入根节点 rootnode; root.setBlack(true);//树根是黑色 return; } RBTreeNode parentroot; RBTreeNode son; if (data2.4 自平衡方法自平衡方法按照需求可以拆分为左旋转、右旋转、设置黑色、设置红色方法2.4.1 左旋转方法结合图查看代码逻辑更清晰旋转过程。/** * 左旋转(逆时针旋转) * param node */ private void leftRotate(RBTreeNode node) { RBTreeNode right node.getRight(); RBTreeNode parent node.getParent(); if (parentnull){ //root节点,将 rootright; right.setParent(null); }else{ if (parent.getLeft()!nullparent.getLeft()node){ // 左右 //node是左子节点左旋转直接将node右子节点旋转挂到父节点左节点 parent.setLeft(right); }else { //右右的情况 //node是子节点直接将node的右子节点旋转挂到父节点的右子节点 parent.setRight(right); } right.setParent(parent); } node.setParent(right); node.setRight(right.getLeft()); if (right.getLeft()!null){ right.getLeft().setParent(node); } right.setLeft(node); }2.4.2 右旋转方法/** * 右旋转(顺时针) * param node */ private void rightRotate(RBTreeNode node) { RBTreeNode left node.getLeft(); RBTreeNode parent node.getParent(); if (parent null) { //根节点 root left; left.setParent(null); } else { if (parent.getLeft() ! null parent.getLeft() node) { //将node的左子节点挂父节点 parent.setLeft(left); } else { //将node的左节点挂父节点的右节点 parent.setRight(left); } left.setParent(parent); } node.setParent(left); node.setLeft(left.getRight()); if (left.getRight() ! null) { left.getRight().setParent(node); } left.setRight(node); }2.4.3 设置红黑色方法private void setRed(RBTreeNode node) { node.setBlack(false); } private void setBlack(RBTreeNode node) { node.setBlack(true); }2.4.4 自平衡方法/** * 节点自平衡 * param node */ private void nodeBanlance(RBTreeNode node) { RBTreeNode father,gFather;//父节点祖父节点 //父节点是红色的 while((fathernode.getParent())!null father.isBlack()false){ gFatherfather.getParent(); if (gFather.getLeft()father){ //父节点在祖父节点的左侧 RBTreeNode uncle gFather.getRight();//叔叔节点 if (uncle!null !uncle.isBlack()){ //叔叔节点不为空 且是红色的 //这种情况需要反色,父节点和叔叔节点变黑爷爷节点变红 setBlack(father); setBlack(uncle); setRed(gFather); //继续循环 nodegFather; continue; } if (nodefather.getRight()){ //需要左旋 leftRotate(father); RBTreeNode tmpnode; nodefather; fathertmp; } setBlack(father); setRed(gFather); //右旋 rightRotate(gFather); }//父为祖右孩子 else { RBTreeNode uncle gFather.getLeft(); if (uncle ! null !uncle.isBlack()) { setBlack(father); setBlack(uncle); setRed(gFather); node gFather; continue; } if (node father.getLeft()) { //右旋 rightRotate(father); RBTreeNode tmp node; node father; father tmp; } setBlack(father); setRed(gFather); //左旋 leftRotate(gFather); } } setBlack(root); }2.5 总结查询时间复杂度 O(logn)应用场景在JDK1.8中HashMap使用数组链表红黑树的数据结构。内部维护着一个数组table该数组保存着每个链表的表头结点或者树的根节点。
