【数据结构】红黑树完整代码

ゞ浴缸里的玫瑰 2022-10-23 11:11 159阅读 0赞

### 红黑树完整代码 ###

*  二叉树 - BinaryTree.java
 *  二叉搜索树 - BSTree.java
 *  平衡二叉搜索树 - BBSTree.java
 *  AVL树 - AVLTree.java
 *  红黑树 - RBTree.java

# 二叉树 - BinaryTree.java #

二叉树类是抽取了其他二叉树（BST，BBST，RBTree）的公共的属性与方法，本身并没有具体用途，所以也不存在添加元素、删除元素等方法。

@SuppressWarnings("unchecked")
    public class BinaryTree<E> implements BinaryTreeInfo {
        
        protected int size;         // 节点个的数量
        protected Node<E> root;     // 根节点
    
        /**
         * 访问规则抽象类；
         * 自定义元素访问规则，
         * 用来控制遍历访问元素时的行为与如何停止
         */
        public static abstract class Visitor<E> {
        
            private boolean stop;
    
            /**
             * @return 如果返回true，就代表停止遍历
             */
            public abstract boolean visit(E element);
        }
    
        /**
         * 节点类
         */
        protected static class Node<E> {
        
            E element;      // 元素值
            Node<E> left;   // 左子节点
            Node<E> right;  // 右子节点
            Node<E> parent; // 父节点
    
            public Node(E element, Node<E> parent) {
        
                this.element = element;
                this.parent = parent;
            }
    
            public boolean isLeaf() {
               // 是否为叶子节点
                return left == null && right == null;
            }
    
            public boolean isLeftChild() {
          // 是否为左子节点
                return parent != null && this == parent.left;
            }
    
            public boolean isRightChild() {
          // 是否为右子节点
                return parent != null && this == parent.right;
            }
    
            // 兄弟节点
            public Node<E> sibling() {
        
                // 如果是左子树，返回它的兄弟节点右子树
                if (isLeftChild()) return parent.right;
                // 如果是右子树，返回它的兄弟节点左子树
                if (isRightChild()) return parent.left;
                // 既不是左子树也不是右子树，说明没有兄弟节点，返回null
                return null;
            }
    
            // 叔父节点
            // node.parent.sibling()
        }
    
        @Override
        public Object root() {
        
            return this.root;
        }
    
        @Override
        public Object left(Object node) {
        
            return ((Node<E>) node).left;
        }
    
        @Override
        public Object right(Object node) {
        
            return ((Node<E>) node).right;
        }
    
        @Override
        public Object string(Object node) {
        
            return node;
        }
    
        /**
         * 创造节点
         * AVL树 与 B树 的节点各自有其特性
         * 因此在 BinaryTree 中提供一个方法让他们去重新
         */
        protected Node<E> createNode(E element, Node<E> parent) {
        
            return new Node<>(element, parent);
        }
    
    
        /**
         * 元素的数量
         */
        public int size() {
        
            return size;
        }
    
    
        /**
         * 是否为空
         */
        public boolean isEmpty() {
        
            return size == 0;
        }
    
        /**
         * 清空所有元素
         */
        public void clear() {
        
            root = null;
            size = 0;
        }
    
    
        /**
         * 前序遍历（递归）
         */
        public void preorderTraversalRecursion(Visitor<E> visitor) {
        
            if (visitor == null) return;
            preorderTraversalRecursion(root, visitor);
        }
    
        private void preorderTraversalRecursion(Node<E> node, Visitor<E> visitor) {
        
            if (node == null || visitor.stop) return;
    
            visitor.stop = visitor.visit(node.element);
            preorderTraversalRecursion(node.left, visitor);
            preorderTraversalRecursion(node.right, visitor);
        }
    
        /**
         * 前序遍历（迭代）
         */
        public void preorderTraversal(Visitor<E> visitor) {
        
            if (root == null || visitor == null) return;
    
            Stack<Node<E>> stack = new Stack<>();
            Node<E> node = root;
            while (!stack.isEmpty() || node != null) {
        
                if (node != null) {
        
                    if (visitor.visit(node.element)) return;
                    stack.push(node);
                    node = node.left;
                } else {
        
                    node = stack.pop();
                    node = node.right;
                }
            }
        }
    
        /**
         * 中序遍历（递归）
         */
        public void inorderTraversalRecursion(Visitor<E> visitor) {
        
            if (visitor == null) return;
            inorderTraversalRecursion(root, visitor);
        }
    
        private void inorderTraversalRecursion(Node<E> node, Visitor<E> visitor) {
        
            if (node == null || visitor.stop) return;
    
            inorderTraversalRecursion(node.left, visitor);
            if (visitor.stop) return;
            visitor.stop = visitor.visit(node.element);
            inorderTraversalRecursion(node.right, visitor);
        }
    
    
        /**
         * 中序遍历（迭代）
         */
        public void inorderTraversal(Visitor<E> visitor) {
        
            if (root == null || visitor == null) return;
    
            Stack<Node<E>> stack = new Stack<>();
            Node<E> node = root;
            while (!stack.isEmpty() || node != null) {
        
                //这是模拟递归的调用
                if (node != null) {
         // 如果当前节点不为null，就不断往左节点方向走，
                    stack.push(node); // 每走一次就将当前节点保存到栈中
                    node = node.left;
                } else {
         // 如果当前节点为null，说明左边走到头了，
                    node = stack.pop(); // 然后从栈中弹出节点，并赋给当前节点node
                    if (visitor.visit(node.element)) return;
                    node = node.right; //然后转向当前节点的右边节点，继续上面整个过程
                }
            }
        }
    
    
        /**
         * 后序遍历（递归）
         */
        public void postorderTraversalRecursion(Visitor<E> visitor) {
        
            if (visitor == null) return;
            postorderTraversalRecursion(root, visitor);
        }
    
        private void postorderTraversalRecursion(Node<E> node, Visitor<E> visitor) {
        
            if (node == null || visitor.stop) return;
    
            postorderTraversalRecursion(node.left, visitor);
            postorderTraversalRecursion(node.right, visitor);
            if (visitor.stop) return;
            visitor.stop = visitor.visit(node.element);
    
        }
    
    
        /**
         * 后序遍历（迭代）双栈实现
         */
        public void postorderTraversal(Visitor<E> visitor) {
        
            if (root == null || visitor == null) return;
    
            Stack<Node<E>> s1 = new Stack<>();
            Stack<Node<E>> s2 = new Stack<>();
            Node<E> node = root;
            s1.push(node);
            while (!s1.isEmpty()) {
        
                node = s1.pop();
                s2.push(node);
                if (node.left != null) {
        
                    s1.push(node.left);
                }
                if (node.right != null) {
        
                    s1.push(node.right);
                }
            }
            while (!s2.isEmpty()) {
        
                node = s2.pop();
                if (visitor.visit(node.element)) return;
            }
        }
    
    
        /**
         * 层序遍历（队列实现）
         */
        /*
        层序遍历（Level Order Traversal）
        从上到下、从左到右依次访问每一个节点
        实现思路：使用队列，先入队列
            1.将根节点入队
            2.循环执行以下操作，直到队列为空
                将队头节点 top 出队，进行访问
                将 top 的左子节点入队
                将 top 的右子节点入队
         */
        public void levelOrderTraversal(Visitor<E> visitor) {
        
            if (root == null || visitor == null) return;
    
            Queue<Node<E>> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                Node<E> node = queue.poll();
                if (visitor.visit(node.element)) return;
                if (node.left != null) {
        
                    queue.offer(node.left);
                }
                if (node.right != null) {
        
                    queue.offer(node.right);
                }
            }
        }
    
    
        /**
         * 求树的高度（递归）
         */
        public int treeHeightRecursive() {
        
            return heightRecursive(root);
        }
    
        /*
         节点的高度 = 最大子节点高度（左子节点或右子节点的最大值） + 1
         根节点的高度 就等于 树的高度
         叶子节点的高度 = 1
         空节点的高度 = 0
         */
        private int heightRecursive(Node<E> node) {
        
            if (node == null) return 0;
            return 1 + Math.max(heightRecursive(node.left), heightRecursive(node.right));
        }
    
        /**
         * 求树的高度（迭代）
         */
        public int treeHeightIterative() {
        
            if (root == null) return 0;
            // 树的高度
            int treeHeight = 0;
            // 存储着每一层的节点数量
            int levelSize = 1;
            Queue<Node<E>> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                // 每从队列中，出队一个节点，levelSize就减一
                Node<E> node = queue.poll();
                levelSize--;
    
                if (node.left != null) {
        
                    queue.offer(node.left);
                }
                if (node.right != null) {
        
                    queue.offer(node.right);
                }
                if (levelSize == 0) {
         // 意味着即将要访问下一层
                    // 因为每出队一个节点，都会将它的左右子节点 加入到队列
                    // 所以 下一层的节点数 = 队列中节点的数
                    levelSize = queue.size();
                    treeHeight++;  // 意味着即将要访问下一层，所以treeHeight加一
                }
    
            }
            return treeHeight;
        }
    
        /**
         * 前驱节点：中序遍历时的前一个节点
         */
        protected Node<E> predecessor(Node<E> node) {
        
            if (node == null) return node;
            // 前驱节点在左子树当中（left.right.right.right....）
            Node<E> pre = node.left;
            if (pre != null) {
        
                while (pre.right != null) {
        
                    pre = pre.right;
                }
                return pre;
            }
            // 从父节点、祖父节点中寻找前驱节点
            while (node.parent != null && node == node.parent.left) {
        
                node = node.parent;
            }
            // 当循环结束，说明有两种情况
            // 1、node.parent == null 当前节点的父节点为空
            // 2、node == node.parent.right 当前节点是该父节点的右子节点
            return node.parent;
        }
    
        /**
         * 后继节点：中序遍历时的后一个节点
         * 后继节点和前驱节点是对称的
         */
        protected Node<E> successor(Node<E> node) {
        
            if (node == null) return null;
    
            // 后继节点在右子树当中（right.left.left.left....）
            Node<E> post = node.right;
            if (post != null) {
        
                while (post.left != null) {
        
                    post = post.left;
                }
                return post;
            }
    
            // 从父节点、祖父节点中寻找后继节点
            while (node.parent != null && node == node.parent.right) {
        
                node = node.parent;
            }
            return node.parent;
        }
    
        /**
         * 是否是完全二叉树
         */
        public boolean isComplete() {
        
            if (root == null) return false;
            Queue<Node<E>> queue = new LinkedList<>();
            queue.offer(root);
            boolean leaf = false;
            while (!queue.isEmpty()) {
        
                Node<E> node = queue.poll();
                // leaf=true，若当前节点不是叶子节点，返回false
                if (leaf && !node.isLeaf()) return false;
    
                if (node.left != null) {
        
                    queue.offer(node.left);
                } else if (node.right != null) {
         // 来到这里，说明左节点为空，即node.left == null && node.right != null
                    return false;
                }
    
                if (node.right != null) {
        
                    queue.offer(node.right);
                } else {
         // 来到这里，说明右节点为空 node.right == null，
                    // 只要当前节点的右子节点为空，说明后面的节点都要是叶子节点，才是完全二叉树
                    leaf = true;
                }
            }
            return true;
        }
    
    
    }

