算法导论之红黑树

  • 定义
  • 插入
  • 删除

定义

等价于4阶B树


红黑树定义.png

插入

  • 插入示例


    插入示例.png
  • 双红情形1：uncle是黑色
    待补

  • 双红情形2：uncle是红色
    策略：只换色不旋转，转化为情形1


    双红情形2.png
  • 源代码 RedBlackTree.java 
package cs.tsinghua.edu.chapter8;

public class RedBlackTree<Key extends Comparable> extends BST {
    public static void main(String[] args) {
        int key11 = 11;
        int key2 = 2;
        int key14 = 14;
        int key1 = 1;
        int key7 = 7;
        int key15 = 15;
        int key5 = 5;
        int key8 = 8;
        int key4 = 4;
        //初始化红黑树
        RedBlackTree tree = new RedBlackTree();
        tree.insert(key11);
        tree.insert(key2);
        tree.insert(key14);
        tree.insert(key1);
        tree.insert(key7);
        tree.insert(key15);
        tree.insert(key5);
        tree.insert(key8);
        tree.inOrder(tree.root);
        //插入测试
        tree.insert(key4);
        tree.inOrder(tree.root);

    }

    @Override
    public BinNode insert(Comparable e) {
        BinNode x = super.search(e);
        if (x != null) {
            return x;
        }
        x = new BinNode();
        x.setKey(e);
        x.setParent(super.hot);
        x.setHeight(-1);
        x.setColor(RBColor.RB_RED);
        BinNode p = super.hot;
        if (p == null) {
            this.root = x;
        } else if (x.getKey().compareTo(p.getKey()) < 0) {
            p.setLeft(x);
        } else {
            p.setRight(x);
        }
        super.size++;
        //修正双红
        solveDoubleRed(x);
        return x != null ? x : super.hot.getParent();
    }

    private void solveDoubleRed(BinNode x) {
        if (super.isRoot(x)) {
            super.root.setColor(RBColor.RB_BLACK);
            super.root.setHeight(super.root.getHeight()+1);
            return ;
        }
        BinNode p = x.getParent();
        if (isBlack(p)) {
            return ;
        }
        BinNode g = p.getParent();
        BinNode u = super.getUncle(x);
        if (isBlack(u)) {
            if (super.isLChild(x) && super.isLChild(p)) {
                p.setColor(RBColor.RB_BLACK);
            }else {
                x.setColor(RBColor.RB_BLACK);
            }
            g.setColor(RBColor.RB_RED);
            BinNode gg = g.getParent();

            BinNode gCopy = new BinNode();
            gCopy.setKey(g.getKey());
            gCopy.setLeft(g.getLeft());
            gCopy.setRight(g.getRight());
            gCopy.setHeight(g.getHeight());
            gCopy.setColor(g.getColor());
            gCopy.setParent(g.getParent());

            BinNode xNewRoot = super.rotateAt(x);
            if (super.isRoot(gCopy)) {
                this.root = xNewRoot;
            }else if (super.isLChild(gCopy)) {
                g.getParent().setLeft(xNewRoot);
            }else {
                g.getParent().setRight(xNewRoot);
            }
            BinNode r = xNewRoot;
            r.setParent(gg);
        }else {
            //u是红色
            p.setColor(RBColor.RB_BLACK);
            p.setHeight(p.getHeight()+1);
            u.setColor(RBColor.RB_BLACK);
            u.setHeight(u.getHeight()+1);
            if (!super.isRoot(g)) {
                g.setColor(RBColor.RB_RED);
            }
            solveDoubleRed(g);
        }
    }

    private boolean isBlack(BinNode p) {
        boolean result = false ;
        if (p==null || p.getColor().equals(RBColor.RB_BLACK)) {
            result = true;
        }
        return result;
    }
}

辅助类

  • BST.java
package cs.tsinghua.edu.chapter8;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉搜索树实现
 */
public class BST<Key extends Comparable> {

    //入口：根节点
    protected BinNode root;
    //辅助节点:记录父节点引用
    protected BinNode hot;
    //节点个数
    protected int size;

    public static void main(String[] args) {
        BST tree = new BST();
        int key15 = 15;
        int key6 = 6;
        int key18 = 18;
        int key3 = 3;
        int key7 = 7;
        int key17 = 17;
        int key20 = 20;
        int key2 = 2;
        int key4 = 4;
        int key13 = 13;
        int key9 = 9;
        //插入测试
        tree.insert(key15);
        tree.insert(key6);
        tree.insert(key18);
        tree.insert(key3);
        tree.insert(key7);
        tree.insert(key17);
        tree.insert(key20);
        tree.insert(key2);
        tree.insert(key4);
        tree.insert(key13);
        tree.insert(key9);
        ////中序遍历
        tree.inOrder(key15);
//        //最大值
//        tree.getMax(tree.root);
//        //最小值
//        tree.getMin(tree.root);
//        //继任者
//        System.out.println(tree.getSuccessor(tree.root));
//        Node node9 = tree.search(entry9);
//        System.out.println(node9);
        //删除测试
        // 见297页情形a
        //tree.delete(entry9);
        //见297页情形b
        tree.delete(key13);
        //见297页情形c
        //tree.delete(entry18);
        //见297页情形d
        //tree.delete(entry15);
        tree.inOrder(tree.root);
    }

