树形数据结构 • CoderXL's Blog

树形数据结构涵盖范围非常广，它们往往是很多问题上性能最优的数据结构，具体包括堆、树状数组、线段树、搜索树、并查集、Trie 等。

数据结构与算法课程仅涉及了其中的堆和搜索树，因此其余树形数据结构将不在此介绍。

堆#

堆有很多变种，但它们的核心功能就是高效地支持以下操作（以小根堆为例）：插入一个数、查询最小值、删除最小值。

功能强大的堆还可以实现（以小根堆为例）：合并两个堆、减小一个元素的值（Decrease Key）。

此处只介绍最基本的堆——二叉堆。

二叉堆#

二叉堆是一棵完全二叉树，可以用数组紧凑存储：对于下标为 $i$ 的节点，其左子节点为 $2i$ ，右子节点为 $2i+1$ ，父节点为 $\lfloor i/2 \rfloor$ .

graph TD
    1[1] --> 2[3]
    1 --> 3[2]
    2 --> 4[5]
    2 --> 5[7]
    3 --> 6[4]
    3 --> 7[6]

二叉堆的数组表示

C++
Python

int heap[N],cnt=0;
void insert(int x)
{
    heap[++cnt]=x;
    int i=cnt,fa;
    while(i>>1>=1)
    {
        fa=i>>1;
        if(heap[fa]>heap[i])
            swap(heap[fa],heap[i]);
        else
            break;
        i=fa;
    }
}
void pop()
{
    heap[1]=heap[cnt--];
    int i=1,son;
    while(2*i<=cnt)
    {
        son=i<<1;
        if(son+1<=cnt&&heap[son+1]<heap[son])
            son++;
        if(heap[son]<heap[i])
            swap(heap[son],heap[i]);
        else
            break;
        i=son;
    }
}

cpp

heap = [0] * N
cnt = 0

def insert(x):
    global cnt
    cnt += 1
    heap[cnt] = x
    i = cnt
    while i >> 1 >= 1:
        fa = i >> 1
        if heap[fa] > heap[i]:
            heap[fa], heap[i] = heap[i], heap[fa]
        else:
            break
        i = fa

def pop():
    global cnt
    heap[1] = heap[cnt]
    cnt -= 1
    i = 1
    while 2 * i <= cnt:
        son = i << 1
        if son + 1 <= cnt and heap[son + 1] < heap[son]:
            son += 1
        if heap[son] < heap[i]:
            heap[son], heap[i] = heap[i], heap[son]
        else:
            break
        i = son

python

插入：将新元素放到数组末尾，然后不断与父节点比较并上移（up-heap / bubble-up），直到满足堆性质。

删除最小值：用末尾元素替换根节点，然后不断与较小子节点比较并下移（down-heap / bubble-down），直到满足堆性质。

两种操作的时间复杂度均为 $O(\log n)$ ，查询最小值为 $O(1)$ .

应用：对顶堆#

对顶堆用于动态维护中位数（或其他分位数），是一种在线算法。

维护两个堆：

左堆：大根堆，存储较小的一半元素
右堆：小根堆，存储较大的一半元素

保持两个堆的大小差不超过 $1$ ，且左堆的所有元素 $\leq$ 右堆的所有元素。此时中位数就是两个堆的堆顶之一（或两者的平均值）。

插入新元素 $x$ 时：

如果 $x$ 小于等于左堆堆顶，插入左堆；否则插入右堆
平衡两个堆的大小：如果某个堆比另一个堆多 $2$ 个以上元素，将多出的堆顶移到另一个堆

flowchart TD
    subgraph "右堆（小根堆）"
	    direction LR
	    R1[8]
	    R2[10]
	    R3[9]
	    R1 --- R2
	    R1 --- R3
    end
    subgraph "左堆（大根堆）"
	    direction RL
	    L1[7]
	    L2[5]
	    L3[3]
	    L1 --- L2
	    L1 --- L3
    end

当前中位数为 $\frac{7+8}{2}=7.5$ . 插入新元素 $6$ 时， $6 \leq 7$ ，插入左堆；左堆变为 $4$ 个元素，右堆 $3$ 个，不需要平衡。如果继续插入 $4$ ，左堆变 $5$ 个，此时将左堆堆顶 $7$ 移到右堆，两个堆恢复平衡，中位数更新为 $6$ .

