【数据结构】红黑树旋转

数据结构 学习笔记

什么是红黑树

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

看到一篇不错的博客,有详细的图例。这里查看

实现红黑树旋转

public class RedBlackTree {
    RedBlackTree parent;
    RedBlackTree left;
    RedBlackTree right;
    String key;
    int color;

    public RedBlackTree(String key){
        this.key = key;
    }

    //中序遍历
    static void print(RedBlackTree redBlackTree){
        System.out.print(redBlackTree.key+",");
        if(redBlackTree.left != null){
            print(redBlackTree.left);
        }
        if(redBlackTree.right != null){
            print(redBlackTree.right);
        }
    }

    //左旋
    static void leftRotate(RedBlackTree x){
        RedBlackTree y = x.right;
        x.right = y.left;
        if(y.left != null){
            y.left.parent = x;
        }
        y.parent = x.parent;
        if(x.parent == null){
            //y is root
        }else if(x == x.parent.left){
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    //右旋
    static void rightRotate(RedBlackTree y){
        RedBlackTree x = y.left;
        y.left = x.right;
        if(x.right.parent != null){
            x.right.parent = y;
        }
        x.right = y;
        if(y.parent == null){
            //x is root
        }else if(y.parent.left == y){
            y.parent.left = x;
        }else {
            y.parent.right = x;
        }
        x.parent = y.parent;
        y.parent = x;
    }
}

@Test
    public void test(){
        /**
         *   X
         *  / \
         * a  Y
         *   /\
         *  b  r
         * 先序遍历:X,a,Y,b,r,
         * 旋转后
         *     Y
         *    / \
         *   X  r
         *  /\
         * a b
         * 先序遍历:Y,X,a,b,r,
         */
        RedBlackTree x = new RedBlackTree("X");
        RedBlackTree y = new RedBlackTree("Y");
        RedBlackTree a = new RedBlackTree("a");
        RedBlackTree b = new RedBlackTree("b");
        RedBlackTree r = new RedBlackTree("r");

        x.left = a;
        a.parent = x;

        y.left = b;
        y.right = r;
        b.parent = y;
        r.parent = y;

        x.right = y;
        y.parent = x;

        System.out.println("初始树:");
        RedBlackTree.print(x);
        RedBlackTree.leftRotate(x);
        System.out.println("\n左旋后");
        RedBlackTree.print(y);

        System.out.println("\n右旋后:");

        RedBlackTree.rightRotate(y);
        RedBlackTree.print(x);
    }
创建于2017年06月08日 16:50
阅读量 1155
留言列表

暂时没有留言

添加留言