红黑树

一、二叉搜索树

image

二叉搜索树，也称有序二叉树,排序二叉树，具有以下特性：

1、是一棵二叉树

2、若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

3、若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

4、任意节点的左、右子树也分别为二叉查找树。

5、没有键值相等的节点。

二叉树的插入：

image

插入的结点总是作为某一叶子节点的子结点（插入后的树必须也是二叉树）

二叉树的删除：（删除后的树必须也是二叉树）

1、节点为叶子节点直接删除

2、节点有一个叶子节点，则删除该节点后将其叶子节点上移为新的父节点

3、节点有两个叶子节点，则删除该节点后将其右子树的中序列第一个节点（也就是右子树中的最小节点）上移为新的父节点，并将该节点的右节点（该节点必定无左节点）替代其原位置。

image

二、红黑树

红黑树（Red-Black Tree ：R-B Tree），它一种特殊的二叉搜索树。

在线动态红黑树（https://www.cs.usfca.edu/~galles/visualization/RedBlack.html）

image

红黑树的特性：（必须满足二叉搜索树的特性）

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点是黑色。（注意：这里的叶子节点均为NULL ！！！）

（4）如果一个节点是红色的，则它的子节点必须是黑色的。

（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

因为特性(5)，确保没有一条路径会比其他路径长出俩倍（黑-红-黑-红-黑 ：黑-黑-黑）。因而，红黑树是相对是接近平衡的二叉树。

无论是插入还是删除，最重要的就是要保证RBT的特性5


public class Node {
    private String colour = RBTree.RED;
    private Integer value;
    
    private Node fatherNode;
    private Node leftNode;
    private Node rightNode;
    
    private static int length=1;


    public Node( int value) {
        super();
        this.value = value;
    }
    
    public String getColour() {
        return colour;
    }

    public void setColour(String colour) {
        this.colour = colour;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }
    
    public void setFatherNode(Node fatherNode) {
        this.fatherNode = fatherNode;
    }

    public Node setLeftNode(Node leftNode){
        this.leftNode=leftNode;
        if(leftNode!=null){
            leftNode.setFatherNode(this);;
        }
        length++;
        return leftNode;
    }
    
    public Node setRightNode(Node rightNode){
        this.rightNode=rightNode;
        if(rightNode!=null){
            rightNode.setFatherNode(this);
        }
        length++;
        return rightNode;
    }
    
    public Node getLeftNode() {
        return leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public Node getFatherNode() {
        return fatherNode;
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return this.getColour()+":"+this.getValue();
    }
}

插入：

0、插入位置一定为非空的叶子节点（符合二叉搜索树）

1、插入的节点为红节点（为了满足特性5），若插入的是空树，则需要变为黑色（为了满足特性2）

-- 调整树

2、若插入节点的父节点为黑色，即可满足所有的特性（直接插入即可）

3、若插入节点的父节点为红色，（即一定存在黑色祖父节点，因为要满足特性2和特性4），叔节点也为红色，只需将父、叔节点变为黑色，祖父节点变为红色，然后再以祖父节点视为插入节点，进入步骤2重新调整树

4、插入N节点后,N的父节点为红色,叔叔节点为黑色,且N是右子

解决:以N节点父节点为新节点N,并以N为支点进行左旋,父节点变黑，原祖父节点变红，继续判定旋转后的节点N是否满

5、插入:插入N节点后,N的父节点为红色,叔叔节点为黑色,且N是左子

解决:N父节点变黑色,祖父节点变红色,祖父节点为支点进行右旋。

package tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
/**
 * 红黑树 
 * @author heqichao
 *
 */
public class RBTree {
    private Node tree;  //记录树结构
    public static String BLACK="黑";
    public static String RED="红";
    private Map<Integer,List> printMap;
    
    /**
     * 打印树结构
     */
    public void print(){
        printMap=new HashMap<Integer,List>();
        setPrintMap(tree,0);
        Iterator<Map.Entry<Integer, List>> it =printMap.entrySet().iterator();
        while(it.hasNext()){
             Map.Entry<Integer, List> entry=it.next();
             List list =entry.getValue();
             Iterator  listIt =list.iterator();
             while(listIt.hasNext()){
                 System.out.print(listIt.next());
                 System.out.print(",");
             }
             System.out.println();
        }
    }
    private void setPrintMap(Node node ,int i){
        if(printMap.get(i) ==null){
            printMap.put(i, new ArrayList());
        }
        if(node == null){
            //printMap.get(i).add(RBTree.BLACK+":NULL");
            return;
        }
        printMap.get(i).add(node.toString());
        i++;
        setPrintMap(node.getLeftNode(), i);
        setPrintMap(node.getRightNode(), i);
    }
    
