数据结构——红黑树

在计算机科学中平衡二叉搜索树是许多高效数据结构的基础。红黑树Red-Black Tree作为一种自平衡二叉搜索树在保证操作时间复杂度为O(log n)的同时通过巧妙的颜色约束实现了相对较低的维护成本。本文将深入剖析红黑树的原理、核心操作并结合Java集合框架中的TreeMap源码带你彻底掌握这一经典数据结构。一、为什么需要红黑树二叉搜索树在极端情况下会退化为链表导致操作复杂度降至O(n)。为了保持平衡人们发明了多种平衡树如AVL树、红黑树等。与AVL树严格的高度平衡不同红黑树通过“近似平衡”来减少旋转次数从而在插入、删除频繁的场景下表现更优。Java的TreeMap、TreeSet以及HashMap中的链表树化当链表长度超过阈值时会将链表转换为红黑树都基于红黑树实现。二、红黑树的定义与性质红黑树是一棵满足以下五条性质的二叉搜索树每个节点是红色或黑色。根节点是黑色。每个叶子节点NIL节点即空节点是黑色。通常实现中我们用null代表叶子节点并认为其颜色为黑色。如果一个节点是红色则它的两个子节点都是黑色。这条性质保证了没有两个连续的红色节点。对于每个节点从该节点到其所有后代叶子节点的简单路径上均包含相同数目的黑色节点。这条性质称为“黑色平衡”它确保了红黑树的最长路径不超过最短路径的两倍从而保证了操作的时间复杂度为O(log n)。这些性质共同保证了红黑树的高度最多为2log₂(n1)因此查找、插入、删除的时间复杂度均为O(log n)。三、红黑树节点定义在Java中红黑树节点通常包含键、值、左子节点、右子节点、父节点以及颜色标记。以TreeMap中的Entry类为例javastatic final class EntryK,V implements Map.EntryK,V { K key; V value; EntryK,V left; EntryK,V right; EntryK,V parent; boolean color BLACK; // 默认为黑色 // 构造函数、getter、setter等省略 }四、核心操作旋转红黑树的插入和删除操作会破坏其性质需要通过重新着色和旋转来修复。旋转分为左旋和右旋它们是局部调整树结构的原子操作不会改变二叉搜索树的性质。左旋java// 左旋操作将节点p向右旋转使p的右子节点成为新的父节点 private void rotateLeft(EntryK,V p) { if (p ! null) { EntryK,V r p.right; p.right r.left; if (r.left ! null) r.left.parent p; r.parent p.parent; if (p.parent null) root r; else if (p.parent.left p) p.parent.left r; else p.parent.right r; r.left p; p.parent r; } }右旋java// 右旋操作将节点p向左旋转使p的左子节点成为新的父节点 private void rotateRight(EntryK,V p) { if (p ! null) { EntryK,V l p.left; p.left l.right; if (l.right ! null) l.right.parent p; l.parent p.parent; if (p.parent null) root l; else if (p.parent.right p) p.parent.right l; else p.parent.left l; l.right p; p.parent l; } }五、插入操作与修复插入新节点时我们首先按照二叉搜索树的规则找到插入位置然后将新节点染成红色这样不会破坏性质5但可能破坏性质4。如果父节点是黑色插入完成如果父节点是红色则出现连续红色需要根据叔叔节点的颜色进行修复。插入修复的三种情况假设新节点为z父节点为p祖父节点为g叔叔节点为u叔叔节点u是红色将p和u染黑g染红然后将z指向g继续向上修复。叔叔节点u是黑色且z是p的右子节点LL双红对p进行左旋转化为情况3然后按情况3处理。叔叔节点u是黑色且z是p的左子节点LR双红将p染黑g染红然后对g进行右旋。插入修复代码来自TreeMapjavaprivate void fixAfterInsertion(EntryK,V x) { x.color RED; while (x ! null x ! root x.parent.color RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { EntryK,V y rightOf(parentOf(parentOf(x))); if (colorOf(y) RED) { // 情况1叔叔为红色 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x parentOf(parentOf(x)); } else { if (x rightOf(parentOf(x))) { // 情况2当前节点是右孩子 x parentOf(x); rotateLeft(x); } // 情况3当前节点是左孩子 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { // 对称处理 // ... } } root.color BLACK; }六、删除操作与修复删除操作相对复杂。首先找到实际被删除的节点如果待删除节点有两个子节点则用后继节点替换然后转为删除后继节点。删除后如果被删除节点是黑色则会破坏性质5需要进行修复。删除修复的核心是处理“双黑”节点通过旋转和着色恢复平衡。修复过程根据兄弟节点的颜色和子节点的情况分为多种情形。由于篇幅所限这里只列出修复的主要思想具体可参考TreeMap中的fixAfterDeletion方法。七、红黑树 vs. AVL树特性红黑树AVL树平衡条件近似平衡最长路径不超过最短路径的两倍严格平衡左右子树高度差≤1查找效率O(log n)略逊于AVLO(log n)更严格查找更快插入/删除效率旋转次数少平均性能更好可能需要多次旋转但总体仍是O(log n)适用场景插入删除频繁如TreeMap、HashMap内部查找操作远多于插入删除的场景八、Java中的红黑树应用1. TreeMap和TreeSetTreeMap使用红黑树存储键值对所有操作put、get、remove都依赖于红黑树的算法。TreeSet则基于TreeMap实现只使用键。2. HashMap中的树化当HashMap中某个桶的链表长度超过TREEIFY_THRESHOLD默认8时会将链表转换为红黑树以提高查找效率。当红黑树节点数量减少到UNTREEIFY_THRESHOLD默认6时又会退化为链表。九、示例手写一个简单的红黑树下面给出一个极简的红黑树实现只包含插入操作帮助理解核心流程。javapublic class RBTreeK extends ComparableK, V { private static final boolean RED true; private static final boolean BLACK false; private Node root; private class Node { K key; V value; Node left, right, parent; boolean color; Node(K key, V value, Node parent) { this.key key; this.value value; this.parent parent; this.color RED; // 新节点为红色 } } public void put(K key, V value) { if (root null) { root new Node(key, value, null); root.color BLACK; return; } Node parent null; Node cur root; while (cur ! null) { parent cur; int cmp key.compareTo(cur.key); if (cmp 0) cur cur.left; else if (cmp 0) cur cur.right; else { cur.value value; // 更新值 return; } } Node newNode new Node(key, value, parent); if (key.compareTo(parent.key) 0) parent.left newNode; else parent.right newNode; fixAfterInsertion(newNode); } private void fixAfterInsertion(Node x) { x.color RED; while (x ! null x ! root x.parent.color RED) { if (x.parent x.parent.parent.left) { Node y x.parent.parent.right; // 叔叔节点 if (y ! null y.color RED) { // 情况1 x.parent.color BLACK; y.color BLACK; x.parent.parent.color RED; x x.parent.parent; } else { if (x x.parent.right) { // 情况2 x x.parent; rotateLeft(x); } // 情况3 x.parent.color BLACK; x.parent.parent.color RED; rotateRight(x.parent.parent); } } else { // 对称处理 Node y x.parent.parent.left; if (y ! null y.color RED) { x.parent.color BLACK; y.color BLACK; x.parent.parent.color RED; x x.parent.parent; } else { if (x x.parent.left) { x x.parent; rotateRight(x); } x.parent.color BLACK; x.parent.parent.color RED; rotateLeft(x.parent.parent); } } } root.color BLACK; } // 左旋与右旋实现与TreeMap类似此处省略具体代码 private void rotateLeft(Node p) { /* 实现略 */ } private void rotateRight(Node p) { /* 实现略 */ } }十、总结红黑树通过引入颜色属性和五条约束实现了近似平衡的二叉搜索树。其插入、删除操作虽然需要处理多种情况但通过旋转和着色可以在常数次操作内恢复平衡。在Java中TreeMap、TreeSet和HashMap在冲突严重时都依赖于红黑树是学习数据结构与算法的经典范例。理解红黑树不仅能帮助我们更好地使用这些集合类也为设计高性能的数据结构提供了坚实的理论基础。