老搞不清左旋右旋是往哪边转,索性写成哪个方向的子节点上浮
/** * * 总结:红黑树的难点在于插入和删除后的对于树规则的修复, * 在新增时主要采取的策略是上浮插入的红色节点,当遇到cpg连成一条线 并且 cp为红色的情况 我们可以交换 pg 颜色上浮 p,因为上浮的颜色是r 并不会破坏树的结构 * 在删除时主要才去的策略是让 要么可以涂红b的黑色让问题移到p上,要么将p的右侧想办法弄成r 以至于我们交换黑色的b和红色的p之后填充了另一侧的黑色,然后将原来 * 右侧的子节点涂黑,不让右侧的节点数发生变化 * 注意点:红黑树要么单支黑p红c,要么有两个子节点 * * *@author Zhouk*@date 2017年3月7日 下午3:40:23*@describtion BRTree**/public class BRTree<T> { PRivate Node<T> root; public void insert(int index ,T value){ if(root==null){ root = new Node<T>(index, value, false); }else{ insertByStep(root,index,value); } } private Node<T> insertByStep(Node<T> currentParent,int index,T value){ if(index>currentParent.index){ Node<T> rightChild=currentParent.rightChild; if(rightChild==null){ Node<T> insertNode=new Node<T>(index, value,true); insertNode.parent=currentParent; currentParent.rightChild=insertNode; //对于新增节点需要进行 fixed操作 fixedAfterInsert(insertNode); return insertNode; }else if(rightChild.index==index){ rightChild.value=value; return rightChild; }else{ return insertByStep(rightChild, index, value); } }else{ Node<T> leftChild=currentParent.leftChild; if(leftChild==null){ Node<T> insertNode=new Node<T>(index, value,true); insertNode.parent=currentParent; currentParent.leftChild=insertNode; //对于新增节点需要进行 fixed操作 fixedAfterInsert(insertNode); return insertNode; }else if(leftChild.index==index){ leftChild.value=value; return leftChild; }else{ return insertByStep(leftChild, index, value); } } } /** * 添加核心思想是将红色 节点上浮 * 但是 在 * b b * r:p b => r:c b * b r:c r:p * b * 或者 * b b * b r:p => b r:c * r:c b r:p * b * * 这两种 情况 下 结果中的是 r:p 不符合 要求 但是出现了 红色节点下沉的情况 需要特殊处理 * 我们需要将 r:c 涂黑 结果是 r:c 下 黑 多出一个 * 于是 我们将 root的b 涂红 结果 是 root 另外一个分支 少了一个黑 * 我们将 现在是 黑的 r:c 上浮 解决问题 * 要注意的是 * 那么 要满足的条件就是 之前的root 节点 接手的那个 节点 必然需要时黑色 * 不然 root已经被涂红 下移 那么 会出现 两个 假如 r:c 交给他的节点是红色就会出现错误 * 在r:c 是root 左支 时候 交给 root的 是r:c 的rightChild * 在r:c 是root 右支时交给 root的的是 r:c的 leftChild * 总结如下: * //p:parent g:grandfatehr c:child u:uncle * * 1:u:b p:r为g:b左支 c:r为p:r左支: 涂黑 p 涂红g 上浮 p=>complete * 2:u:b p:r为g:b左支 c:r为p:r右支: 上浮c p 为 新的 c 转到 情况1 * 3:u:b p:r为g:b右支 c:r为p:r左支: 上浮 c p 为新的c 转到情况4 * 4:u:b p:r为g:b右支 c:r为p:r右支 涂黑 p 涂红 g 上浮p =>complete * * * 剩余情况 就是p:r u:r(p必然是r ,如果为 b 那么 已经结束) * 那么 涂黑 p 和 u 涂红 g g为新的 c 可能不满足情况 * @param currentNode */ private void fixedAfterInsert(Node<T> currentNode){ //如果当前节点是root节点 那么 无论什么颜色直接涂黑 if(currentNode.parent==null){ currentNode.color=false; } //如果插入节点的父节点 的颜色为黑 那么 什么也不做 返回 if(!currentNode.parent.color){ return; } //如果 父节点 为红色 此时必然有祖父节点 else{ //如果叔父节点为 黑色 Node<T> uncleNode=getParentAnotherChild(currentNode.parent); if(uncleNode==null||!uncleNode.color){ //判断 位置 Node<T> parent=currentNode.parent; Node<T> grandParent=parent.parent; if(grandParent.index>parent.index){ //情况1 if(parent.index>currentNode.index){ grandParent.color=true; parent.color=false; leftChildFloat(parent); } //情况2 else{ rightChildFloat(currentNode); fixedAfterInsert(currentNode.leftChild); } }else{ //情况3 if(parent.index>currentNode.index){ leftChildFloat(currentNode); fixedAfterInsert(currentNode.rightChild); } //情况4 else{ grandParent.color=true; parent.color=false; rightChildFloat(parent); } } } //如果叔父节点为红色 else{ //将 父亲节点 和叔父节点颜色涂黑 祖父节点涂红 重新开始 fixed操作 uncleNode.color=false; currentNode.parent.color=false; currentNode.parent.color=true; fixedAfterInsert(currentNode.parent.parent); } } } public boolean remove(int i){ Node<T> removeNode=find(i); if(removeNode==null)return false; //假如删除的不是叶子节点 需要进行fixed操作 deleteAndFixed(removeNode); return true; } /** * @param removeNode 待删除的节点 * 定义待删除节点 为 r 定义 右侧最小节点的 s * s 可能存在 右支但是 不可能有左支 * 我们交换s和r 的 index 和 value * 现在假如 s为红色 那么并 不影响平衡 * 但如果 s 为 黑色 那么 原来 s 位置 现在 r 位置就少了一个黑色 * 我们需要让 现在 r的右侧移动一个黑色过来 再删掉r * 如果 r的兄弟节点 b 为红色 直接上浮 b ,b 和p(父节点)交换颜色, * * * 交换颜色 上浮的实质: * * 因为 g 节点会移动到另一侧 但是颜色是p的颜色 * * 假如p是b,g是r 那么 移动后 g移动过的一侧多了原来p的颜色b(用于删除时填充b) * 而现在 原来p这一侧的root变成了 r 少了个b (原来c未移动的子节点为红色 ,我们可以直接涂黑 达到平衡) * //这就需要 假如左节点上浮 需要 孩子的左孩子为 红色 * 假如 右节点上浮 需要孩子的右孩子为红色 * (删除时仅仅存在这种情况 ,被删除的是右侧最小节点,都是左边少) * 假如p是r,g是b 那么 移动后 g移动过的一侧多了 r (无所谓) * 而现在 原来p这一侧的root变成b 也无所谓 * //所以假如在p是r g是b的情况下 我们可以随意交换移动 * (就像新增时调整一样,可以用来调整连续r的问题) * * * 解决一侧少一个黑的方法 * 0:假如兄弟节点为红 那么 上浮兄弟节点交换 b和p的颜色 那么原来兄弟节点的子节点 * (红色的子节点 ,必为黑) * 变成现在的兄弟节点 进入其余b为黑的情况 * 1:假如b 为黑 那么 我需要将当前b的右孩子变成红色 * 1.1假如左右还是都是黑色 那么 涂红b p为新的c * 1.2假如左侧是红色 右侧是黑色 那么把左侧的红色移动到右侧 (交换b和其左侧的黑色 然后上浮左侧子节点) * 左侧子节点 为新的b 其右侧为原来的b颜色为原来左侧的颜色r 转入1.3 * 1.3假如左侧是右侧是红色 那么 那么我们可以交换p和g颜色 上浮p 涂黑右侧子节点 达到平衡 * * * 删除存在的特殊情况: * 删除的是root节点 直接删了 * 要么是单支黑p红c直接将g的child指向c c的parent指向g * 假如删除的是叶子节点 直接进入fix操作 */ private void deleteAndFixed(Node<T> removeNode){ //假如是根节点 if(removeNode.parent==null){ root=null; return; } //叶子节点的情况 if(removeNode.leftChild==null&&removeNode.rightChild==null){ fixedAfterDelete(removeNode); if(removeNode.index<removeNode.parent.index){ removeNode.parent.leftChild=null; }else{ removeNode.parent.rightChild=null; } } //黑色红单支的情况 else if(removeNode.rightChild==null){ Node<T> parent=removeNode.parent; Node<T> leftChild=removeNode.leftChild; if(parent.index>removeNode.index){ parent.leftChild=leftChild; leftChild.parent=parent; leftChild.color=false; }else{ parent.rightChild=leftChild; leftChild.parent=parent; leftChild.color=false; } }else if(removeNode.leftChild==null){ Node<T> parent=removeNode.parent; Node<T> rightChild=removeNode.rightChild; if(parent.index>removeNode.index){ parent.leftChild=rightChild; rightChild.parent=parent; rightChild.color=false; }else{ parent.rightChild=rightChild; rightChild.parent=parent; rightChild.color=false; } } //双子节点的情况 else{ Node<T> finalRemoveNode=removeNode.rightChild; while(finalRemoveNode.leftChild!=null){ finalRemoveNode=finalRemoveNode.leftChild; } //如果是红色 不做操作 if (finalRemoveNode.color) { return; }else{ removeNode.value=finalRemoveNode.value; removeNode.index=finalRemoveNode.index; fixedAfterDelete(finalRemoveNode); } if(finalRemoveNode.index<finalRemoveNode.parent.index){ finalRemoveNode.parent.leftChild=null; }else{ finalRemoveNode.parent.rightChild=null; } } } private void fixedAfterDelete(Node<T> finalRemoveNode){ //如果兄弟节点为黑色 注意 兄弟节点不可能为null 为null时当前节点必为红色 Node<T> brother=getParentAnotherChild(finalRemoveNode); //如果brother为红色 if(brother.color){ brother.color=false; brother.parent.color=true; rightChildFloat(brother); //任然处理当前节点 fixedAfterDelete(finalRemoveNode); }else{ //子节点全黑 if(!isRed(brother.leftChild)&&!(isRed(brother.rightChild))){ //brother 涂红 brother.color=true; fixedAfterDelete(brother.parent); }else if(isRed(brother.leftChild)){ brother.leftChild.color=false; brother.color=true; leftChildFloat(brother.leftChild); }else{ brother.color=false; brother.parent.color=true; rightChildFloat(brother); brother.leftChild.color=false; } } } private boolean isRed(Node<T> node){ return node!=null&&node.color; } public Node<T> find(int i){ if(root==null)return null; return findByStep(root,i); } public Node<T> findByStep(Node<T> currentParent,int i){ if(currentParent.index>i){ Node<T> leftChild=currentParent.leftChild; if(leftChild==null)return null; if(leftChild.index==i)return leftChild; return findByStep(leftChild,i); }else{ Node<T> rightChild=currentParent.rightChild; if(rightChild==null)return null; if(rightChild.index==i)return rightChild; return findByStep(rightChild,i); } } /** * 返回兄弟节点 * @param currentNode * @return */ private Node<T> getParentAnotherChild(Node<T> currentNode){ if(currentNode==null||currentNode.parent==null){ return null; } if(currentNode.index<currentNode.parent.index){ return currentNode.parent.rightChild; }else{ return currentNode.parent.leftChild; } } /** * 左侧孩子 上浮 * @param itemNode 孩子节点 */ private void leftChildFloat(Node<T> itemNode){ Node<T> parent=itemNode.parent; Node<T> grandParent=parent.parent; Node<T> right=itemNode.rightChild; parent.parent=itemNode; itemNode.rightChild=parent; parent.leftChild=right; if(right!=null){ right.parent=parent; } itemNode.parent=grandParent; if(grandParent!=null){ if(grandParent.index>itemNode.index){ grandParent.leftChild=itemNode; }else{ grandParent.rightChild=itemNode; } } } /** * 右侧孩子上浮 * @param itemNode 孩子节点 */ private void rightChildFloat(Node<T> itemNode){ Node<T> parent=itemNode.parent; Node<T> grandParent=parent.parent; Node<T> left=itemNode.leftChild; parent.parent=itemNode; itemNode.leftChild=parent; parent.rightChild=left; if(left!=null){ left.parent=parent; } itemNode.parent=grandParent; if(grandParent!=null){ if(grandParent.index>itemNode.index){ grandParent.leftChild=itemNode; }else{ grandParent.rightChild=itemNode; } } } public static class Node<T>{ int index; T value; Node<T> parent; Node<T> leftChild; Node<T> rightChild; /** * red:true,black:false */ boolean color; public Node(int index, T value, boolean color) { super(); this.index = index; this.value = value; this.color = color; } }}新闻热点
疑难解答