    protected Iterable<BinNode> inOrder(Key e) {
        BinNode x = search(e);
        return inOrder(x);
    }

    protected BinNode getSuccessor(BinNode x) {
        if (x.getRight() != null) {
            return getMin(x.getRight());
        }
        BinNode y = x.getParent();
        BinNode z = x;
        while (y != null && z.getKey().compareTo(y.getRight().getKey()) == 0) {
            z = y;
            y = y.getParent();
        }
        return y;
    }

    protected BinNode getMax(Key e) {
        BinNode x = search(e);
        if (x != null) {
            return getMax(x);
        }
        return x;
    }

    private BinNode getMax(BinNode x) {
        BinNode y = x;
        while (y.getRight() != null) {
            y = y.getRight();
        }
        return y;
    }

    protected void delete(Key e) {
        BinNode x = search(e);
        delete(x);
    }

    protected void delete(BinNode z) {
        BinNode x = z;
        if (x.getLeft() == null) {
            //情形a
            transplant(x, x.getRight());
        } else if (x.getRight() == null) {
            //情形b
            transplant(x, x.getLeft());
        } else {
            BinNode y = getMin(x.getRight());
            BinNode p = y.getParent();
            if ((p.getKey().compareTo(x.getKey())) != 0) {
                //节点y不是待删除节点的右孩子
                transplant(y, y.getRight());
                y.setRight(x.getRight());
                y.getRight().setParent(y);
            }
            transplant(x, y);
            y.setLeft(x.getLeft());
            y.getLeft().setParent(y);
        }
    }

    /**
     * 使用节点v替换节点u
     * 主要功能：修改节点u的父节点及其左右孩子节点的指向
     *
     * @param u
     * @param v
     */
    private void transplant(BinNode u, BinNode v) {
        BinNode y = u.getParent();
        if (y == null) {
            //节点u是根节点
            this.root = v;
        } else if (y.getLeft() != null && y.getLeft().getKey().compareTo(u.getKey()) == 0) {
            //节点u是左孩子
            y.setLeft(v);
        } else if (y.getRight() != null && y.getRight().getKey().compareTo(u.getKey()) == 0) {
            //节点u是右孩子
            y.setRight(v);
        }
        //修改节点v的父节点
        if (v != null) {
            v.setParent(y);
            this.hot = y;
            updateHeightAbove(y);
        }
    }

    private BinNode getMin(BinNode x) {
        BinNode y = x;
        while (y.getLeft() != null) {
            y = y.getLeft();
        }
        return y;
    }

