树适合用于搜索，可是要达到好的效果（O(logN)时间），树中根到各个叶的距离不能差得太多。满足此要求的树称为平衡树，而本节讨论的AVL树则是其中最经典的一种。
type node[T constraints.Ordered] struct {
key T
state int8 //平衡因子
parent *node[T]
kids [2]*node[T] //Left与Right分别为0和1
}AVL树在其节点中加入了平衡因子，用于记录右子树高度（根到叶节点的最大距离）和左子树高度之差。当平衡因子的绝对值不超过一时，认为树处于平衡状态。
AVL树的关键在于保持平衡状态，在失去平衡的时候，必须进行再平衡变换。只要时刻保持警惕，非平衡状态时会有且只有一个节点的平衡因子为-2或2，再分析其子节点的平衡因子，则一共有四种情况。鉴于对称性，我们实际上只需要分析两种——LL型和LR型。
下面我们展示如何进行（旋转）变换：
---------------LR型-------------- ---------------LL型---------------
| G | C | | G | P |
| / \ | / \ | | / \ | / \ |
| P | P G | | P | C G |
| / \ | / \ / \ | | / \ | / \ / \ |
| C | u v | | C x | x |
| / \ | | | / \ | |
| u v | | | | |
除了伪LL型（及伪RR型）外，变换将使子树的高度下降。
func (G *node[T]) rotate() (*node[T], bool) {
Pside := (G.state + 2) / 4 //G.state == -2 || G.state == 2
Uside := 1 - Pside
P := G.kids[Pside]
if direct := G.state / 2; P.state == -direct { //LR(RL)
C := P.kids[Uside] //C != nil
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)
G.state, P.state = 0, 0
if C.state == direct {
G.state = -direct
} else if C.state == -direct {
P.state = direct
}
C.state = 0
return C, false
} else { //LL(RR)
G.kids[Pside] = G.Hook(P.kids[Uside])
P.kids[Uside] = P.hook(G)
if P.state == direct { //真LL(RR)
G.state, P.state = 0, 0
return P, false
} else { //伪LL(RR)，保持高度
G.state, P.state = direct, -direct
return P, true
} } }插入有可能会破坏平衡，只是不会出现伪LL型（或伪RR型）的情况。此时，只需要一次旋转变换和若干（O(logN)）次平衡因子的调整，便可以重新恢复平衡状态。
func (tr *Tree[T]) rebalanceAfterInsert(root *node[T], trace uint64) {
for {
state := root.state
root.state += int8(trace&1)*2 - 1 //调整平衡因子（trace是查找分支记录）
if state == 0 { //root.state为-1或1
if root.parent != nil {
root = root.parent //级联回溯
trace >>= 1
continue
}
} else if root.state != 0 { //root.state为-2或2
super := root.parent
root, _ = root.rotate() //再平衡变换（子树高度必然下降，到此结束）
if super == nil {
tr.root = super.hook(root)
} else {
super.kids[(trace>>1)&1] = super.hook(root)
} }
break //root.state为0，没什么好做的
} }删除也有可能会破坏平衡。因为旋转变换很可能使子树高度下降，一次旋转未必能解决问题，故变换次数和平衡因子的调整次数都可达O(logN)。
func (tr *Tree[T]) rebalanceAfterRemove(root *node[T], trace uint64) {
state, stop := root.state, false
root.state -= int8(trace&1)*2 - 1
for state != 0 { //如果原平衡因子为0则子树高度不变
super := root.parent
if super == nil {
if root.state != 0 { //root.state为-2或2
root, _ = root.rotate()
tr.root = super.hook(root) //再平衡变换
}
break
}
if root.state != 0 { //root.state为-2或2
root, stop = root.rotate()
super.kids[(trace>>1)&1] = super.hook(root)
if stop { break } //子树高度不变，终止追溯
}
root, state = super, super.state //级联回溯
trace >>= 1
root.state -= int8(trace&1)*2 - 1
} }前面我们默认AVL树是平衡的，这里我们来分析一下它到底平衡到什么程度：
设l(n)表示树中最短路径为n时树的最大高度（即最长路径的长度），则l(n+1) = l(n) + 2
X
l(n+1) = Depth { / \ } = l(n) + 2
l(n)+1 l(n)
显然f(1) = 2，于是可归纳得l(n) = 2n
也就是说最长路径的长度不会超过最短路径长度的两倍，所以，最坏情况下单点搜索时间还是O(logN)级。
设f(n)为构成高度为n的AVL树所需的最少节点，易见：
f(n+1) = f(n) + f(n-1) + 1
最终可以解出f(n) ≈ 2^((log(√5+1)-1)n) ≈ 2^(n/1.44)
进而可以得到一个更精确的结论：AVL树最长可能路径长度为1.44log(N)左右。