树与搜索：分层数据结构

二叉搜索树：有序性的结构表达

package main

import "fmt"

type BST struct {
    val         int
    left, right *BST
}

func (t *BST) Insert(val int) *BST {
    if t == nil {
        return &BST{val: val}
    }
    if val < t.val {
        t.left = t.left.Insert(val)
    } else if val > t.val {
        t.right = t.right.Insert(val)
    }
    return t
}

// BST 性质：中序遍历 = 升序序列
func (t *BST) InOrder() []int {
    if t == nil {
        return nil
    }
    result := t.left.InOrder()
    result = append(result, t.val)
    result = append(result, t.right.InOrder()...)
    return result
}

// 高度：衡量最坏情况复杂度
func (t *BST) Height() int {
    if t == nil {
        return 0
    }
    lh, rh := t.left.Height(), t.right.Height()
    if lh > rh {
        return lh + 1
    }
    return rh + 1
}

func main() {
    var root *BST
    for _, v := range []int{5, 3, 7, 1, 4, 6, 8} {
        root = root.Insert(v)
    }
    fmt.Println("中序遍历:", root.InOrder())  // [1 2 3 4 5 6 7 8]
    fmt.Println("树高:", root.Height())  // 3（平衡）

    // 最坏情况：顺序插入退化成链表
    var degenerate *BST
    for _, v := range []int{1, 2, 3, 4, 5, 6, 7} {
        degenerate = degenerate.Insert(v)
    }
    fmt.Println("退化树高:", degenerate.Height())  // 7（链表）
}

AVL 树：最严格的平衡

AVL 树要求每个节点的左右子树高度差（平衡因子）≤ 1。通过四种旋转（左旋、右旋、左右旋、右左旋）维持这个不变量。树高严格 ≤ 1.44 log₂(n+2)，保证所有操作 O(log n)。代价是插入/删除时可能需要多次旋转，比红黑树常数略大。

package main

import "fmt"

type AVL struct {
    val, height int
    left, right *AVL
}

func height(n *AVL) int {
    if n == nil { return 0 }
    return n.height
}

func updateHeight(n *AVL) {
    lh, rh := height(n.left), height(n.right)
    if lh > rh { n.height = lh + 1 } else { n.height = rh + 1 }
}

func balanceFactor(n *AVL) int { return height(n.left) - height(n.right) }

// 右旋（修复左重不平衡）
func rotateRight(y *AVL) *AVL {
    x := y.left
    y.left = x.right
    x.right = y
    updateHeight(y)
    updateHeight(x)
    return x
}

// 左旋
func rotateLeft(x *AVL) *AVL {
    y := x.right
    x.right = y.left
    y.left = x
    updateHeight(x)
    updateHeight(y)
    return y
}

func balance(n *AVL) *AVL {
    updateHeight(n)
    bf := balanceFactor(n)
    if bf > 1 {  // 左重
        if balanceFactor(n.left) < 0 { n.left = rotateLeft(n.left) }  // 左右情况
        return rotateRight(n)
    }
    if bf < -1 {  // 右重
        if balanceFactor(n.right) > 0 { n.right = rotateRight(n.right) }  // 右左情况
        return rotateLeft(n)
    }
    return n
}

func insert(n *AVL, val int) *AVL {
    if n == nil { return &AVL{val: val, height: 1} }
    if val < n.val { n.left = insert(n.left, val) } else if val > n.val { n.right = insert(n.right, val) }
    return balance(n)
}

func main() {
    var root *AVL
    for _, v := range []int{1, 2, 3, 4, 5, 6, 7} {  // 顺序插入
        root = insert(root, v)
    }
    fmt.Println("AVL 树高:", height(root))  // 3（自动平衡）
}

B 树：为磁盘 IO 优化的平衡树

B 树（B-tree）是 m 阶平衡树，每个节点最多 m-1 个键和 m 个子节点。树高 h = O(log_m n)，m 越大，树越矮，磁盘 IO 越少。数据库索引用 B+ 树（所有数据在叶节点，叶节点用链表串联），范围查询只需扫描叶节点链表。

树是图的简化，也是数据结构的骨架——理解树，你就理解了分层的本质。

— 算法导论