一、Color类（节点颜色）

java">/*自定义一个枚举类型 Color，它所声明的变量只有REC和BLACK两种值，其必须使用Color.+值的方式进行赋值*/
public enum Color {RED,BLACK
}

二、Pair类（键值对）

java">/*** key-value 对象* @param <K> 键* @param <V> 值*/
public class Pair<K extends Comparable<K>,V>{public K key;public V value;public Pair() {}public Pair(K key, V value) {this.key = key;this.value = value;}@Overridepublic String toString() {return "Pair{" +"key=" + key +", value=" + value +'}';}
}

三、RBTNode类（红黑树节点）

java">/*** 红黑树节点（实现Map）*/
public class RBTNode <K extends Comparable<K>,V>{Pair<K,V> pair;// 节点值RBTNode<K,V> left;// 左节点RBTNode<K,V> right;// 右节点Color color;// 节点颜色public RBTNode() {}public RBTNode(Pair<K, V> pair) {this.pair = pair;this.color = Color.RED;}@Overridepublic String toString() {return "RBTNode{" +"pair=" + pair +", left=" + left +", right=" + right +", color=" + color +'}';}
}

四、RBT类（红黑树）

java">/*** 红黑树（实现Map）* @param <K> 键* @param <V> 值*/
public class RBT <K extends Comparable<K>,V>{public int size;// 节点数目/*** 获取树中的节点数目* @return*/public int getSize(){return this.size;}/*** 判断当前节点的颜色是否为红色* @param node 当前节点* @return 是否*/private boolean isRead(RBTNode node){if(node == null) return false;return node.color == Color.RED;}/*** 左旋当前节点并将新节点返回* @param node 当前节点* @return 新节点*/private RBTNode leftRotate(RBTNode node){RBTNode X = node.right;RBTNode T2 = X.left;node.right = T2;X.left = node;// 将旧节点颜色赋给新节点X.color = node.color;// 将红色赋给旧节点node.color = Color.RED;return X;}/*** 右旋当前节点并将新节点返回* @param node 当前节点* @return 新节点*/private RBTNode rightRotate(RBTNode node){RBTNode X = node.left;RBTNode T2 = X.right;node.left = T2;X.right = node;// 将旧节点颜色赋给新节点X.color = node.color;// 将旧节点的颜色变为红色node.color = Color.RED;return X;}/*** 赋值当前节点及左右节点的颜色* @param node*/private void reverseColor(RBTNode node){node.color = Color.RED;node.left.color = Color.BLACK;node.right.color = Color.BLACK;}/*** 在当前节点中插入值为pair的节点* @param node 当前节点* @param pair 节点值* @return 新节点*/public RBTNode<K,V> insert(RBTNode<K,V> node,Pair<K,V> pair){if(node ==  null){size++;return new RBTNode<>(pair);}if(pair.key.compareTo(node.pair.key) == 0){node.pair.value = pair.value;}else if(pair.key.compareTo(node.pair.key) < 0){node.left = insert(node.left, pair);}else{node.right = insert(node.right, pair);}// 调整节点位置和节点颜色// 三个顺序操作，即对当前节点都要进行的操作// 左旋操作if(isRead(node.right) && !isRead(node.left)){node = leftRotate(node);}// 右旋操作if(isRead(node.left) && isRead(node.left.left)){node = rightRotate(node);}// 颜色翻转if(isRead(node.left) && isRead(node.right)){reverseColor(node);}return node;}/*** 在当前节点中获取键为key的节点* @param node 当前节点* @param key 键值* @return 键为key的节点*/public RBTNode<K,V> get(RBTNode<K,V> node,K key){if(node == null) return null;if(key.compareTo(node.pair.key) == 0){return node;}else if(key.compareTo(node.pair.key) < 0){return get(node.left, key);}else{return get(node.right, key);}}/*** 中序遍历当前节点* @param node 当前节点*/public void inOrder(RBTNode node){if(node == null) return;inOrder(node.left);System.out.println(node.pair.key+":"+node.pair.value);inOrder(node.right);}
}

五、TestRBT（测试）

java">public class TestRBT {public static void main(String[] args) {RBT<Integer,Integer> tree = new RBT<>();RBTNode<Integer,Integer> root = null;root = tree.insert(root, new Pair<>(24, 244));root = tree.insert(root, new Pair<>(51, 511));root = tree.insert(root, new Pair<>(11, 111));root = tree.insert(root, new Pair<>(23, 233));root = tree.insert(root, new Pair<>(47, 477));root.color = Color.BLACK;tree.inOrder(root);System.out.println(tree.getSize());System.out.println(tree.get(root, 11));}
}