# 二叉搜索树 - BSTree.java #

之前已经有一篇文章介绍了，[二叉搜索树详细代码][Link 1]

@SuppressWarnings("unchecked")
    public class BST<E> extends BinaryTree<E> {
        
        private Comparator<E> comparator;
    
        public BST() {
        
            this(null);
        }
    
        public BST(Comparator<E> comparator) {
        
            this.comparator = comparator;
        }
    
        /**
         * 辅助方法
         * 通过元素值获取对应节点
         */
        private Node<E> getNode(E element) {
        
            Node<E> node = root;
            while (node != null) {
        
                // 传入的值与当前节点的值比较
                int cmp = compare(element, node.element);
                if (cmp == 0) return node; // 相等，返回当前节点
                if (cmp < 0) {
         // 往当前节点左子树找
                    node = node.left;
                } else {
         // 往当前节点右子树找
                    node = node.right;
                }
            }
            return null; // 没有找到该元素对应的节点
        }
    
        /**
         * 辅助方法
         * 检测传入元素值是否为null
         * 为null则抛出异常
         */
        private void elementNotNullCheck(E element) {
        
            if (element == null) {
        
                throw new IllegalArgumentException("element must not be null");
            }
        }
    
        /**
         * 返回值等于0，代表e1和e2相等,
         * 返回值大于0，代表e1大于e2,
         * 返回值小于0，代表e1小于e2
         */
        private int compare(E e1, E e2) {
        
            if (this.comparator != null) {
        
                return comparator.compare(e1, e2);
            }
            // BST的节点元素必须具备可比较性
            // 如果强转失败，说明是BST的元素有问题，不具备可比较性
            return ((Comparable<E>) e1).compareTo(e2);
        }
    
        /**
         * 是否包含某元素
         */
        public boolean contains(E element) {
        
            return getNode(element) != null;
        }
    
        /**
         * 添加元素
         */
        public void add(E element) {
        
            elementNotNullCheck(element);
            // 添加第一个节点
            if (root == null) {
        
                //root = new Node<>(element, null);
                root = createNode(element, null);
                size++;
                afterAdd(root);// 新添加节点之后的处理
                return;
            }
            // 添加的不是第一个节点
            // 找到父节点
    
            // 假设当前节点为根节点，父节点也是跟节点
            Node<E> node = root;
            Node<E> parent = null;
            int cmp = 0; //记录最后一次比较结果
            do {
        
                cmp = compare(element, node.element); //记录最后一次比较结果
                parent = node; //记录父节点
                if (cmp > 0) {
         //插入的节点 大于 当前节点，就往当前节点的右节点走
                    node = node.right;
                } else if (cmp < 0) {
         //插入的节点 小于 当前节点，就往当前节点的左节点走
                    node = node.left;
                } else {
         // 插入的节点 等于 当前节点，就用插入节点的值替换当前节点的值
                    node.element = element;
                    return;
                }
                //当node==null退出循环，需要记录上一个节点，即父节点就是node==null之前的那个节点
            } while (node != null);
    
            // 当走到这里，说明已经退出循环，即当前节点node==null
            // 找到了要插入的位置，当前节点的位置就是要插入新节点的位置，所以用父节点指向新节点即可
            // 看看插入到父节点的哪个位置
            //Node<E> newNode = new Node<>(element, parent);
            Node<E> newNode = createNode(element, parent);
            if (cmp > 0) {
        
                parent.right = newNode;
            } else {
        
                parent.left = newNode;
            }
            size++;
            // 新添加节点之后的处理
            afterAdd(newNode);
        }
    
    
        /**
         * 删除元素
         */
        public void remove(E element) {
        
            remove(getNode(element));
        }
    
        /**
         * 删除节点
         */
        protected void remove(Node<E> node) {
        
            if (node == null) return;
    
            // 删除度为2的节点
            if (node.left != null && node.right != null) {
        
                // 找到该节点的前驱 或 后继节点
                Node<E> s = super.successor(node); //Node<E> s = predecessor(node);
                // 用后继节点的值覆盖度为2的节点的值
                node.element = s.element;
                // 删除后继节点（前驱、后继一定是度为0或1的节点）
                // 将node指向后继节点，删除node就相当于删除后继节点
                node = s;
            }
    
            // 删除node节点（node的度必然是1或者0）
            // child是删除的节点的子节点
            Node<E> child = node.left != null ? node.left : node.right;
    
            if (child != null) {
         // 度为1的节点
                // 更改child的parent
                child.parent = node.parent;
                // 更改parent的left、right的指向
                if (node.parent == null) {
         // node是度为1的节点并且是根节点
                    root = child;
                } else if (node == node.parent.left) {
         // node是度为1的节点，不是根节点
                    node.parent.left = child;
                } else {
         // node == node.parent.right
                    node.parent.right = child;
                }
                // 删除节点之后的处理
                afterRemove(child); // 传入被删除节点的子节点
    
            } else if (node.parent == null) {
         // node是叶子节点并且是根节点
                root = null;
    
                // 删除节点之后的处理
                afterRemove(node);
            } else {
         // node是叶子节点，但不是根节点
                if (node == node.parent.left) {
        
                    node.parent.left = null;
                } else {
         // node == node.parent.right
                    node.parent.right = null;
                }
    
                // 删除节点之后的处理
                afterRemove(node);
            }
    
            size--; //节点个数减一
        }
    
    
        /**
         * 添加node之后的调整
         *
         * @param node 新添加的节点
         */
        protected void afterAdd(Node<E> node) {
        
        }
    
        /**
         * 删除node之后的调整
         *
         * @param node 被删除的节点 或者 用以取代被删除节点的子节点（当被删除节点的度为1）
         */
        protected void afterRemove(Node<E> node) {
        
        }
    
    
    }

