利用上班摸鱼时间，手撕红黑树（Java代码实现）

• • 操作术语
  • 代码实现
  • 测试验证

红黑树节点主要成员包括指向左孩子、右孩子、父节点的引用，一个boolean类型的变量标识是红或黑。
对于查询操作，跟二叉搜索树一样
插入、删除可能会影响红黑树的平衡，需要通过旋转和变色维护。

左旋逻辑：
设对节点p左旋，其目标为使节点p成为其右孩子节点的左孩子节点，操作为修改节点p和节点p的右孩子节点的父指针，再修改各自的孩子指针。

右旋逻辑：
设对节点p右旋，其目标为使节点p成为其左孩子节点的右孩子节点，操作为修改节点p和节点p的左孩子节点的父指针，再修改各自的孩子指针。

插入逻辑：

1. 找插入位置，要插入的节点肯定为叶子节点，且设置为红色
2. 判断其父节点颜色而做相应旋转以及变色操作

删除逻辑：

1. 要删除的节点有左孩子节点和右孩子节点，找其直接后继节点，交换位置，待替换的节点指向后继节点的右孩子节点（如果存在的话，否则指向自己）
2. 要删除的节点孩子节点仅有一个，替换节点即为其孩子节点
3. 要删除的节点没有孩子节点，替换节点指向自己
4. 如果替换节点不为删除节点，则将替换节点直接替换删除节点
5. 根据删除节点颜色，做平衡操作
6. 替换节点就是删除节点，修改指针引用，将其删除

图文并茂请参考https://blog.csdn.net/weixin_45685353/article/details/105912742?spm=1001.2014.3001.5502

import java.util.*;


public class RedBlackTree {

    private TreeNode root;
    private Comparator comparator;
    public RedBlackTree() {
    }

    public RedBlackTree(Comparator comparator) {
        this.comparator = comparator;
    }

    class TreeNode {
        private T val;
        private TreeNode left;
        private TreeNode right;

        private TreeNode parent;
        private boolean red;

        public TreeNode(T val) {
            this.val = val;
        }
    }

    public TreeNode find(T target) {
        TreeNode p = root;
        for (; p != null; ) {
            int dir = comparator == null ? ((Comparable) target).compareTo(p.val) : comparator.compare(target, p.val);
            if (dir < 0) {
                p = p.left;
            } else if (dir > 0) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    public void insert(T val) {
        TreeNode p = root, pp = null;
        int dir = 0;
        for (; p != null; ) {
            pp = p;
            dir = comparator == null ? ((Comparable) val).compareTo(p.val) : comparator.compare(val, p.val);
            if (dir < 0) {
                p = p.left;
            } else if (dir > 0) {
                p = p.right;
            } else {
                return;
            }
        }
        TreeNode node = new TreeNode(val);
        if (pp == null) {
            node.red = false;
            root = node;
            return;
        }
        if (dir < 0) {
            pp.left = node;
        } else {
            pp.right = node;
        }
        node.parent = pp;
        balanceInsert(node);
    }

    public List getInnerValues() {
        List list = new ArrayList<>();
        ArrayDeque stack = new ArrayDeque<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.addLast(p);
                p = p.left;
            }
            p = stack.removeLast();
            list.add(p.val);
            p = p.right;
        }
        return list;
    }

    public void remove(T target) {
        TreeNode t;
        if ((t = this.find(target)) == null) {
            return;
        }
        if (t == root && t.left == null && t.right == null) {
            root = null;
            return;
        }
        TreeNode tl = t.left, tr = t.right, replace;
        if (tl != null && tr != null) {
            TreeNode s = tr, sl;
            while ((sl = s.left) != null) {
                s = sl;
            }
            boolean c = t.red;
            t.red = s.red;
            s.red = c;
            TreeNode sr = s.right, tp = t.parent;
            if (tr == s) {
                t.parent = s;
                s.right = t;
            } else {
                TreeNode sp = s.parent;
                if ((t.parent = sp) != null) {
                    if (s == sp.left) {
                        sp.left = t;
                    } else {
                        sp.right = t;
                    }
                }
                s.right = tr;
                tr.parent = s;
            }
            t.left = null;
            if ((t.right = sr) != null) {
                sr.parent = t;
            }
            s.left = tl;
            tl.parent = s;
            if ((s.parent = tp) == null){
                root = s;
            } else if (t == tp.left) {
                tp.left = s;
            } else {
                tp.right = s;
            }
            if (sr != null) {
                replace = sr;
            } else {
                replace = t;
            }
        } else if (tl != null) {
            replace = tl;
        } else if (tr != null) {
            replace = tr;
        } else {
            replace = t;
        }
        if (replace != t) {
            TreeNode tp = replace.parent = t.parent;
            if (tp == null) {
                root = replace;
            } else if (tp.left == t) {
                tp.left = replace;
            } else {
                tp.right = replace;
            }
            t.left = t.right = t.parent = null;
        }
        if (!t.red) {
            balanceRemove(replace);
        }
        if (replace == t) {
            TreeNode tp = t.parent;
            t.parent = null;
            if (tp != null) {
                if (tp.left == t) {
                    tp.left = null;
                } else {
                    tp.right = null;
                }
            }
        }
    }

