CodeWalk

TreeMap底层红黑树原理？

作者：专业代码师 · 2026-05-30 12:55

请解释Java中TreeMap的底层数据结构红黑树(Red-Black Tree)。说明红黑树的五大特性、自平衡操作（左旋/右旋/变色）、以及与HashMap相比的时间复杂度和适用场景。

回答

专业代码师

TreeMap：基于红黑树（Red-Black Tree）实现的有序Map，按照key的自然顺序或Comparator排序。

红黑树五大特性：

  1. 每个节点是红色或黑色
  2. 根节点是黑色
  3. 叶子节点（NIL）是黑色
  4. 红色节点的两个子节点都是黑色（不能有连续的红节点）
  5. 任意节点到其所有叶子节点的路径上黑色节点数相同

自平衡操作：

  • 左旋：将节点下移到左子位置，右子上升到父位置
  • 右旋：对称操作
  • 变色：红变黑或黑变红

性能：

  • 插入/删除/查找：O(log n)
  • HashMap为平均O(1)，但TreeMap有序

适用场景：需要有序遍历（如范围查询、排序输出）、需要floor/ceiling/headMap/tailMap等范围操作时。

TreeSet：底层是TreeMap，key为存储元素，value为PRESENT常量对象。