红黑树 Java 完整实现

红黑树 Java 完整实现红黑树是一种自平衡二叉查找树通过 5 条核心规则保证树的高度始终接近 O (log n)查询 / 插入 / 删除效率极高。Java 的 TreeMap、TreeSet 底层就是红黑树。红黑树 5 大核心规则每个节点必须是红色或黑色根节点必须是黑色所有叶子节点空节点都是黑色如果一个节点是红色则它的两个子节点都是黑色不能有连续红节点从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点public class RedBlackTreeT extends ComparableT { // 颜色常量 private static final boolean RED false; private static final boolean BLACK true; // 树节点内部类 static class NodeT extends ComparableT { T value; NodeT left; NodeT right; NodeT parent; boolean color; public Node(T value) { this.value value; this.color RED; // 新插入节点默认红色 this.left null; this.right null; this.parent null; } } // 根节点 private NodeT root; // 1. 基础工具方法 // 获取祖父节点 private NodeT grandparent(NodeT node) { if (node null || node.parent null) return null; return node.parent.parent; } // 获取叔叔节点 private NodeT uncle(NodeT node) { NodeT grand grandparent(node); if (grand null) return null; return (node.parent grand.left) ? grand.right : grand.left; } // 2. 旋转操作核心 /** * 左旋以 x 为支点左旋 * x y * \ / * y → x */ private void leftRotate(NodeT x) { NodeT y x.right; x.right y.left; if (y.left ! null) { y.left.parent x; } y.parent x.parent; if (x.parent null) { root y; } else if (x x.parent.left) { x.parent.left y; } else { x.parent.right y; } y.left x; x.parent y; } /** * 右旋以 y 为支点右旋 * y x * / \ * x → y */ private void rightRotate(NodeT y) { NodeT x y.left; y.left x.right; if (x.right ! null) { x.right.parent y; } x.parent y.parent; if (y.parent null) { root x; } else if (y y.parent.right) { y.parent.right x; } else { y.parent.left x; } x.right y; y.parent x; } // 3. 插入后修复核心 private void fixInsert(NodeT node) { NodeT parent, grand, uncle; // 父节点是红色才需要修复 while (node ! root node.parent.color RED) { parent node.parent; grand grandparent(node); uncle uncle(node); // 情况 1父节点是左孩子 if (parent grand.left) { // 1.1 叔叔是红色 → 变色 if (uncle ! null uncle.color RED) { parent.color BLACK; uncle.color BLACK; grand.color RED; node grand; } // 1.2 叔叔是黑色当前节点是右孩子 → 左旋转成情况3 else { if (node parent.right) { node parent; leftRotate(node); parent node.parent; } // 1.3 叔叔是黑色当前节点是左孩子 → 右旋变色 parent.color BLACK; grand.color RED; rightRotate(grand); } } // 情况 2父节点是右孩子镜像处理 else { // 2.1 叔叔是红色 → 变色 if (uncle ! null uncle.color RED) { parent.color BLACK; uncle.color BLACK; grand.color RED; node grand; } // 2.2 叔叔是黑色当前节点是左孩子 → 右旋转成情况3 else { if (node parent.left) { node parent; rightRotate(node); parent node.parent; } // 2.3 叔叔是黑色当前节点是右孩子 → 左旋变色 parent.color BLACK; grand.color RED; leftRotate(grand); } } } // 强制根节点为黑色 root.color BLACK; } // 4. 插入节点 public void insert(T value) { if (value null) throw new IllegalArgumentException(value cannot be null); NodeT newNode new Node(value); NodeT parent null; NodeT current root; // 1. 二叉查找树插入逻辑 while (current ! null) { parent current; int cmp newNode.value.compareTo(current.value); if (cmp 0) { current current.left; } else if (cmp 0) { current current.right; } else { // 不允许重复值 return; } } newNode.parent parent; if (parent null) { root newNode; } else if (newNode.value.compareTo(parent.value) 0) { parent.left newNode; } else { parent.right newNode; } // 2. 修复红黑树性质 fixInsert(newNode); } // 5. 中序遍历验证有序性 public void inOrder() { inOrder(root); } private void inOrder(NodeT node) { if (node null) return; inOrder(node.left); System.out.print(node.value (node.color ? 黑 : 红 )); inOrder(node.right); } // 测试 public static void main(String[] args) { RedBlackTreeInteger tree new RedBlackTree(); // 插入测试数据 int[] arr {10, 20, 30, 15, 25, 5}; for (int num : arr) { tree.insert(num); } System.out.println(红黑树中序遍历节点颜色); tree.inOrder(); } }代码核心说明1. 节点结构存储值、左孩子、右孩子、父节点、颜色新节点默认红色最小化破坏红黑树规则2. 旋转操作左旋解决右子树过长问题右旋解决左子树过长问题旋转是红黑树保持平衡的核心手段3. 插入修复逻辑3 种情况叔叔为红色父 / 叔变黑祖父变红向上递归叔叔为黑色 节点是右孩子先左旋父节点叔叔为黑色 节点是左孩子右旋祖父节点 变色