    private void balanceInsert(TreeNode t) {
        TreeNode tp, tpp, tppl, tppr;
        t.red = true;
        for (; ; ) {
            if ((tp = t.parent) == null) {
                t.red = false;
                return;
            }
            if (!tp.red || (tpp = tp.parent) == null) {
                return;
            }
            if ((tppl = tpp.left) == tp) {
                if ((tppr = tpp.right) != null && tppr.red) {
                    tppl.red = false;
                    tppr.red = false;
                    tpp.red = true;
                    t = tpp;
                } else {
                    if (t == tp.right) {
                        rotateLeft(t = tp);
                        tpp = (tp = t.parent) == null ? null : tp.parent;
                    }
                    if (tp != null) {
                        tp.red = false;
                        if (tpp != null) {
                            tpp.red = true;
                            rotateRight(tpp);
                        }
                    }
                }
            } else {
                if (tppl != null && tppl.red) {
                    tppl.red = false;
                    tp.red = false;
                    tpp.red = true;
                    t = tpp;
                } else {
                    if (t == tp.left) {
                        rotateRight(t = tp);
                        tpp = (tp = t.parent) == null ? null : tp.parent;
                    }
                    if (tp != null) {
                        tp.red = false;
                        if (tpp != null) {
                            tpp.red = true;
                            rotateLeft(tpp);
                        }
                    }
                }
            }
        }
    }

    private void balanceRemove(TreeNode t) {
        TreeNode tp, tpl, tpr;
        for (; ; ) {
            if (t == null || t == root) {
                return;
            } else if ((tp = t.parent) == null) {
                t.red = false;
                return;
            } else if (t.red) {
                t.red = false;
                return;
            } else if ((tpl = tp.left) == t) {
                if ((tpr = tp.right) != null && tpr.red) {
                    tpr.red = false;
                    tp.red = true;
                    rotateLeft(tp);
                    tpr = (tp = t.parent) == null ? null : tp.right;
                }
                if (tpr == null) {
                    t = tp;
                } else {
                    TreeNode sl = tpr.left, sr = tpr.right;
                    if ((sr == null || !sr.red) && (sl == null || !sl.red)) {
                        tpr.red = true;
                        t = tp;
                    } else {
                        if (sr == null || !sr.red) {
                            sl.red = false;
                            tpr.red = true;
                            rotateRight(tpr);
                            tpr = (tp = t.parent) == null ? null : tp.right;
                        }
                        if (tpr != null) {
                            tpr.red = tp != null && tp.red;
                            if ((sr = tpr.right) != null) {
                                sr.red = false;
                            }
                        }
                        if (tp != null) {
                            tp.red = false;
                            rotateLeft(tp);
                        }
                        t = root;
                    }
                }
            } else {
                if (tpl != null && tpl.red) {
                    tpl.red = false;
                    tp.red = true;
                    rotateRight(tp);
                    tpl = (tp = t.parent) == null ? null : tp.left;
                }
                if (tpl == null) {
                    t = tp;
                } else {
                    TreeNode sl = tpl.left, sr = tpl.right;
                    if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
                        tpl.red = true;
                        t = tp;
                    } else {
                        if (sl == null || !sl.red) {
                            sr.red = false;
                            tpl.red = true;
                            rotateLeft(tpl);
                            tpl = (tp = t.parent) == null ? null : tp.left;
                        }
                        if (tpl != null) {
                            tpl.red = tp != null && tp.red;
                            if ((sl = tpl.left) != null) {
                                sl.red = false;
                            }
                        }
                        if (tp != null) {
                            tp.red = false;
                            rotateRight(tp);
                        }
                        t = root;
                    }
                }
            }
        }
    }

    private void rotateLeft(TreeNode t) {
        TreeNode tr, trl, tp;
        // 左旋，成为其右子节点的左子节点
        if (t != null && (tr = t.right) != null) {
            // 修改父指针
            if ((tp = tr.parent = t.parent) == null) {
                tr.red = false;
                root = tr;
            } else if (tp.left == t) {
                tp.left = tr;
            } else {
                tp.right = tr;
            }
            // 修改子指针
            if ((trl = t.right = tr.left) != null) {
                trl.parent = t;
            }
            // 成为其右子节点的左子节点
            tr.left = t;
            t.parent = tr;
        }
    }

    private void rotateRight(TreeNode t) {
        TreeNode tl, tlr, tp;
        // 右旋，成为其左子节点的右子节点
        if (t != null && (tl = t.left) != null) {
            // 修改父指针
            if ((tp = tl.parent = t.parent) == null) {
                tl.red = false;
                root = tl;
            } else if (tp.left == t) {
                tp.left = tl;
            } else {
                tp.right = tl;
            }
            // 修改子指针
            if ((tlr = t.left = tl.right) != null) {
                tlr.parent = t;
            }
            // 成为其左子节点的右子节点
            tl.right = t;
            t.parent = tl;
        }
    }
}

测试类如下，

import com.bipa.tree.RedBlackTree;

import java.util.List;


public class Main {

    public static final int LOOP_NUM = 10_000;

    public static void main(String[] args) {
        RedBlackTree redBlackTree = new RedBlackTree<>();
        for (int i = LOOP_NUM; i > 0; i--) {
            redBlackTree.insert(i);
        }
        for (int i = LOOP_NUM; i > 0; i--) {
            // 获取红黑树中序遍历后的节点值
            List list = redBlackTree.getInnerValues();
            System.out.println(list);

            // 验证是否升序
            for (int j = 1; j < list.size(); j++) {
                if (list.get(j-1) > list.get(j)) {
                    // 发现降序，打印fail，结束方法
                    System.out.println("fail!");
                    return;
                }
            }
            redBlackTree.remove(i);
        }
        System.out.println("succ");
    }

}

运行结果截图，