Java 红黑树代码

以下是 Java 中实现红黑树的代码： ``` import java.util.Map; import java.util.TreeMap; public class RedBlackTree<K extends Comparable<K>, V> { private static final boolean RED = true; private 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; color = RED; } } private Node root; private int size; public RedBlackTree() { root = null; size = 0; } private boolean isRed(Node node) { if (node == null) return BLACK; return node.color; } private Node leftRotate(Node node) { Node x = node.right; node.right = x.left; x.left = node; x.color = node.color; node.color = RED; return x; } 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; } private void flipColors(Node node) { node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } public void add(K key, V value) { root = add(root, key, value); root.color = BLACK; } 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 node.value = value; if (isRed(node.right) && !isRed(node.left)) node = leftRotate(node); if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node); if (isRed(node.left) && isRed(node.right)) flipColors(node); return node; } public V get(K key) { Node node = root; while (node != null) { if (key.compareTo(node.key) < 0) node = node.left; else if (key.compareTo(node.key) > 0) node = node.right; else return node.value; } return null; }