搜索树#

二叉搜索树（Binary Search Tree, BST）#

二叉搜索树是一棵二叉树，满足以下性质：

对任意节点，其左子树中所有节点的值 $\leq$ 该节点的值
其右子树中所有节点的值 $>$ 该节点的值
左右子树也都是二叉搜索树

对 BST 做中序遍历，得到的序列是有序的。

操作#

查找：从根开始，将目标值与当前节点比较——相等则找到；目标值小则进入左子树，大则进入右子树；到达空节点则表示不存在。

插入：沿查找路径走到空位置，在该位置创建新节点。

删除：分三种情况：

叶子节点：直接删除
只有一个子节点：用该子节点替代自己
有两个子节点：用后继（右子树中的最小值节点）替代自己，然后递归删除后继节点

BST 旋转示意

C++
Python

struct BST {
    struct Node {
        int val;
        Node *left = nullptr, *right = nullptr;
        Node(int v) : val(v) {}
    };
    Node* root = nullptr;

    Node* find(Node* x, int v) {
        if (!x || x->val == v) return x;
        return v < x->val ? find(x->left, v) : find(x->right, v);
    }

    Node* insert(Node* x, int v) {
        if (!x) return new Node(v);
        if (v < x->val) x->left = insert(x->left, v);
        else if (v > x->val) x->right = insert(x->right, v);
        return x;
    }

    Node* erase(Node* x, int v) {
        if (!x) return nullptr;
        if (v < x->val) x->left = erase(x->left, v);
        else if (v > x->val) x->right = erase(x->right, v);
        else {
            if (!x->left || !x->right) {
                Node* y = x->left ? x->left : x->right;
                delete x;
                return y;
            }
            Node* suc = x->right;
            while (suc->left) suc = suc->left;
            x->val = suc->val;
            x->right = erase(x->right, suc->val);
        }
        return x;
    }
};

cpp

class BST:
    class Node:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None

    def find(self, x, v):
        if x is None or x.val == v:
            return x
        return self.find(x.left, v) if v < x.val else self.find(x.right, v)

    def insert(self, x, v):
        if x is None:
            return self.Node(v)
        if v < x.val:
            x.left = self.insert(x.left, v)
        elif v > x.val:
            x.right = self.insert(x.right, v)
        return x

    def erase(self, x, v):
        if x is None:
            return None
        if v < x.val:
            x.left = self.erase(x.left, v)
        elif v > x.val:
            x.right = self.erase(x.right, v)
        else:
            if x.left is None or x.right is None:
                return x.left or x.right
            suc = x.right
            while suc.left:
                suc = suc.left
            x.val = suc.val
            x.right = self.erase(x.right, suc.val)
        return x

python

复杂度#

操作	平均情况	最坏情况
查找	$O(\log n)$	$O(n)$
插入	$O(\log n)$	$O(n)$
删除	$O(\log n)$	$O(n)$

最坏情况出现在顺序插入时（如 1, 2, 3, 4, 5），BST 退化成链表，树高达到 $O(n)$ . 这就是引入平衡树的动机。

平衡树是对二叉搜索树的改进。普通二叉搜索树容易在顺序插入时退化成链表，导致树高过高，操作效率从 $O(\log n)$ 降低为 $O(n)$ . 平衡树在插入删除时引入额外操作，“平衡”树高，因此得名平衡树。

AVL 树#

AVL 树是最早的自平衡二叉搜索树。它在 BST 的基础上要求：对任意节点，其左右子树的高度差（平衡因子）不超过 $1$ .

$\text{Balance Factor}(u) = \text{height}(\text{left}(u)) - \text{height}(\text{right}(u)) \in \{-1, 0, 1\}$

这一约束保证了 AVL 树的高度始终为 $O(\log n)$ （严格来说不超过 $1.44 \log_2(n+2) - 1.328$ ）。

AVL 树示例

旋转#

当插入或删除操作导致某个节点的平衡因子超出 $[-1, 1]$ 时，需要通过旋转来恢复 AVL 性质。失衡有四种情况，对应两种基本旋转：

LL（左左）：左子树的左子树过高 → 右旋

LR（左右）：左子树的右子树过高 → 先左后右

RR（右右）：右子树的右子树过高 → 左旋

RL（右左）：右子树的左子树过高 → 先右后左

