1、红黑树与2-3树
2、树的绝对平衡性
2-3树在添加结点的时候，新的结点永远不会添加到空的位置，而只会我们最后找到的叶子结点做融合。 1）对于根结点是4结点的时候（4结点一个结点内有3个元素，2-3树每个结点只能有1或2个元素），我们可以直接将4结点分为一颗子树（由3个2结点组成的树，即每个结点只有一个元素）。 2）对于叶子结点来说，如果该叶子结点因为添加一个元素，从3结点变成4结点，我们先将该结点拆分为由3个2结点组成的树，再将这颗树的根结点与其父节点融合成为一个3结点（如果父结点原来只有一个元素）。这样才能保证2-3树的绝对平衡性！ 3）在2）中，如果拆分的树的根结点的父结点原来有2个元素，根结点同样融合到父亲结点后，父亲结点成为一个4结点，我们将这个4结点进行分裂，如下： 2-3树插入的规律如下：
3、红黑树与2-3树的等价性
4、红黑树的基本性质与复杂度分析
5、保持根结点为黑色和左旋转 + 颜色翻转和右旋转
红黑树添加结点的规则： 1）在添加红黑树的根结点的时候，我们首先添加红色结点，因为红黑树的根结点必须是黑色，我们需要将根结点变为红色；（对应2-3树中添加一个根结点） 2）需要将根结点变为黑色，这种情况在添加结点的时候（不止是添加根结点）是普遍存在的！ 3）添加的新结点（非根结点）在红黑树中**（左子树为空，右子树可以为空或者黑色结点）的黑色结点的左侧**，直接添加即可，表示2-3树的3结点。（对应2-3树中将元素添加到一个2结点，使得2结点变为3结点）。注意，此处黑色结点也可以是红色的，对应2个偏向左侧的红色结点，其实就是对应下面（6）的情况，我们再按下面（6的情u况处理即可！） 4）添加的新结点（非根结点）在红黑树中**（右子树为空，左子树为空或者黑色结点）的黑色结点的右侧**，此时不满足红黑树的性质（红黑树中所有的红色结点都在左侧），此时需要进行左旋转。（对应2-3树中将元素添加到一个2结点，使得2结点变为3结点）。注意，此处黑色结点也可以是红色的，左旋转后对应2个偏向左侧的红色结点，其实就是对应下面（6）的情况，我们再按下面（6的情况处理即可！）。 5）如果添加的新结点在黑色结点的右侧，而此时黑色结点左侧还有一个红色结点，添加之前，源节点对应2-3树中3结点，添加后，黑色结点左右两侧都是红色结点，对应2-3树的4结点。此时，2-3树需要将4结点拆分为子树，而红黑树中我们需要进行颜色翻转。 6）如果添加的新结点在黑色结点的左侧红色结点的左侧，此时黑色结点左侧为红色结点，黑色结点右侧是黑色结点，这样在2-3树中表示往3结点添加一个元素，时期变为4结点。同样要将4结点拆分为子树，红黑树中，我们则需要对黑色结点进行右旋转（顺时针）。
6、红黑树中添加新的元素 上面少说一种情况，就是在红色结点的右边添加新的红色结点： 红黑树的各类情况处理方法： 我们在红黑树中进行平衡维护的时候，如上图，应该从左到右进行判断： 1）如果当前结点的右孩子结点为红色（当前结点可以是红色(2-3树4结点)，也可以是黑色(2-3树3结点)），且左孩子结点为黑色，则将当前结点左旋转； 2）如果当前结点的左孩子以及左孩子的左孩子都是红色的，则对当前结点进行右旋转； 3）如果当前结点的左右孩子都是红色，则进行颜色翻转； 4）对于另外2种对应2-3树中3结点的情况，黑节点左孩子为红结点，右孩子为黑结点，不需要操作；黑结点右孩子为红结点，左孩子为黑结点，包含在（1）中；
红黑树的代码如下：
package com.lkj; import java.util.ArrayList; /** 红黑树也是基于二分搜索树实现的！ */ public class RBTree<K extends Comparable<K>, V> { //为了避免记红色与黑色的Boolean值，定义2个厂里 public static final boolean RED = true; public static final boolean BLACK = false; private class Node{ public K key; public V value; public Node left, right; public boolean color;//用于表示结点的颜色 public Node(K key, V value){ this.key = key; this.value = value; left = null; right = null; /** 初始化一个结点的颜色为红色：由于2-3树在添加结点的时候，新的结点永远不会添加到空的位置，而只会我们最后找到的叶子结点做融合。 我们新添加一个结点的时候，这个结点总要与某一个叶子结点进行融合（如果这个结点不是树的第一个结点）成为一个新的3/4结点， 而红黑树中，红色结点表示它与他的父亲结点进行融合。 即新添加的结点始终是要和某个结点进行融合，那么我们将新添加的结点设置为红色！代表新结点要在红黑树中对应的2-3树中的某一个结点进行融合！ */ color = RED; } } private Node root; private int size; public RBTree(){ root = null; size = 0; } //-------------------------------------------------------------辅助函数 // 判断节点node的颜色 private boolean isRed(Node node) { //如果结点为null，定义它是黑色的，那么返回BLACK=false，不是红色 if(node == null) return BLACK; return node.color;//否则，直接返回node的颜色：RED=true表示是红色；BLACK=false表示不是红色 } // node x // / \ 左旋转 / \ // T1 x ---------> node T3 // / \ / \ // T2 T3 T1 T2 //当心添加的结点（红色）添加到叶子结点的右侧，需要对该叶子结点进行左旋转（逆时针） //此处x为新添加结点，而node为x的父节点 private Node leftRotate(Node node) { Node x = node.right; //左旋转 node.right = x.left; x.left = node; //改变node与x颜色 x.color = node.color; node.color = RED; return x; } // node x // / \ 右旋转 / \ // x T2 -------> y node // / \ / \ // y T1 T1 T2 private Node rightRotate(Node node) { Node x = node.left; //右旋转 node.left = x.right; x.right = node; //维护颜色 x.color = node.color; node.color = RED; return x; } //颜色翻转:Node为黑色，其左节点为红色，新添加的红色结点在其右侧 private void flipColors(Node node) { node.color = RED; node.left.color = BLACK; node.right.color = RED; } //------------------------------------------------------------ public int getSize(){ return size; } public boolean isEmpty(){ return size == 0; } //------------------------------------------添加 public void add(K key, V value){ root = add(root, key, value); root.color = BLACK;// 1、必须将最终根节点设置为黑色节点 } private Node add(Node node, K key, V value) { if(node == null){ size ++; return new Node(key, value);//默认插入红色结点 } if(key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if(key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; /** 以当前结点为根的树添加完结点后，需要对当前结点进行红黑树的维护。 注意，下面3个过程包含我们之前分析的5类特殊情况（根结点为黑色我们在上面维护）， 且这几个过程不是互斥的，有可能都执行，而且顺序不可变。 这整个过程会从底层向上传递，不断维护红黑树的性质 */ //当前结点为黑色或者红色，右节点为红色，左结点为黑色，将当前结点左旋转 if(isRed(node.right) && !isRed(node.left)) node = leftRotate(node);//注意将旋转后新的根结点赋予node //当前结点的左孩子，以及左孩子的左孩子都是红色，将当前结点右旋转 if(isRed(node.left) && isRed(node.left.left)) node = rightRotate(node);//注意将旋转后新的根结点赋予node //当前结点的左右孩子都是红色，将当前结点进行颜色交换 if(isRed(node.left) && isRed(node.right)) flipColors(node); return node; } //------------------------------------------ private Node getNode(Node node, K key){ if(node == null) return null; if(key.equals(node.key)) return node; else if(key.compareTo(node.key) < 0) return getNode(node.left, key); else // if(key.compareTo(node.key) > 0) return getNode(node.right, key); } public boolean contains(K key){ return getNode(root, key) != null; } public V get(K key){ Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue){ Node node = getNode(root, key); if(node == null) throw new IllegalArgumentException(key + " doesn't exist!"); node.value = newValue; } private Node minimum(Node node){ if(node.left == null) return node; return minimum(node.left); } private Node removeMin(Node node){ if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } public V remove(K key){ Node node = getNode(root, key); if(node != null){ root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key){ if( node == null ) return null; if( key.compareTo(node.key) < 0 ){ node.left = remove(node.left , key); return node; } else if(key.compareTo(node.key) > 0 ){ node.right = remove(node.right, key); return node; } else{ // key.compareTo(node.key) == 0 if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } // 待删除节点右子树为空的情况 if(node.right == null){ Node leftNode = node.left; node.left = null; size --; return leftNode; } Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } } public static void main(String[] args) { System.out.println("Pride and Prejudice"); ArrayList<String> words = new ArrayList<>(); if(FileOperation.readFile("pride-and-prejudice.txt", words)) { System.out.println("Total words: " + words.size()); RBTree<String, Integer> map = new RBTree<>(); for (String word : words) { if (map.contains(word)) map.set(word, map.get(word) + 1); else map.add(word, 1); } System.out.println("Total different words: " + map.getSize()); System.out.println("Frequency of PRIDE: " + map.get("pride")); System.out.println("Frequency of PREJUDICE: " + map.get("prejudice")); } System.out.println(); } }7、红黑树的性能分析与测试 红黑树的添加/删除操作对比AVL要更加好，而由于红黑树的高度最高是2logn，而AVL树是logn级别，因此查询操作AVL树优于红黑树。 红黑树与AVL树的性能比较，参考：添加链接描述
8、更多和红黑树相关的问题
