红黑树的五大性质1.每个节点要么是红色要么是黑色。2.根节点是黑色的。3.所有叶子节点NIL 空节点都是黑色的。4.红色节点的两个子节点必须是黑色的即不能有连续的红色节点。5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点这个数目称为黑高。数据结构 平均查找 最坏查找 平衡性普通二叉查找树 O(log n) O(n) 不平衡AVL 树 O(log n) O(log n) 严格平衡红黑树 O(log n) O(log n) 近似平衡AVL 树查询更快但插入/删除需要更多旋转适合读多写少。红黑树插入/删除效率更高旋转次数少适合频繁增删的场景。红黑树时间复杂度:查找O(log n)插入O(log n)最多旋转 2 次删除O(log n)最多旋转 3 次红黑树插入插入的节点初始为红色。主要分三种情况1.父节点是黑色 → 直接插入无需修复。2.父节点是红色且叔叔节点也是红色→ 父、叔变黑祖父变红然后递归处理祖父。3.父节点是红色叔叔节点是黑色→ 需要旋转 变色。LL 型对祖父右旋父变黑祖父变红。RR 型对祖父左旋父变黑祖父变红。LR / RL 型先对父节点旋转转换成 LL/RR 型再旋转祖父。红黑树删除1. 删除红色节点 → 直接删无需修复2. 删除黑色节点无孩子 或 只有一个孩子3. 删除有单个子节点的黑色节点4. 删除有左右两个孩子的节点红黑树旋转1.左旋Left Rotate右子节点过高右右型、右左型修复中的一步2.右旋Right Rotate左子节点过高左左型、左右型修复中的一步操作 AVL 树 红黑树插入旋转 最多 2 次 最多 2 次删除旋转 最多 O(log n) 次 最多 3 次红黑树删除最多 3 次旋转这是它相比 AVL 树的优势。