二叉搜索树

删除

• 如果要删除的点至多有一个儿子，则直接删除，然后把儿子移上来；
• 如果要删除的点有两个儿子，则找到后继，把要删除的点的值修改为后继的值，然后递归删除后继。

AVL 树

平衡因子：左子树高度 $-$ 右子树高度 当平衡因子的绝对值小于等于 $1$ 时，认为树处于平衡状态。

旋转

左旋/右旋：把节点变成右/左儿子的左/右儿子

LL 型失衡：新插入的节点在失衡节点左儿子的左子树；其他情况（LR、RL、RR）同理

• LL 和 RR 型，只需要对失衡节点进行右旋/左旋；
• LR 型，先对失衡节点的左儿子左旋，然后变成 LL 型，对失衡节点右旋；
• RL 型和 LR 型同理。

插入的节点如果同时造成多个祖先失衡，只需要调整一次最近的失衡节点即可。但删除节点后，需要依次对每个祖先节点检查失衡。

红黑树

性质

1. 每个点是红色或者黑色
2. 根和叶子（$\text{NIL}$）是黑色的
3. 红色节点的儿子都是黑色的
4. 取定一个点，到任何一个叶子的路径上，黑色的点的个数都相等

操作

插入

插入一个红色节点，但它的父亲如果是红色节点，那么不满足性质 3。

• 如果插入的节点是根，那么直接把它变成黑色即可；
• 如果插入节点的叔叔是红色，那么把父亲、叔叔、爷爷翻转颜色，然后把爷爷当作插入节点，继续判断；
• 如果插入节点的叔叔是黑色，观察自己、父亲、爷爷的形态，使用[[二叉搜索树#AVL 树#旋转|AVL 树的旋转规则]]进行旋转，然后将最后一次旋转的旋转点和中心点翻转颜色。