状态机：给定规则下分类讨论——红黑树(+队列实验-银行模拟)

• 状态机：分类讨论，为了递归与美观，把重复的去掉
• due to 二叉树不保证平衡，here comes Red-Black tree——每条路黑高相同，lmax<2lmin
• 类似还有AVLT（1.44lgn，但维护代价大）

红黑树的插入(只用到分类讨论)

• 二叉树平常搜索找到插入点的位置，
• 从插入点开始，每次父节点与子节点同为红色，推理小游戏*1

红黑树的删除

二叉树的删除

• 0/1个长度>1子树，delete
• 2个长度>1子树，从节点少情况入手，

根A
A-子:A-left,A-rihgt
...
叶节点(l1,...,lm)(r1,...,rn)
l1<...<lm<r1<...<rn！
r1为根或lm为根
根r1/lm
叶节点(l1,...,lm)(r2,...,rn)/(l1,...,lm-1)(r1,...,rn)

• 推理小游戏*2