一、一句话红黑树 ≈ 近似平衡的二叉查找树保证查找 O(log n)二、5 条性质背前 4 条即可节点是红 / 黑根是黑叶子NIL是黑红节点的孩子必须是黑不能连续红任意节点到叶子的黑高相同保证平衡三、vs AVL面试必问对比红黑树AVL平衡弱平衡黑高一致严格平衡插入/删除更快旋转少慢查询稍慢更快应用TreeMap、HashMap早期数据库插入删除多 → 红黑树查询多 → AVL四、旋转理解就行左旋右子变父右旋左子变父五、插入只记结论新节点默认红色父节点是黑 → 结束父节点是红 → 看叔叔叔叔红 → 变色 上推叔叔黑 → 旋转 变色六、时间复杂度操作时间查找O(log n)插入O(log n)删除O(log n)七、工程应用JavaTreeMap/TreeSetCstd::mapLinux 调度器八、要不要手写面试刷题工作❌ 不考❌ 不写❌ 不用写只考理论不考手写。
红黑树（简易版）
发布时间：2026/5/22 18:11:34
一、一句话红黑树 ≈ 近似平衡的二叉查找树保证查找 O(log n)二、5 条性质背前 4 条即可节点是红 / 黑根是黑叶子NIL是黑红节点的孩子必须是黑不能连续红任意节点到叶子的黑高相同保证平衡三、vs AVL面试必问对比红黑树AVL平衡弱平衡黑高一致严格平衡插入/删除更快旋转少慢查询稍慢更快应用TreeMap、HashMap早期数据库插入删除多 → 红黑树查询多 → AVL四、旋转理解就行左旋右子变父右旋左子变父五、插入只记结论新节点默认红色父节点是黑 → 结束父节点是红 → 看叔叔叔叔红 → 变色 上推叔叔黑 → 旋转 变色六、时间复杂度操作时间查找O(log n)插入O(log n)删除O(log n)七、工程应用JavaTreeMap/TreeSetCstd::mapLinux 调度器八、要不要手写面试刷题工作❌ 不考❌ 不写❌ 不用写只考理论不考手写。
)