    /**
     * 插入元素
     * @param num 元素值
     * @return
     */
    public  Node put(int num){
        //0、插入的节点一定为红色的非NULL的"叶子节点"
        Node insertNode =new Node(num);
        //1、如果树为空，则直接将该节点变为根节点（变黑色为了满足特性2）
        if(tree ==null ){
            insertNode.setColour(BLACK);
            tree=insertNode;
            return tree;
        }
        boolean hasValue =insert(tree,insertNode);
        if(!hasValue){
            Node fatherNode =insertNode.getFatherNode();
            //2、如果插入节点的父节点为黑色，则已满足所有特性，直接结束
            if(BLACK.equals(fatherNode.getColour())){
                return tree;
            }else{
                //3、如果插入节点的父节点为红色(祖父节点一定为黑色)，则需要按情况旋转或  重新着色
                addNodeAdjust(insertNode);
            }
        }
        return tree;
    }
    private  boolean insert(Node tree,Node insertNode){
        //查找结点的对应位置并插入
        if(tree.getValue() == insertNode.getValue()){
            return true;
        }else if( tree.getValue() > insertNode.getValue() ){ // 往左树查找
            if(tree.getLeftNode()!=null ){
                return insert(tree.getLeftNode(), insertNode);
            }else{
                tree.setLeftNode(insertNode);
            }
        }else{
            if(tree.getRightNode()!=null ){ //往右树查找
                return insert(tree.getRightNode(),insertNode);
            }else{
                tree.setRightNode(insertNode);
            }
        }
        return false;
    }
    
    /**
     * 调整树结构,根据情况旋转和着色
     * @param insertNode 基准节点
     */
    private  void addNodeAdjust(Node insertNode){
        if(insertNode == null){
            return;
        }
        //如果调整导致根节点变红，则直接令根节点变黑
        if(insertNode.getFatherNode() == null){
            insertNode.setColour(BLACK);
            return;
        }
        if(BLACK.equals(insertNode.getFatherNode().getColour())){
            return;
        }
        Node fatherNode =insertNode.getFatherNode();
        //3、如果插入节点的父节点为红色(祖父节点一定为黑色)，则需要按情况旋转或  重新着色
            //3.1 如果插入节点的叔节点也为红色，只需将父、叔节点变为黑色，祖父节点变为红色，然后再以祖父节点视为插入节点，重新调整树
        Node uncleNode =fatherNode.getFatherNode().getLeftNode();
        if(uncleNode == fatherNode){
            uncleNode=fatherNode.getFatherNode().getRightNode();
        }
        if(uncleNode!=null && RED.equals(uncleNode.getColour())){
            fatherNode.setColour(BLACK);
            uncleNode.setColour(BLACK);
            fatherNode.getFatherNode().setColour(RED);
            addNodeAdjust(fatherNode.getFatherNode());
        }else{
            //3.2插入节点的叔节点为黑色（注：叔节点为NULL，也是黑色!!!）
                Node grandFather =fatherNode.getFatherNode();
                if(insertNode.getValue()<fatherNode.getValue()){
                    //3.2.1插入节点在父节点左树，则右转
                    if(grandFather!=null && grandFather.getValue()< fatherNode.getValue()){
                    //    6
                    //          10
                    //       8         8为插入点,先右转后再左转
                        turnRight(insertNode); 
                        turnLeft(insertNode);
                        //继续检查调整
                        addNodeAdjust(insertNode.getFatherNode());
                    }else{
                    //          14
                    //      10
                    //   8             8为插入点,直接右转
                        turnRight(insertNode.getFatherNode());
                        //继续检查调整  
                        addNodeAdjust(fatherNode.getFatherNode());
                    }
                }else{
                    //3.2.2插入节点在父节点右树，则左转
                    if(grandFather!=null && grandFather.getValue()>fatherNode.getValue()){
                    //           10
                    //      6
                    //         8       8为插入点,先左转后再右转
                        turnLeft(insertNode);
                        turnRight(insertNode);
                        //继续检查调整
                        addNodeAdjust(insertNode.getFatherNode());
                    }else{
                    //   4
                    //      6 
                    //         8     8为插入点,直接左转转
                        turnLeft(insertNode.getFatherNode());
                        //继续检查调整
                        addNodeAdjust(fatherNode.getFatherNode());
                    }
                }
        }
    }
    
