一句话答案

红黑树是近似平衡 BST，五大性质保证最长路径不超最短两倍，HashMap 链表 ≥8 时转红黑树提升查找到 O(logn)。

核心要点

红黑树五性质： 1.非红即黑 2.根黑 3.叶(NIL)黑 4.红无红子 5.黑路同数

HashMap 中的使用： 链表≥8 且数组≥64 → 转红黑树；节点≤6 → 退化链表

AVL vs 红黑树： AVL 查找更快但插删旋转多；红黑树增删少旋转，适合 HashMap/TreeMap

追问与易错

追问方向：

• 红黑树和 AVL 树怎么选？
• HashMap 为什么不一直用红黑树？
• 红黑树的旋转操作理解吗？

易错点：

• ❌ 红黑树就是平衡二叉树——是近似平衡
• ❌ HashMap 链表到 8 就转——还需数组长度 >=64

💡 记忆锚点

红黑树五条铁律保证"不太歪"：非红即黑、根黑、叶黑、红不连红、黑路同数，最长路径最多是最短的两倍（近似平衡）。HashMap的策略像排队：人少时排链表（简单），人多到8个且桌子够大（数组>=64）就上叫号系统（红黑树O(logn)），人少于6个再拆回链表。