LL 和 RR 是单旋转，LR 和 RL 是双旋转（两次单旋转的组合）。旋转操作保持 BST 的中序遍历不变，只改变节点间的层次关系。

C++
Python

struct AVL {
    struct Node {
        int ch[2];   // ch[0]=左, ch[1]=右
        int val, height;
    };
    vector<Node> tr;
    int root, tot;

    AVL(int cap = 200000) {
        tr.resize(cap + 5);
        root = tot = 0;
    }

    int h(int x) { return tr[x].height; }

    void pull(int x) {
        tr[x].height = max(h(tr[x].ch[0]), h(tr[x].ch[1])) + 1;
    }

    // dir=0 左旋（右孩子上移），dir=1 右旋（左孩子上移）
    int rotate(int x, int dir) {
        int y = tr[x].ch[dir ^ 1];
        tr[x].ch[dir ^ 1] = tr[y].ch[dir];
        tr[y].ch[dir] = x;
        pull(x); pull(y);
        return y;
    }

    int balanceFactor(int x) {
        return h(tr[x].ch[0]) - h(tr[x].ch[1]);
    }

    int rebalance(int x) {
        if (!x) return x;
        pull(x);
        int bf = balanceFactor(x);
        if (bf > 1) {  // 左偏
            if (balanceFactor(tr[x].ch[0]) < 0)
                tr[x].ch[0] = rotate(tr[x].ch[0], 0);  // LR：先左
            x = rotate(x, 1);  // 右旋
        } else if (bf < -1) {  // 右偏
            if (balanceFactor(tr[x].ch[1]) > 0)
                tr[x].ch[1] = rotate(tr[x].ch[1], 1);  // RL：先右
            x = rotate(x, 0);  // 左旋
        }
        return x;
    }

    int _insert(int x, int v) {
        if (!x) {
            tr[++tot] = {{0, 0}, v, 1};
            return tot;
        }
        if (v < tr[x].val) tr[x].ch[0] = _insert(tr[x].ch[0], v);
        else tr[x].ch[1] = _insert(tr[x].ch[1], v);
        return rebalance(x);
    }

    void insert(int v) { root = _insert(root, v); }

    int getMin(int x) {
        while (tr[x].ch[0]) x = tr[x].ch[0];
        return x;
    }

    int _erase(int x, int v) {
        if (!x) return x;
        if (v == tr[x].val) {
            if (!tr[x].ch[0] || !tr[x].ch[1])
                x = tr[x].ch[0] ? tr[x].ch[0] : tr[x].ch[1];
            else {
                int y = getMin(tr[x].ch[1]);
                tr[x].val = tr[y].val;
                tr[x].ch[1] = _erase(tr[x].ch[1], tr[y].val);
            }
        } else if (v < tr[x].val)
            tr[x].ch[0] = _erase(tr[x].ch[0], v);
        else
            tr[x].ch[1] = _erase(tr[x].ch[1], v);
        return rebalance(x);
    }

    void erase(int v) { root = _erase(root, v); }

    bool find(int v) {
        int x = root;
        while (x) {
            if (v == tr[x].val) return true;
            x = v < tr[x].val ? tr[x].ch[0] : tr[x].ch[1];
        }
        return false;
    }
}avl;

cpp

