- 正确答案：红黑树是一种自平衡的二叉查找树，通过在每个节点上增加一个存储位表示节点的颜色（红色或黑色），并通过一组约束规则来确保树在插入、删除等操作后仍然保持近似平衡，从而保证基本操作（如查找、插入、删除）的时间复杂度为O(log n)。左旋和右旋是红黑树用于维持平衡的核心旋转操作。在Java中，TreeMap和TreeSet底层就是基于红黑树实现的。 - 解答思路： 1. 首先解释什么是红黑树，强调其作为自平衡二叉搜索树的特性。 2. 说明红黑树的五条性质，这些性质是理解其平衡机制的基础。 3. 详细描述左旋和右旋的操作过程，包括指针如何调整。 4. 最后结合Java中的实际应用（TreeMap/TreeSet）说明其使用场景。 - 深度知识讲解：一、红黑树的定义与性质红黑树是一棵满足以下五个性质的二叉查找树： 1. 每个节点是红色或黑色。 2. 根节点是黑色。 3. 所有叶子节点（NIL节点，即空节点）都是黑色。 4. 如果一个节点是红色，则它的两个子节点都必须是黑色（即不能有两个连续的红色节点）。 5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（称为“黑高”一致）。这些性质共同作用，使得红黑树的最大高度不超过2*log₂(n+1)，因此能保证操作效率。二、左旋与右旋操作旋转操作不会改变二叉搜索树的中序遍历结果（即仍保持有序性），但可以调整树的结构以恢复平衡。 1. 左旋（Left Rotation）场景：当某个节点x的右孩子y为红色且破坏了平衡时，可能需要左旋。操作：以x为轴心向左旋转，使y成为新的子树根，x变为y的左孩子。假设节点结构如下： class Node { int key; Node left, right, parent; boolean color; // true=red, false=black } 左旋代码（伪代码）： function rotateLeft(root, x): 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 return root 2. 右旋（Right Rotation）是左旋的镜像操作。伪代码： function rotateRight(root, y): 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 return root 注意：旋转操作通常发生在插入或删除后的修复阶段，配合颜色翻转一起使用。三、红黑树的插入修复流程简述： 1. 新节点以红色插入（避免破坏黑高性质）。 2. 若父节点是黑色，无需修复。 3. 否则，根据叔节点颜色和位置，分情况处理： - 叔节点为红：变色（父、叔变黑，祖父变红），然后递归向上处理。 - 叔节点为黑：进行旋转（LL、LR、RR、RL型）并重新着色。四、Java中的红黑树实现在Java标准库中，java.util.TreeMap 和 java.util.TreeSet 的底层数据结构就是红黑树。 TreeMap 示例： TreeMap map = new TreeMap<>(); map.put(3, "three"); map.put(1, "one"); map.put(4, "four"); map.put(2, "two"); System.out.println(map); // 输出 {1=one, 2=two, 3=three, 4=four} 内部实现细节（基于JDK源码）： - TreeMap 继承自 AbstractMap，并实现了 NavigableMap 接口。 - 其内部定义了一个静态内部类 Entry 表示红黑树节点： static final class Entry implements Map.Entry { K key; V value; Entry left; Entry right; Entry parent; boolean color = BLACK; } - 插入操作调用 fixAfterInsertion 方法进行颜色调整和旋转。 - 删除后调用 fixAfterDeletion 来修复。 - 所有操作平均时间复杂度 O(log n) 为什么Java选择红黑树而不是AVL树？ - 红黑树牺牲了部分平衡性（最大高度约2logn），但旋转次数更少。 - 插入/删除性能更稳定，适合频繁修改的场景。 - 在HashMap中，当链表长度超过8且桶数组长度>=64时，链表会转换为红黑树（即“树化”），这也是Java 8的一个优化。 HashMap中的红黑树特例： transient TreeNode treeifyBin(Node[] tab, int hash) 当单个哈希桶中的链表节点过多时，为了提升查找性能（从O(n)降到O(log n)），会将链表转成红黑树。 TreeNode 类继承 LinkedHashMap.Entry，并扩展为支持树形结构。总结对比： | 特性 | AVL树 | 红黑树 | |--------------|-------------------|--------------------------| | 平衡严格度 | 高（左右子树高度差≤1） | 较宽松（最长路径≤2倍最短） | | 插入删除开销 | 多次旋转 | 旋转较少 | | 查找性能 | 更快 | 略慢 | | 应用场景 | 查看重于更新 | 更新频繁（如Java集合） | 因此，Java选择红黑树作为TreeMap和TreeSet的实现基础，是因为它在动态操作下的综合性能更优。 - 扩展知识点： - 红黑树与2-3-4树的等价关系：红黑树可视为2-3-4树的一种二叉表示形式。每一个2-3-4树的操作都可以映射到红黑树的颜色变换和旋转操作。 - NIL哨兵节点：实际实现中常使用一个共享的空节点（sentinel）代替null，简化边界判断。 - 线程安全性：TreeMap不是线程安全的，若需并发访问应使用Collections.synchronizedSortedMap或ConcurrentSkipListMap替代。 - 实际面试建议：能够手绘红黑树插入/删除后的调整过程，尤其是典型情况（如插入导致双红冲突后的三种修复情形）非常重要。同时要理解Java中TreeMap提供的有序遍历（自然顺序或Comparator）、firstKey()/lastKey()、subMap()等方法背后的红黑树支持机制。

阿里云智能二面

全站热榜

创作者周榜