    /**
     * 将节点设置为根节点
     * @param node 
     */
    private void setRoot(Node node){
        Node srcRoot =node.getFatherNode();
        node.setFatherNode(null);
        if(srcRoot.getValue() <node.getValue()){
            srcRoot.setRightNode(node.getLeftNode());
            node.setLeftNode(srcRoot);
        }else{
            srcRoot.setLeftNode(node.getRightNode());
            node.setRightNode(srcRoot);
        }
        node.setColour(BLACK);
        srcRoot.setColour(RED);
        tree=node;
    }
    
    /**
     * 左转
     * @param node基准节点
     */
    private  void turnLeft(Node node){
        Node fatherNode =node.getFatherNode();
        Node grandFatherNode =fatherNode.getFatherNode();
        if(grandFatherNode == null){
            setRoot(node);
        }else{
            if(grandFatherNode.getValue()<fatherNode.getValue()){
                grandFatherNode.setRightNode(node);
            }else{
                grandFatherNode.setLeftNode(node);
            }
            fatherNode.setRightNode(node.getLeftNode());        
            node.setLeftNode(fatherNode);
            node.setColour(BLACK);
            fatherNode.setColour(RED);
        }
    }
    
    /**
     * 右转
     * @param node 基准节点
     */
    private  void turnRight(Node node){
        Node fatherNode =node.getFatherNode();
        Node grandFatherNode =fatherNode.getFatherNode();
        if(grandFatherNode == null){
            setRoot(node);
        }else{
            if(grandFatherNode.getValue()<fatherNode.getValue()){
                grandFatherNode.setRightNode(node);
            }else{
                grandFatherNode.setLeftNode(node);
            }
            fatherNode.setLeftNode(node.getRightNode());
            node.setRightNode(fatherNode);
            node.setColour(BLACK);
            fatherNode.setColour(RED);
        }
    }
    
    /**
     * 获取元素节点
     * @param tree
     * @param num
     * @return
     */
    public String get(int num){
        Node node =get(tree, num);
        if(node !=null){
            return node.toString();
        }
        return null;
    }
    private Node get(Node tree,int num){
        if(tree != null){
            if(tree.getValue() == num){
                return tree;
            }else if( tree.getValue() > num){ // 往左树查找
                if(tree.getLeftNode()!=null ){
                    return get(tree.getLeftNode(), num);
                }
            }else{
                if(tree.getRightNode()!=null ){ //往右树查找
                    return get(tree.getRightNode(), num);
                }
            }
        }
        return null;
    }
    
    private Node getRearNode(Node node){
        if(node.getLeftNode() == null){
            return node;
        }else{
            return getRearNode(node.getLeftNode());
        }
        
    }
    
    private void copyNodeValue(Node src,Node des){
        des.setValue(src.getValue());
    }
}

删除：
后补。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 红黑树之原理详解
    R-B Tree简介 R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找...
    张晨辉Allen阅读 9,351评论 5赞 30
  • 红黑树详解
    1、红黑树介绍 红黑树又称R-B Tree，全称是Red-Black Tree，它是一种特殊的二叉查找树，红黑树的...
    文哥的学习日记阅读 9,943评论 1赞 35
  • 数据结构与算法--从平衡二叉树(AVL)到红黑树
    数据结构与算法--从平衡二叉树(AVL)到红黑树 上节学习了二叉查找树。算法的性能取决于树的形状，而树的形状取决于...
    sunhaiyu阅读 7,687评论 4赞 32
  • 红黑树专题
    0.目录 1.算法导论的红黑树本质上是2-3-4树 2.红黑树的结构和性质 3.红黑树的插入 4.红黑树的删除 5...
    王侦阅读 2,542评论 1赞 2
  • 红黑树-算法导论
    这个周看算法导论，看到红黑树，看的我云里雾里绕啊。虽然最后看懂了，据我估计，要是过一个星期不看保证忘干净，因此决定...
    充满活力的早晨阅读 1,979评论 0赞 3