# 平衡二叉搜索树 - BBSTree.java #

这里的平衡二叉树类也只是为了抽取出公共代码，后面的 AVL树 与 B树 会继承它。

/**
     * 平衡二叉树搜索树
     */
    public class BBST<E> extends BST<E> {
        
    
        public BBST() {
        
            this(null);
        }
    
        public BBST(Comparator<E> comparator) {
        
            super(comparator);
        }
    
        /**
         * 统一所有旋转
         *
         * @param r             当前子树的根节点
         * @param a,b,c,d,e,f,g 从小到大一次排序的节点
         */
        protected void rotate(
                Node<E> r,
                Node<E> a, Node<E> b, Node<E> c,
                Node<E> d,
                Node<E> e, Node<E> f, Node<E> g) {
        
    
            // 让d成为这棵子树的根节点
            d.parent = r.parent;
            if (r.isLeftChild()) {
        
                r.parent.left = d;
            } else if (r.isRightChild()) {
        
                r.parent.right = d;
            } else {
        
                root = d;
            }
    
            // a-b-c
            b.left = a;
            if (a != null) a.parent = b;
    
            b.right = c;
            if (c != null) c.parent = b;
    
            // e-f-g
            f.left = e;
            if (e != null) e.parent = f;
    
            f.right = c;
            if (g != null) g.parent = f;
    
            // b-d-f
            d.left = b;
            d.right = f;
            b.parent = d;
            f.parent = d;
        }
    
        /**
         * 左旋转
         */
        protected void rotateLeft(Node<E> grand) {
        
            Node<E> parent = grand.right;
            Node<E> child = parent.left;
            grand.right = child;
            parent.left = grand;
    
            afterRotate(grand, parent, child);
        }
    
        /**
         * 右旋转
         */
        protected void rotateRight(Node<E> grand) {
        
            Node<E> parent = grand.left;
            Node<E> child = parent.right;
            grand.left = child;
            parent.right = grand;
    
            afterRotate(grand, parent, child);
        }
    
        /**
         * 公共代码：不管是左旋、右旋，都要执行的
         * @param grand 失衡节点
         * @param parent 失衡节点的tallerChild
         * @param child g和p需要交换的子树（本来是p的子树，后来会变成g的子树）
         */
        private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        
            // 维护T1、g、p的parent属性
            // 先让parent成为这颗子树的根节点
            parent.parent = grand.parent;
            // 并且判断grand是左子树,还有右子树
            if (grand.isLeftChild()) {
         // grand是左子树
                grand.parent.left = parent; // 将parent成为左子树
            } else if (grand.isRightChild()) {
        
                grand.parent.right = parent; // 将parent成为右子树
            } else {
         // 既不是左子树,也不是右子树,说明grand是root节点
                root = parent; // 将parent成为根节点
            }
    
            // 更新child的parent属性
            if (child != null) {
        
                child.parent = grand;
            }
            // 更新grand的parent属性
            grand.parent = parent;
    
        }
    
    }

