红黑树是带颜色约束的二叉搜索树。节点为红或黑，根和空叶视为黑；红节点不能有红孩子；任一节点到后代空叶的路径包含相同数量黑节点。这些性质使最长路径不超过最短路径约两倍，高度保持 O(log n)。

搜索仍按二叉搜索树比较键。插入先作为普通 BST 叶子加入并染红，以免立刻改变黑高；若父节点为红，则出现连续红，需要根据叔节点颜色处理。叔为红时，父与叔染黑、祖父染红并向上继续；叔为黑时，通过左旋或右旋把折线调整为直线，再旋转祖父并交换颜色。

旋转只改变局部连接而保持中序次序。左旋让右孩子上升、原节点成为其左孩子；右旋对称。删除更复杂：删除黑节点可能导致某条路径少一个黑色，需要借助兄弟节点颜色、兄弟孩子颜色、旋转和重新着色逐层修复。

查找、插入、删除均为 O(log n)，空间为 O(n)。相比 AVL，红黑树平衡条件更宽松，更新时旋转通常较少；AVL 高度更紧，读多写少时可能有优势。它常用于有序映射、集合和内核调度等需要稳定上界的场景。

误区是认为红黑树绝对平衡、只背五条性质却不会检查黑高、把旋转当作交换键值，以及忽略父指针和根引用更新。小结：颜色是编码平衡信息，旋转保持排序，重新着色恢复黑高；理解这三者分工比记大量情况更重要。