TikTok 红黑树：黑高、旋转与最坏查询保证

题目重点：从颜色不变量证明高度界，说明插删修复职责，不把红黑树与二叉堆混淆。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

红黑树首先满足BST有序关系，再加颜色约束：节点红或黑，root黑，空叶黑，红节点孩子不为红，每个节点到后代空叶路径黑节点数相同。空叶是概念哨兵，不一定存实际对象。
统一黑高的路径配合禁止连续红，保证任一路径至多交替插入红节点。黑高b至少对应2^b−1个内部节点，因此高度至多约2log2(n+1)，得到最坏对数查找。
旋转只重排局部父子结构，保持中序key顺序；颜色调整恢复黑高与红邻接。旋转不是排序整个子树，也不能靠颜色改变弥补违反BST键序的插入。
插入先按BST找位置，通常新节点染红以不直接增加路径黑高，再按父/叔关系重染或旋转修复；root最终黑。删除黑节点可能造成黑高缺失，修复比插入复杂，需追踪替代节点和兄弟状态。
不必在基础问点背所有删除case但应说明为何需要修复与高度证明。生产实现还要维护父指针、sentinel和size等增强字段，旋转后元数据不能遗忘。
测试有序输入、高重复key策略、连续插删后每条不变量；仅比较查到的值不够发现暂时红红或黑高错误。递归验证黑高并核对BST范围可作独立校验。

若所有节点只按普通BST插入升序，会变链；红黑修复避免高度n。红节点能夹在黑路径之间，但不能连续两个，因此最长路径不会无限偏斜。

搜索/插入/删除最坏O(log n)，每次局部旋转O(1)，存储O(n)。范围输出k项通常O(log n+k)，比较器成本另计。