# AVL树 - AVLTree.java #

AVL树在之前的文章中也单独记载过，[AVL树的代码][AVL]，这里主要是为了写红黑树，对很多代码进行了重构，AVL树中也有一些代码被抽取到BBST中。

/**
     * AVL树
     */
    @SuppressWarnings("unchecked")
    public class AVLTree<E> extends BBST<E> {
        
    	public AVLTree() {
        
    		this(null);
    	}
    	public AVLTree(Comparator<E> comparator) {
        
    		super(comparator);
    	}
    	
    	private static class AVLNode<E> extends Node<E> {
        
    		int height = 1; // AVL树中的节点，需要高度这个属性来计算平衡因子
    		
    		public AVLNode(E element, Node<E> parent) {
        
    			super(element, parent);
    		}
    		// 平衡因子
    		public int balanceFactor() {
        
    			int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    			int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    			return leftHeight - rightHeight;
    		}
    		// 更新高度
    		public void updateHeight() {
        
    			int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    			int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    			height = 1 + Math.max(leftHeight, rightHeight);
    		}
    		// 获取左右子树中，高度最长的节点
    		public Node<E> tallerChild() {
        
    			int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    			int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    			if (leftHeight > rightHeight) return left;
    			if (leftHeight < rightHeight) return right;
    			return isLeftChild() ? left : right;
    		}
    		@Override
    		public String toString() {
        
    			String parentString = "null";
    			if (parent != null) {
        
    				parentString = parent.element.toString();
    			}
    			return element + "_p(" + parentString + ")_h(" + height + ")";
    		}
    	}
    	/**
    	 * 是否平衡
    	 * 平衡因子的绝对值 <= 1 则平衡
    	 */
    	private boolean isBalanced(Node<E> node) {
        
    		return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
    	}
    	/**
    	 * 更新高度
    	 */
    	private void updateHeight(Node<E> node) {
        
    		((AVLNode<E>)node).updateHeight();
    	}
    	/**
    	 * 覆盖了BST中的afterAdd方法
    	 * BST中add以后无需调整，而AVL树需要恢复平衡和更新高度
    	 */
    	@Override
    	protected void afterAdd(Node<E> node) {
        
    		while ((node = node.parent) != null) {
         // 从当前节点探测根结点，逐个调整平衡
    			if (isBalanced(node)) {
         // 已经平衡
    				// 更新高度
    				updateHeight(node);
    			} else {
         // 不平衡
    				// 恢复平衡
    				rebalance(node);
    				// 只需要恢复了最下面那个不平衡的节点，则整棵树恢复平衡，无需继续往上探测
    				break;
    			}
    		}
    	}
    	
    	@Override
    	protected void afterRemove(Node<E> node) {
        
    		while ((node = node.parent) != null) {
         // 从当前节点探测根结点，逐个调整平衡
    			if (isBalanced(node)) {
         // 已经平衡
    				// 更新高度
    				updateHeight(node);
    			} else {
         // 不平衡
    				// 恢复平衡
    				rebalance(node);
    			}
    		}
    	}
    	
    	/**
    	 * AVL树的节点有其特性(height)，与BinaryTree.java中的节点不同
    	 */
    	@Override
    	protected Node<E> createNode(E element, Node<E> parent) {
        
    		return new AVLNode<>(element, parent);
    	}
    	
    	/**
    	 * 恢复平衡
    	 * @param grand 高度最低的那个不平衡节点
    	 */
    	/**
    	 * 恢复平衡
    	 * 利用“统一旋转”的代码
    	 * @param grand 高度最低的那个不平衡节点
    	 */
    	private void rebalance(Node<E> grand) {
         
    		Node<E> parent = ((AVLNode<E>)grand).tallerChild();
    		Node<E> node = ((AVLNode<E>)parent).tallerChild();
    		if (parent.isLeftChild()) {
         // L
    			if (node.isLeftChild()) {
         // LL
    				rotate(grand, node, node.right, parent, parent.right, grand);
    			} else {
         // LR
    				rotate(grand, parent, node.left, node, node.right, grand);
    			}
    		} else {
         // R
    			if (node.isLeftChild()) {
         // RL
    				rotate(grand, grand, node.left, node, node.right, parent);
    			} else {
         // RR
    				rotate(grand, grand, parent.left, parent, node.left, node);
    			}
    		}
    	}
    	/**
    	 * 恢复平衡
    	 * “左旋”与“右旋”分别进行
    	 * @param grand 高度最低的那个不平衡节点
    	 */
    	private void rebalance2(Node<E> grand) {
        
    		Node<E> parent = ((AVLNode<E>)grand).tallerChild();
    		Node<E> node = ((AVLNode<E>)parent).tallerChild();
    		if (parent.isLeftChild()) {
         // L
    			if (node.isLeftChild()) {
         // LL
    				rotateRight(grand);
    			} else {
         // LR
    				rotateLeft(parent);
    				rotateRight(grand);
    			}
    		} else {
         // R
    			if (node.isLeftChild()) {
         // RL
    				rotateRight(parent);
    				rotateLeft(grand);
    			} else {
         // RR
    				rotateLeft(grand);
    			}
    		}
    	}
    	
    	@Override
    	protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        
    		super.afterRotate(grand, parent, child);
    		
    		// 更新高度
    		updateHeight(grand);
    		updateHeight(parent);
    	}
    	
    	@Override
    	protected void rotate(Node<E> r, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f) {
        
    		super.rotate(r, b, c, d, e, f);
    		
    		// 更新高度
    		updateHeight(b);
    		updateHeight(f);
    		updateHeight(d);
    	}
    	
    }