class AVL:
    class Node:
        __slots__ = ('ch', 'val', 'height')
        def __init__(self, val):
            self.ch = [None, None]  # [left, right]
            self.val = val
            self.height = 1

    def __init__(self):
        self.root = None

    def _h(self, x):
        return x.height if x else 0

    def _pull(self, x):
        if x:
            x.height = max(self._h(x.ch[0]), self._h(x.ch[1])) + 1

    def _rotate(self, x, dir):
        y = x.ch[dir ^ 1]
        x.ch[dir ^ 1] = y.ch[dir]
        y.ch[dir] = x
        self._pull(x)
        self._pull(y)
        return y

    def _bf(self, x):
        return self._h(x.ch[0]) - self._h(x.ch[1])

    def _rebalance(self, x):
        if not x: return None
        self._pull(x)
        bf = self._bf(x)
        if bf > 1:
            if self._bf(x.ch[0]) < 0:
                x.ch[0] = self._rotate(x.ch[0], 0)
            x = self._rotate(x, 1)
        elif bf < -1:
            if self._bf(x.ch[1]) > 0:
                x.ch[1] = self._rotate(x.ch[1], 1)
            x = self._rotate(x, 0)
        return x

    def insert(self, v):
        def _ins(x):
            if not x: return self.Node(v)
            if v < x.val: x.ch[0] = _ins(x.ch[0])
            else: x.ch[1] = _ins(x.ch[1])
            return self._rebalance(x)
        self.root = _ins(self.root)

    def erase(self, v):
        def _erase(x):
            if not x: return None
            if v == x.val:
                if not x.ch[0] or not x.ch[1]:
                    x = x.ch[0] or x.ch[1]
                else:
                    suc = x.ch[1]
                    while suc.ch[0]: suc = suc.ch[0]
                    x.val = suc.val
                    x.ch[1] = _erase(x.ch[1])
            elif v < x.val: x.ch[0] = _erase(x.ch[0])
            else: x.ch[1] = _erase(x.ch[1])
            return self._rebalance(x)
        self.root = _erase(self.root)

    def find(self, v):
        x = self.root
        while x:
            if v == x.val: return True
            x = x.ch[0] if v < x.val else x.ch[1]
        return False

python

复杂度#

操作	时间复杂度	空间复杂度
查找	$O(\log n)$	$O(1)$
插入	$O(\log n)$	$O(\log n)$
删除	$O(\log n)$	$O(\log n)$
遍历	$O(n)$	$O(n)$

B 树（B-Tree）#

B 树是一种多路平衡搜索树，专为磁盘等块存储设备设计。B 树中每个节点对应一个磁盘块，通过增大分支因子来压缩树高，减少磁盘 I/O 次数。

一棵 $m$ 阶 B 树满足：

每个内部节点最多有 $m$ 个子节点、 $m-1$ 个关键字
除根节点外，每个内部节点至少有 $\lceil m/2 \rceil$ 个子节点
根节点至少有 $2$ 个子节点（除非是叶子）
所有叶子在同一层

插入时，如果节点关键字数达到上限 $m-1$ ，则将中间关键字上移到父节点，节点分裂为两个。若根节点分裂，树高增加 $1$ .

删除时，如果节点关键字数不足下限，尝试从兄弟节点借用关键字，否则与兄弟节点合并。合并可能导致父节点也不足下限，需向上传播。

B 树的高度为 $O(\log_m n)$ ，对于较大的 $m$ （如数据库中的 $m$ 通常为几百），树高非常小，查询效率极高。

2-3 树#

2-3 树是一种 B 树（阶数 $m=3$ ），节点分为两种：

2-节点：包含 $1$ 个关键字和 $2$ 个子节点
3-节点：包含 $2$ 个关键字和 $3$ 个子节点

所有叶子在同一层，保证了完美平衡。

插入：找到对应的叶子，如果是 2-节点直接变成 3-节点；如果是 3-节点则暂时变成 4-节点（3 个关键字），然后分裂——中间关键字上移到父节点，剩余两个关键字各成 2-节点。分裂可能向上传播。

删除：从 3-节点中删除直接变为 2-节点；从 2-节点中删除后节点为空，需要从兄弟节点借关键字或与兄弟合并，可能向上传播。

红黑树#

红黑树是一种近似平衡的二叉搜索树，通过给节点着色（红/黑）来保证平衡。它满足以下五条性质：

每个节点是红色或黑色
根节点是黑色
每个叶子（NIL 空节点）是黑色
红色节点的两个子节点都是黑色（不能有连续的红节点）
从任一节点到其所有叶子后代的路径上，黑色节点数相同（称为黑色高度）

性质 4 和 5 共同保证了：从根到叶子的最长路径不超过最短路径的 $2$ 倍，因此树高为 $O(\log n)$ .

红黑树的插入和删除通过变色和旋转来恢复上述五条性质。实际工程中（如 C++ std::map、Linux 内核），红黑树比 AVL 树更常用——虽然红黑树的查找略慢（树高稍高），但插入和删除时需要调整的节点更少，综合性能更好。

B+ 树（B+Tree）#

B+ 树是 B 树的变种，主要区别在于：

内部节点只存储关键字（用于路由），不存储实际数据
所有数据都存储在叶子节点中
叶子节点通过链表链接在一起，支持高效的范围查询