4.md

树

1. AVL树
2. 红黑树
3. 弱AVL树
4. B+树
5. 基数树

---

树是一种层次结构，有一个根节点，然后开枝散叶。

type Node[T any] struct {
    key         T
    left, right *Node[T]
}

有些时候，我们希望能直接找到兄弟节点，或者希望在分支较多时节省存储空间，会使用链表来记录兄弟节点。

type Node[T any] struct {
    key   T
    child *Node[T]    //指向长子
    peer  *Node[T]    //兄弟节点链表（也可以用双向链表）
}

二叉搜索树

        4
       / \
      2   5
     / \   \
    1   3   6

　　二叉搜索树是基于二叉树的一种逻辑结构，要求左子节点值、父节点值、右子节点值构成有序列，以便于从根开始寻找具有某个值的节点。二叉搜索树的搜索与插入都比较容易，可是删除要费点功夫。当目标节点有两个子节点时，直接删除将面临子节点安置的问题（无法子承父位）。此时，我们选择为目标节点找个替死鬼——值与之最接近的两个节点之一。替死鬼显然不会还有两个子节点，删除它并让目标节点把它的值保留下来就好。

func (tr *NaiveBST[T]) Remove(key T) bool {
    target, parent := tr.root, (*node[T])(nil)
    for target != nil && key != target.key {
        if key < target.key {
            target, parent = target.left, target
        } else {
            target, parent = target.right, target
    }   }
    if target == nil { return false }               //不存在

    var victim, orphan *node[T]
    switch {
    case target.left == nil:
        victim, orphan = target, target.right
    case target.right == nil:
        victim, orphan = target, target.left
    default:                                        //需要找替死鬼
        victim, parent = target.right, target
        for victim.left != nil {                    //取中右（或中左）
            victim, parent = victim.left, victim
        }
        orphan = victim.right
    }

    if parent == nil {                              //此时victim==target
        tr.root = orphan
    } else {
        if victim.key < parent.key {
            parent.left = orphan
        } else {                                    //子承父位
            parent.right = orphan
        }
        target.key = victim.key                     //还魂
    }
    return true
}

---

返回　下一章　下一节