    public Iterable<BinNode> inOrder(BinNode x) {
        List<BinNode> nodes = new ArrayList<>();
        Stack<BinNode> helper = new Stack<>();
        BinNode y = x;
        while (true) {
            if (y != null) {
                helper.push(y);
                y = y.getLeft();
            } else if (!helper.isEmpty()) {
                y = helper.pop();
                nodes.add(y);
                y = y.getRight();
            } else {
                break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (BinNode node : nodes) {
            sb.append(node.getKey()).append("#").append(node.getColor().getName()).append(" ");
        }
        System.out.println(sb);
        return nodes;
    }

    protected BinNode search(Key e) {
        this.hot = null;
        return search(this.root, e);
    }

    private BinNode search(BinNode x, Key e) {
        if (x == null || x.getKey().compareTo(e) == 0) {
            return x;
        }
        this.hot = x;
        if (e.compareTo(x.getKey()) < 0) {
            return search(x.getLeft(), e);
        } else {
            return search(x.getRight(), e);
        }
    }

    public BinNode insert(Key e) {
        BinNode w = search(e);
        if (w != null) {
            return w;
        }
        BinNode y = null;
        BinNode x = this.root;
        while (x != null) {
            y = x;
            if (e.compareTo(x.getKey()) < 0) {
                x = x.getLeft();
            } else {
                x = x.getRight();
            }
        }
        this.hot = y;
        BinNode z = new BinNode();
        z.setParent(y);
        z.setKey(e);
        if (y == null) {
            this.root = z;
        } else if (z.getKey().compareTo(y.getKey()) < 0) {
            y.setLeft(z);
        } else {
            y.setRight(z);
        }
        updateHeightAbove(z);
        this.size ++;
        return z;
    }

    protected void updateHeightAbove(BinNode x) {
        BinNode y = x;
        while (y != null) {
            updateHeight(y);
            y = y.getParent();
        }
    }

    protected void updateHeight(BinNode x) {
        int height = 1 + Math.max(getStature(x.getLeft()), getStature(x.getRight()));
        x.setHeight(height);
    }

    protected int getStature(BinNode x) {
        int height = -1;
        if (x != null) {
            height = x.getHeight();
        }
        return height;
    }

    protected boolean isLChild(BinNode x) {
        boolean result = false;
        if (!isRoot(x) && x.getKey().compareTo(x.getParent().getKey()) < 0) {
            result = true;
        }
        return result;
    }

    protected boolean isRoot(BinNode x) {
        boolean result = false;
        if (x != null && x.getParent() == null) {
            result = true;
        }
        return result;
    }

    protected boolean isRChild(BinNode x) {
        boolean result = false;
        if (!isRoot(x) && x.getKey().compareTo(x.getParent().getKey()) > 0) {
            result = true;
        }
        return result;
    }

    protected boolean hasRChild(BinNode x) {
        boolean result = false;
        if (x.getRight() != null) {
            result = true;
        }
        return result;
    }

    protected boolean hasLChild(BinNode x) {
        boolean result = false;
        if (x.getLeft() != null) {
            result = true;
        }
        return result;
    }

    protected BinNode getUncle(BinNode x) {
        if (isLChild(x.getParent())) {
            return x.getParent().getParent().getRight();
        }else {
            return x.getParent().getParent().getLeft();
        }
    }

    protected BinNode fromParent(BinNode x) {
        if (isRoot(x)) {
            return this.root;
        }else if (isLChild(x)) {
            return x.getParent().getLeft();
        }else {
            return x.getParent().getRight();
        }
    }

    protected BinNode rotateAt(BinNode v) {
        BinNode p = v.getParent();
        BinNode g = p.getParent();
        if (isLChild(p)) {
            if (isLChild(v)) {
                p.setParent(g.getParent());
                return connect34(v,p,g, v.getLeft(),v.getRight(), p.getRight(), g.getRight());
            }else {
                v.setParent(g.getParent());
                return connect34(p, v, g, p.getLeft(), v.getLeft(), v.getRight(), g.getRight());
            }
        }else {
            if (isRChild(v)) {
                p.setParent(g.getParent());
                return connect34(g,p,v, g.getLeft(), p.getLeft(), v.getLeft(), v.getRight());
            }else {
                v.setParent(g.getParent());
                return connect34(g,v,p, g.getLeft(), v.getLeft(), v.getRight(), p.getRight());
            }
        }
    }

    private BinNode connect34(BinNode a, BinNode b, BinNode c, BinNode T0, BinNode T1, BinNode T2, BinNode T3) {
        //a
        a.setLeft(T0);
        if (T0 != null) {
            T0.setParent(a);
        }
        a.setRight(T1);
        if (T1 != null) {
            T1.setParent(a);
        }
        updateHeight(a);
        //c
        c.setLeft(T2);
        if (T2 != null) {
            T2.setParent(c);
        }
        c.setRight(T3);
        if (T3 != null) {
            T3.setParent(c);
        }
        updateHeight(c);
        //b
        b.setLeft(a);
        a.setParent(b);
        b.setRight(c);
        c.setParent(b);
        updateHeight(b);
        return b;
    }
}
  • BinNode.java
package cs.tsinghua.edu.chapter8;


public class BinNode<Key extends Comparable> {
    private Key key;

    private BinNode parent;

    private BinNode left;

    private BinNode right;

    private int height;

    private RBColor color;

    public Key getKey() {
        return key;
    }

    public void setKey(Key key) {
        this.key = key;
    }

    public BinNode getParent() {
        return parent;
    }

    public void setParent(BinNode parent) {
        this.parent = parent;
    }

    public BinNode getLeft() {
        return left;
    }

    public void setLeft(BinNode left) {
        this.left = left;
    }

    public BinNode getRight() {
        return right;
    }

    public void setRight(BinNode right) {
        this.right = right;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public RBColor getColor() {
        return color;
    }

    public void setColor(RBColor color) {
        this.color = color;
    }

}
  • RBColor.java
package cs.tsinghua.edu.chapter8;

public enum RBColor {

    RB_BLACK(0,"黑色"),
    RB_RED(1,"红色");

    RBColor(int color, String name) {
        this.color = color;
        this.name = name;
    }

    public int getColor() {
        return color;
    }

    public String getName() {
        return name;
    }

    private final int color;

    private final String name;

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

推荐阅读更多精彩内容

  • 算法导论之红黑树&区间树
    实验要求 实验代码 区间树的很多操作是红黑树进行一点简单的修改，区间树中加入的max域 注意在插入和旋转的时候进行...
    东来_198c阅读 1,803评论 0赞 2
  • 红黑树深入剖析及Java实现(转)
    红黑树是平衡二叉查找树的一种。为了深入理解红黑树，我们需要从二叉查找树开始讲起。 BST 二叉查找树（Binary...
    kanehe阅读 1,406评论 0赞 8
  • 换个角度彻底理解红黑树
    0 、前言 红黑树是软件工程中非常重要的数据结构，在很多的工程领域都有它的身影，比如java的treemap、li...
    小龙的城堡阅读 3,512评论 5赞 68
  • MarkDown
    1. 简介 1.1 什么是 MyBatis ？ MyBatis 是支持定制化 SQL、存储过程以及高级映射的优秀的...
    笨鸟慢飞阅读 5,877评论 0赞 4
  • 红黑树
    引自：https://zhuanlan.zhihu.com/p/24367771Java代码实现 红黑树是平衡二叉...
    Magic11阅读 235评论 0赞 0