01字典树

最大异或问题

红黑树

二叉查找树，两头黑（叶子结点为黑色的空节点），红不连续（被黑隔开），黑数目（黑高）相同

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

插入和删除需要少量的颜色变更和不超过三次树旋转（插入两次）

增加节点先标记为红色

修改指针结构

left-rotate/right-rotate

围绕节点X的左旋/右旋

魔方复原

插入操作的平衡调整

红黑树的平衡调整过程是一个迭代的过程，正在处理的节点是关注节点

祖父节点，叔父节点

1. 插入节点的父节点是黑色
2. 插入节点是根节点
3. 插入节点的父节点是红色
   1. 关注节点的叔父节点是红色
   2. 关注节点的叔父节点是黑色
      1. 关注节点是父节点的右子节点
      2. 关注节点是父节点的左子节点

删除操作的平衡调整

1. 初步调整，满足黑高相同
   1. 删除的节点只有一个子节点
   2. 删除的节点有两个非空子节点
      1. 删除的节点的后继节点是其右子节点
      2. 删除的节点的后继节点不是其右子节点
2. 二次调整，满足红色节点不相邻
   1. 关注节点的兄弟节点是红色
   2. 关注节点的兄弟节点是黑色
      1. 兄弟节点的左右子节点都是黑色
      2. 兄弟节点的左子节点是红色，右子节点是黑色
      3. 兄弟节点的右子节点是红色