# 红黑树 - RBTree.java #

/**
     * 红黑树
     */
    public class RBT<E> extends BBST<E> {
        
    
        private static final boolean RED = false;
        private static final boolean BLACK = true;
    
        public RBT() {
        
            this(null);
        }
    
        public RBT(Comparator<E> comparator) {
        
            super(comparator);
        }
    
        /**
         * 红黑树的节点类
         * 节点有颜色，RED 或者 BLACK
         */
        private static class RBTNode<E> extends Node<E> {
        
            boolean color;
    
            public RBTNode(E element, Node<E> parent) {
        
                super(element, parent);
            }
    
            @Override
            public String toString() {
        
                String str = "";
                if (color == RED) {
        
                    str = "R_";
                }
                return str + element.toString();
            }
        }
    
        @Override
        protected Node<E> createNode(E element, Node<E> parent) {
        
            return new RBTNode<>(element, parent);
        }
    
    
        /**
         * 添加有12种情况：
         * 新添加的节点（默认红色）
         *
         * 1、当parent是黑色，不做任何处理，添加完成后任是一棵红黑树。
         * 2、当parent不是黑色（为红色）：即当前节点和父节点都是红色的情况（double red）
         *      Ⅰ：其中4种为上溢的情况：【判定条件：uncle节点是红色】
         *          ①：上溢【LL】【RR】【LR】【RL】：
         *              将parent、uncle染成黑色，
         *              然后grand向上合并，
         *              并且将grand染成红色当作新节点处理【递归】；
         *              grand向上合并时，可能会继续发生上溢，
         *              若上溢到根节点，只需将根节点染成黑色。
         *      Ⅱ：其中4种为旋转的情况：【判定条件：uncle节点不是红色（是黑色）】
         *          ①：旋转【LL】【RR】
         *              将parent染成黑色，grand染成红色，
         *              然后对grand进行旋转，
         *                  若grand是LL的情况：右旋转，
         *                  若grand是RR的情况：左旋转。
         *          ②：旋转【LR】【RL】
         *              将自己染成黑色，grand染成红色，
         *              然后对grand进行旋转，
         *                  若grand是LR的情况：parent左旋转、grand右旋转，
         *                  若grand是RL的情况：parent右旋转、grand左旋转。
         *
         * @param node 新添加的节点（默认红色）
         */
        @Override
        protected void afterAdd(Node<E> node) {
        
    
            Node<E> parent = node.parent;
    
            // 添加的是根节点 或者 上溢到达了根节点
            if (parent == null) {
        
                black(node);
                return;
            }
            // 如果父节点是黑色，直接返回
            if (isBlack(parent)) return;
    
            // 叔父节点
            Node<E> uncle = parent.sibling();
            // 祖父节点
            Node<E> grand = parent.parent;
            if (isRed(uncle)) {
         // 叔父节点是红色【B树节点上溢】
                black(parent);
                black(uncle);
                // 把祖父节点当做是新添加的节点
                afterAdd(red(grand));
            } else {
         // 叔父节点不是红色【旋转】
                if (parent.isLeftChild()) {
         // L
                    if (node.isLeftChild()) {
         // LL
                        red(grand);
                        black(parent);
                        rotateRight(grand);
                    } else {
         // LR
                        red(grand);
                        black(node);
                        rotateLeft(parent);
                        rotateRight(grand);
                    }
                } else {
         // R
                    if (node.isLeftChild()) {
         // RL
                        red(grand);
                        black(node);
                        rotateRight(parent);
                        rotateLeft(grand);
                    } else {
         // RR
                        red(grand);
                        black(parent);
                        rotateLeft(grand);
                    }
                }
            }
    
        }
    
        @Override
        protected void afterRemove(Node<E> node) {
        
            // 如果删除的节点是红色
            // 或者 用以取代删除节点的子节点是红色
            if (isRed(node)) {
        
                black(node);
                return;
            }
    
            Node<E> parent = node.parent;
            // 删除的是根节点
            if (parent == null) return;
    
            // 删除的是黑色叶子节点【下溢】
            // 判断被删除的node是左还是右
            boolean left = (parent.left == null || node.isLeftChild());
            // 如果left为true，兄弟节点就是right，否则就是left
            Node<E> sibling = left ? parent.right : parent.left;
    
            if (left) {
         // 被删除的节点在左边，兄弟节点在右边
                if (isRed(sibling)) {
         // 兄弟节点是红色
                    black(sibling);
                    red(parent);
                    rotateLeft(parent);
                    // 更换兄弟
                    sibling = parent.right;
                }
    
                // 兄弟节点必然是黑色
                if (isBlack(sibling.left) && isBlack(sibling.right)) {
        
                    // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                    boolean parentBlack = isBlack(parent);
                    black(parent);
                    red(sibling);
                    if (parentBlack) {
        
                        afterRemove(parent);
                    }
                } else {
         // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                    // 兄弟节点的左边是黑色，兄弟要先旋转
                    if (isBlack(sibling.right)) {
        
                        rotateRight(sibling);
                        sibling = parent.right;
                    }
    
                    color(sibling, colorOf(parent));
                    black(sibling.right);
                    black(parent);
                    rotateLeft(parent);
                }
            } else {
         // 被删除的节点在右边，兄弟节点在左边
                if (isRed(sibling)) {
         // 兄弟节点是红色
                    black(sibling);
                    red(parent);
                    rotateRight(parent);
                    // 更换兄弟
                    sibling = parent.left;
                }
    
                // 兄弟节点必然是黑色
                if (isBlack(sibling.left) && isBlack(sibling.right)) {
        
                    // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                    boolean parentBlack = isBlack(parent);
                    black(parent);
                    red(sibling);
                    if (parentBlack) {
        
                        afterRemove(parent);
                    }
                } else {
         // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                    // 兄弟节点的左边是黑色，兄弟要先旋转
                    if (isBlack(sibling.left)) {
        
                        rotateLeft(sibling);
                        sibling = parent.left;
                    }
    
                    color(sibling, colorOf(parent));
                    black(sibling.left);
                    black(parent);
                    rotateRight(parent);
                }
            }
    
        }
    
        // 下面的是一些辅助方法
        /**
         * 对传入的节点染色，并返回染色后的该节点
         */
        private Node<E> color(Node<E> node, boolean color) {
        
            if (node == null) return node;
            ((RBTNode<E>) node).color = color;
            return node;
        }
    
        /**
         * 染成红色
         */
        private Node<E> red(Node<E> node) {
        
            return color(node, RED);
        }
    
        /**
         * 染成黑色
         */
        private Node<E> black(Node<E> node) {
        
            return color(node, BLACK);
        }
    
        /**
         * 判断当前节点是什么颜色
         * @return 返回 BLACK 或 RED
         */
        private boolean colorOf(Node<E> node) {
        
            // 如果节点是null，说明是空节点，返回black，否则返回节点本身的颜色
            return node == null ? BLACK : ((RBTNode<E>) node).color;
        }
    
        /**
         * 判断当前节点是否是黑颜色
         * @return true 或 false
         */
        private boolean isBlack(Node<E> node) {
        
            return colorOf(node) == BLACK;
        }
    
        /**
         * 判断当前节点是否是红颜色
         * @return true 或 false
         */
        private boolean isRed(Node<E> node) {
        
            return colorOf(node) == RED;
        }
    
    
    
    }

[Link 1]: https://blog.csdn.net/qq_32727095/article/details/112236842
[AVL]: https://blog.csdn.net/qq_32727095/article/details/112462399