红黑树也是一种平衡二叉搜索树，它和AVL树堪称双璧（虽然历史上红黑树与B树的渊源可能更深）。
红黑树的节点同样有平衡因子：
type node[T constraints.Ordered] struct {
key T
black bool //平衡因子
parent *node[T]
kids [2]*node[T]
}由于平衡因子只有1bit，可以考虑和parent字段合并：
type node[T constraints.Ordered] struct {
key T
trait uintptr //压缩字段
kids [2]*node[T]
}
func (unit *node[T]) setParent(parent *node[T]) {
pt := uintptr(unsafe.Pointer(parent))
if (pt & HackBit) != 0 {
panic("unexpected high pointer")
}
unit.trait = pt | (unit.trait & HackBit)
}
func (unit *node[T]) getParent() *node[T] {
pt := unit.trait & ^HackBit
return (*node[T])(unsafe.Pointer(pt))
}
func (unit *node[T]) isRed() bool {
return (unit.trait & HackBit) == 0
}
func (unit *node[T]) isBlack() bool {
return (unit.trait & HackBit) != 0
}
func (unit *node[T]) setRed() {
unit.trait &= ^HackBit
}
func (unit *node[T]) setBlack() {
unit.trait |= HackBit
} 不同于AVL树的一本正经，红黑树走的是猥琐路线。我们不是想要一棵平衡树吗？好，先来一棵完美的平衡树，它从根到叶的所有路径都等长。我们把这棵树称为黑树。但是，黑树实在太完美了，我们很难从它身上捞到什么好处。于是，我们要对黑树进行注水。注进去的点，我们称之为红点，注过水的黑树就成了红黑树。
不过，注水还有些讲究。有点像视频中过渡帧依赖于关键帧，在红黑树中，红点只允许出现在黑点之后。这确保了树中最长路径（半红半黑）的长度不会超过最短路径（全黑）长度的两倍，与AVL树有异曲同工之妙。
如上所述，插入红点。如果该点落在黑点之后，那么万事大吉，否则需要根据其叔父节点的颜色分两种情况考虑。
------------红叔模式------------
= bG | rG =
= / \ | / \ =
= rP rU | bP bU =
= | | | =
= rC | rC =
对于叔父为红点的情况，改变父辈和祖辈节点的颜色就可以解决。不过，祖父与曾祖间可能需要继续协调，因而变色次数为O(logN)级。
------------------LR型----------------- ------------------LL型-----------------
| bG | bC | | bG | bP |
| / \ | / \ | | / \ | / \ |
| rP bU | rP rG | | rP bU | rC rG |
| / \ | / \ / \ | | / \ | / \ |
| rC | u v bU | | rC x | x bU |
| / \ | |
| u v | |
对于叔父为黑点的情况，依据三代关系可进一步分为四种情形。鉴于对称性，我们只分析其中两种，而它们都可以通过一次旋转变换解决。
func (tr *Tree[T]) rebalanceAfterInsert(P *node[T], trace uint64) {
for P.isRed() { //违反双红禁
G := P.getParent() //必然存在，根为黑，P非根
super := G.getParent()
Pside := (trace >> 1) & 1
Uside := 1 - Pside
U := G.kids[Uside]
if U != nil && U.isRed() { //红叔模式，变色解决
P.setBlack()
U.setBlack()
if super != nil {
G.setRed()
P = super
trace >>= 2
continue //上溯，检查双红禁
} //遇根终止
} else { //黑叔模式，旋转解决
var root *node[T]
if (trace & 1) == Pside { //LL(RR)
G.kids[Pside] = G.Hook(P.kids[Uside])
P.kids[Uside] = P.hook(G)
root = P
} else { //LR(RL)
C := P.kids[Uside]
P.kids[Uside] = P.Hook(C.kids[Pside])
G.kids[Pside] = G.Hook(C.kids[Uside])
C.kids[Pside], C.kids[Uside] = C.hook(P), C.hook(G)
root = C
}
G.setRed()
root.setBlack()
if super == nil {
tr.root = super.hook(root)
} else {
super.kids[(trace>>2)&1] = super.hook(root)
}
}
break //变色时才需要循环
} }func (tr *Tree[T]) Remove(key T) bool {
//...
if root := victim.getParent(); root == nil {
//...
} else {
//...
if victim.isBlack() { //红victim随便删，黑的要考虑
if orphan != nil && orphan.isRed() {
orphan.setBlack() //红子变黑顶上
} else { //剩下情况：victim黑，orphan也黑
tr.rebalanceAfterRemove(root, trace) //此时victim的兄弟必然存在
} }
target.key = victim.key
}
return true
}红黑树的删除就是要设法留住黑点。当被删除的点或其遗孤是红点时不需太多考虑，否则要来一番移花接木。
----------------红叔模式----------------
= bG | bU =
= / \ | / \ =
= bO rU | rG bZ =
= / \ | / \ =
= bY bZ | bO bY =
当遗孤的叔父为红点时，不好直接处理，但我们可以通过一次旋转变出一个黑叔父来。
------------------双黑------------------
| xG | bG |
| / \ | / \ |
| bO bU | bO rU |
| / \ | / \ |
| bY bZ | bY bZ |
------------------中红------------------
| xG | xY |
| / \ | / \ | ----------------中黑外红----------------
| bO bU | bG bU | | xG | xU |
| / \ | / \ / \ | | / \ | / \ |
| rY xZ | bO u v xZ | | bO bU | bG bZ |
| / \ | | | / \ | / \ |
| u v | | | bY rZ | bO bY |
当遗孤的叔父为黑点时，依据堂兄弟节点的颜色有三类情形：双黑、中红、中黑外红。其中双黑可以通过变色解决，如果这个过程中祖父节点的颜色发生变化，还会产生连锁效应。其它两种情形都需要一次旋转变换。红叔模式的变换不会导致双黑情形，所以整个删除过程的旋转次数不超过两次（O(1)，不同于AVL树的O(logN)），但是变色次数仍可到O(logN)。
func (tr *Tree[T]) rebalanceAfterRemove(G *node[T], trace uint64) {
for {
super := G.getParent()
Oside := trace & 1
Uside := 1 - Oside
U := G.kids[Uside] //U != nil
Y, Z := U.kids[Oside], U.kids[Uside] //红叔下必是两个实体黑
if U.isRed() { //红叔模式
G.kids[Uside] = G.hook(Y)
U.kids[Oside] = U.hook(G)
U.setBlack()
G.setRed()
if super == nil {
tr.root = super.hook(U)
} else {
super.kids[(trace>>1)&1] = super.hook(U)
}
trace = (trace << 1) | Oside
continue //变出黑U后再行解决
}
var root *node[T]
if Y == nil || Y.isBlack() {
if Z == nil || Z.isBlack() { //双黑，变色解决
U.setRed()
if G.isRed() {
G.setBlack()
} else if super != nil {
G = super
trace >>= 1
continue //上溯
}
break
}
G.kids[Uside] = G.Hook(Y)
U.kids[Oside] = U.hook(G)
U.copyColor(G)
G.setBlack()
Z.setBlack()
root = U //中黑外红
} else { //中红
G.kids[Uside] = G.Hook(Y.kids[Oside])
U.kids[Oside] = U.Hook(Y.kids[Uside])
Y.kids[Oside], Y.kids[Uside] = Y.hook(G), Y.hook(U)
Y.copyColor(G)
G.setBlack()
root = Y
}
if super == nil {
tr.root = super.hook(root)
} else {
super.kids[(trace>>1)&1] = super.hook(root)
}
break //个别情况需要循环
} }