5.2 向底部的2-结点插入新键
用和二叉查找树相同的方式向一棵红黑树中插入一个新键，会在树的底部新增一个结点（可以保证有序性），唯一区别的地方是我们会用红链接将新结点和它的父结点相连。如果它的父结点是一个2-结点，那么刚才讨论的两种方式仍然适用。
5.3 向一棵双键树(即一个3-结点)中插入新键
这种情况有可以分为三种子情况：
新键大于原树中的两个键
新键介于原数中两个键之间
5.4 向树底部的3-结点插入新键
假设在树的底部的一个3-结点下加入一个新的结点。前面我们所讲的3种情况都会出现。指向新结点的链接可能是 3-结点的右链接（此时我们只需要转换颜色即可），或是左链接(此时我们需要进行右旋转然后再转换)，或是中链接(此时需要先左旋转然后再右旋转，最后转换颜色)。颜色转换会使中间结点的颜色变红，相当于将它送入了父结点。这意味着父结点中继续插入一个新键，我们只需要使用相同的方法解决即可，直到遇到一个2-结点或者根结点为止。
6. 根结点的颜色总是黑色
之前我们介绍结点API的时候，在结点Node对象中color属性表示的是父结点指向当前结点的连接的颜色，由于根结点不存在父结点，所以每次插入操作后，我们都需要把根结点的颜色设置为黑色。
7. 红黑树的实现
7.1 红黑树的API设计
| 类名 | RedBlackTree, Value> |
| 构造方法 | RedBlackTree()：创建RedBlackTree对象 |
| 成员方法 | 1.private boolean isRed(Node x)：判断当前结点的父指向链接是否为红色 2.private Node rotateLeft(Node h):左旋调整 3.private Node rotateRight(Node h):右旋调整 4.private void flflipColors(Node h)：颜色反转,相当于完成拆分4-结点 5.public void put(Key key, Value val):在整个树上完成插入操作 6.private Node put(Node h, Key key, Value val):在指定树中，完成插入操作,并返回添加元素后新的树 7.public Value get(Key key):根据key，从树中找出对应的值 8.private Value get(Node x, Key key):从指定的树x中，找出key对应的值 9.public int size():获取树中元素的个数 |
| 成员变量 | 1.private Node root : 记录根结点 2.private int N:记录树中元素的个数 3.private static fifinal boolean RED：红色链接标识 4.private static fifinal boolean BLACK:黑色链接标识 |
7.2 代码
public class RedBlackTree<Key extends Comparable<Key>, Value> { //根节点 private Node root; //记录树中元素的个数 private int N; //红色链接 private static final boolean RED = true; //黑色链接 private static final boolean BLACK = false; //结点类 private class Node { //存储键 public Key key; //存储值 private Value value; //记录左子结点 public Node left; //记录右子结点 public Node right; //由其父结点指向它的链接的颜色 public boolean color; public Node(Key key, Value value, Node left, Node right, boolean color) { this.key = key; this.value = value; this.left = left; this.right = right; this.color = color; } } //获取树中元素的个数 public int size() { return N; } /** * 判断当前节点的父指向链接是否为红色 * * @param x * @return */ private boolean isRed(Node x) { if (x==null){ return false; } return x.color==RED; } /** * 左旋转 * * @param h * @return */ private Node rotateLeft(Node h) { //找到h结点的右子结点x Node x = h.right; //找到x结点的左子结点，让x结点的左子结点称为h结点的右子结点 h.right = x.left; //让h结点称为x结点的左子结点 x.left = h; //让x结点的color属性变为h结点的color属性 x.color = h.color; //让h结点的color属性变为RED h.color = RED; return x; } /** * 右旋 * * @param h * @return */ private Node rotateRight(Node h) { //找到h结点的左子结点 x Node x = h.left; //让x结点的右子结点成为h结点的左子结点 h.left = x.right; //让h结点成为x结点的右子结点 x.right = h; //让x结点的color属性变为h结点的color属性 x.color = h.color; //让h结点的color属性为RED h.color = RED; return x; } /** * 颜色反转,相当于完成拆分4-节点 * * @param h */ private void flipColors(Node h) { //当前结点变为红色 h.color = RED; //左子结点和右子结点变为黑色 h.left.color=BLACK; h.right.color = BLACK; } /** * 在整个树上完成插入操作 * * @param key * @param val */ public void put(Key key, Value val) { root = put(root,key,val); //根结点的颜色总是黑色 root.color = RED; } /** * 在指定树中，完成插入操作,并返回添加元素后新的树 * * @param h * @param key * @param val */ private Node put(Node h, Key key, Value val) { //判断h是否为空，如果为空则直接返回一个红色的结点就可以了 if (h == null){ //数量+1 N++; return new Node(key,val,null,null,RED); } //比较h结点的键和key的大小 int cmp = key.compareTo(h.key); if (cmp<0){ //继续往左 h.left = put(h.left,key,val); }else if (cmp>0){ //继续往右 h.right = put(h.right,key,val); }else{ //发生值的替换 h.value = val; } //进行左旋:当当前结点h的左子结点为黑色，右子结点为红色，需要左旋 if (isRed(h.right) && !isRed(h.left)){ h = rotateLeft(h); } //进行右旋：当当前结点h的左子结点和左子结点的左子结点都为红色，需要右旋 if (isRed(h.left) && isRed(h.left.left)){ rotateRight(h); } //颜色反转：当前结点的左子结点和右子结点都为红色时，需要颜色反转 if (isRed(h.left) && isRed(h.right)){ flipColors(h); } return h; } //根据key，从树中找出对应的值 public Value get(Key key) { return get(root,key); } //从指定的树x中，查找key对应的值 public Value get(Node x, Key key) { if (x == null){ return null; } //比较x结点的键和key的大小 int cmp = key.compareTo(x.key); if (cmp<0){ return get(x.left,key); }else if (cmp>0){ return get(x.right,key); }else{ return x.value; } } }
7.3 测试代码
public class RedBlackTreeTest { public static void main(String[] args) { //创建红黑树 RedBlackTree<String,String> tree = new RedBlackTree<>(); //往树中插入元素 tree.put("1","张三"); tree.put("2","李四"); tree.put("3","王五"); //从树中获取元素 String r1 = tree.get("1"); System.out.println(r1); String r2 = tree.get("2"); System.out.println(r2); String r3 = tree.get("3"); System.out.println(r3); } }
