红黑树

• 平和策略和 AVL平衡二叉搜索树 不同
• 红黑树是：保持最高子树不超过最矮树的两倍

特征

• 是一棵二叉搜索树
• 根节点和叶子节点（NULL）都是黑色
• 不存在连续的两个红色节点
• 任意节点到叶所有路径黑节点数量相同
• 可以用一个口诀记忆
  • 左根右、根叶黑、不红红、黑路同

性质

• 最长路径不超过最短路径的2倍 （特征3 4）

• 会发现 AVL树 更严格（所以插入删除的旋转操作更频繁） 所以 AVL 查询更高效、红黑树在插入上更高效 所以在 Java 的 HashMap 以及 C++ 的 Map 和 Set 中都使用了红黑树

插入操作

• 插入节点默认为红色
• 插入红色节点破坏红黑树性质的三种情况
  • 插入节点是根节点 → 根节点直接变黑
    • 破坏根叶黑性质
  • 插入节点的叔叔是红色 → 叔父爷节点变色，爷爷节点变插入节点（观察是否破坏红黑树性质）
  • 插入节点的叔叔是黑色 → （LL RR LR RL）旋转，然后变色
    • 破坏不红红性质（一定要看叔叔颜色）

删除操作

• 有点难暂时跳过