DataStructure_Tree

树专题复习笔记#

0. 总览#

树专题在这门课里大致分成四块：

1. 普通树与二叉树：术语、表示法、遍历、表达式树、线索二叉树。
2. 二叉搜索树 BST：ADT、查找、插入、删除、平均情况分析。
3. 优先队列与二叉堆：堆的结构性质、堆序性质、插入、删除最小元、建堆、d-heap。
4. 线段树 Segment Tree：区间聚合、构建、查询、单点更新、lazy propagation 的引子。

复习时可以抓住一句话：树类结构的题目通常都在问“结构约束 + 递归/路径操作 + 复杂度”。

1. Trees Preliminaries#

1.1 树的定义#

课程 PPT 的定义：

• A tree is a collection of nodes.
• It can be empty.
• Otherwise, it consists of a distinguished node $r$, called the root, and zero or more nonempty subtrees $T_1, \dots, T_k$.
• Each subtree root is connected by a directed edge from $r$.

要点：

• 子树之间不能相连，所以树中每个结点都可以看成某棵子树的根。
• 有 $N$ 个结点的树有 $N-1$ 条边。
• 通常把 root 画在最上面。

1.2 基本术语#

1.3 树的表示法#

List Representation#

用嵌套括号表示：

( A )
( A ( B, C, D ) )
( A ( B ( E, F ), C ( G ), D ( H, I, J ) ) )

问题：每个结点的分支数不固定，所以每个结点需要的 child 指针数量不固定，结构不统一。

FirstChild-NextSibling Representation#

每个结点固定三个域：

typedef struct TreeNode *Tree;
struct TreeNode {
    ElementType Element;
    Tree FirstChild;
    Tree NextSibling;
};

含义：

• FirstChild 指向第一个孩子。
• NextSibling 指向右边的下一个兄弟。
• 这种表示不唯一，因为普通树中 children 的顺序可以任意调整。

普通树转二叉树#

PPT 的说法是把 FirstChild-NextSibling tree 顺时针旋转 $45^\circ$。

转化规则：

• 二叉树的 left child = 原普通树的 first child。
• 二叉树的 right child = 原普通树的 next sibling。
• 根结点没有兄弟，所以转化后的根通常没有右子树。

2. Binary Trees#

2.1 定义与形态#

Binary tree：每个结点最多有两个孩子。

注意：

• 普通树中 children 的顺序不重要。
• 二叉树中 left child 和 right child 不同，所以只有一个孩子时，放左边和放右边是两棵不同的二叉树。

常见形态：

• Skewed binary tree：所有结点几乎都偏向一侧，最坏高度可达 $N-1$。
• Complete binary tree：所有叶子只出现在相邻两层，并且最后一层从左到右连续填充。

2.2 二叉树性质#

第 $i$ 层最多结点数：

深度为 $k$ 的二叉树最多结点数：

这里沿用 PPT 的写法，$k$ 按“层数”理解；如果按前面 \(Depth(root)=0\) 的边数定义，树高为 $h$ 时最多是 $2^{h+1}-1$ 个结点。

任意非空二叉树中：

其中 $n_0$ 是叶子结点数，$n_2$ 是度为 2 的结点数。

证明思路：

树有 $n$ 个结点，则边数：

所有边都来自度为 1 或 2 的结点：

所以：

得到：

2.3 Traversals#

普通树版本：

• Preorder：visit root，再访问每棵 child subtree。
• Postorder：先访问所有 child subtree，再 visit root。
• Levelorder：用 queue，从上到下、从左到右访问。

二叉树常用四种：

二叉树 inorder 递归：

void inorder(Tree T) {
    if (T) {
        inorder(T->Left);
        visit(T->Element);
        inorder(T->Right);
    }
}

迭代 inorder 的核心是“沿左链入栈，弹出访问，再转向右子树”：

void iter_inorder(Tree T) {
    Stack S = CreateStack(MAX_SIZE);
    for (;;) {
        for (; T; T = T->Left) {
            Push(T, S);
        }
        T = Top(S);
        Pop(S);
        if (!T) break;
        visit(T->Element);
        T = T->Right;
    }
}

2.4 表达式树 Expression Trees#

Expression tree / syntax tree 用二叉树表示表达式：

• 叶子结点通常是 operand。
• 内部结点通常是 operator。
• 对表达式树做 inorder 可得到中缀表达式。
• preorder 对应前缀表达式。
• postorder 对应后缀表达式。

PPT 示例：

infix:   A + B * C / D
postfix: A B C * D / +
prefix:  + A / * B C D

由 postfix 构造表达式树：

1. 扫描 postfix。
2. 遇到 operand，建单结点树并入栈。
3. 遇到 operator，弹出两个树：先弹出的是 right subtree，后弹出的是 left subtree。
4. 用 operator 建根，把两个子树接上，再把新树入栈。
5. 最后栈顶就是表达式树。

2.5 树递归应用#

目录列表：

static void ListDir(DirOrFile D, int Depth) {
    if (D is a legitimate entry) {
        PrintName(D, Depth);
        if (D is a directory) {
            for (each child C of D) {
                ListDir(C, Depth + 1);
            }
        }
    }
}

复杂度：

目录大小：

static int SizeDir(DirOrFile D) {
    int TotalSize = 0;
    if (D is a legitimate entry) {
        TotalSize = FileSize(D);
        if (D is a directory) {
            for (each child C of D) {
                TotalSize += SizeDir(C);
            }
        }
    }
    return TotalSize;
}

同样是每个结点访问一次：

2.6 Threaded Binary Trees#

PPT 的动机：

• 一棵有 $n$ 个结点的普通二叉链表有 $2n$ 个 child links。
• 实际边数只有 $n-1$。
• 所以 null links 数量是：

线索二叉树把这些 null links 利用起来，让遍历更方便。

规则：

1. 如果 \(Tree->Left == NULL\)，把它替换成 inorder predecessor。
2. 如果 \(Tree->Right == NULL\)，把它替换成 inorder successor。
3. 不能有 loose threads，所以需要一个 head node，head 的 left child 指向第一结点。

结点结构要加 flag：

typedef struct ThreadedTreeNode *ThreadedTree;

struct ThreadedTreeNode {
    int LeftThread;
    ThreadedTree Left;
    ElementType Element;
    int RightThread;
    ThreadedTree Right;
};

\(LeftThread == TRUE\) 表示 Left 是线索，不是真孩子；RightThread 同理。

3. Binary Search Trees#

3.1 定义#

BST 是一种二叉树，可以为空；非空时满足：

1. 每个结点有一个 key，课程 PPT 中假设 key 是整数且互异。
2. 左子树所有 key 小于 root key。
3. 右子树所有 key 大于 root key。
4. 左右子树也都是 BST。

一句话：

如果允许重复 key，要额外约定重复值放左边还是右边，或者在结点里维护 count。

3.2 Search Tree ADT#

PPT 给出的对象：

• A finite ordered list with zero or more elements.

核心操作：

SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);

3.3 Find#

递归版：

Position Find(ElementType X, SearchTree T) {
    if (T == NULL) return NULL;

    if (X < T->Element)
        return Find(X, T->Left);
    else if (X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}

迭代版：

Position Iter_Find(ElementType X, SearchTree T) {
    while (T) {
        if (X == T->Element) return T;
        if (X < T->Element)
            T = T->Left;
        else
            T = T->Right;
    }
    return NULL;
}

复杂度：

其中 $d$ 是目标结点深度。递归版是 tail recursion，可以自然改成迭代。

3.4 FindMin / FindMax#

最小值一定沿左链走到底：

Position FindMin(SearchTree T) {
    if (T == NULL) return NULL;
    else if (T->Left == NULL) return T;
    else return FindMin(T->Left);
}

最大值一定沿右链走到底：

Position FindMax(SearchTree T) {
    if (T != NULL) {
        while (T->Right != NULL) {
            T = T->Right;
        }
    }
    return T;
}

复杂度：

3.5 Insert#

思路：

1. 先按 Find 的路径寻找插入位置。
2. 如果遇到空位置，就在那里建立新结点。
3. 搜索过程中遇到的最后一个结点会成为新结点的 parent。

递归插入模板：

SearchTree Insert(ElementType X, SearchTree T) {
    if (T == NULL) {
        T = malloc(sizeof(struct TreeNode));
        if (T == NULL) {
            FatalError("Out of space!!!");
        } else {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    } else if (X < T->Element) {
        T->Left = Insert(X, T->Left);
    } else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
    }
    return T;
}

注意最后必须 return T，否则递归接回父结点时会丢树。

复杂度：

3.6 Delete#

删除分三种情况：

1. 删除叶子：把 parent 对它的链接置为 NULL。
2. 删除度为 1 的结点：用它唯一的 child 替代它。
3. 删除度为 2 的结点：
   • 用左子树最大结点，或右子树最小结点替换当前结点。
   • 再到对应子树中删除那个替换结点。
   • 替换结点的度一定至多为 1，所以后续删除会变简单。

课程代码模板使用右子树最小结点：

SearchTree Delete(ElementType X, SearchTree T) {
    Position TmpCell;

    if (T == NULL) {
        Error("Element not found");
    } else if (X < T->Element) {
        T->Left = Delete(X, T->Left);
    } else if (X > T->Element) {
        T->Right = Delete(X, T->Right);
    } else if (T->Left && T->Right) {
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(T->Element, T->Right);
    } else {
        TmpCell = T;
        if (T->Left == NULL)
            T = T->Right;
        else if (T->Right == NULL)
            T = T->Left;
        free(TmpCell);
    }

    return T;
}

复杂度：

其中 $h$ 是树高。

3.7 Lazy Deletion#

如果删除不多，可以在每个结点里加一个 flag：

int Active;

删除时只标记 inactive，不立即 free。

好处：

• 删除变快。
• 如果同一个 key 之后重新插入，可以直接恢复 active，不用重新 malloc。

风险：

• inactive 结点太多时，会让后续操作路径变长，影响效率。

3.8 Average-Case Analysis#

PPT 强调：BST 的高度取决于插入顺序。

例子：插入 $1,2,3,4,5,6,7$。

• 顺序 4,2,1,3,6,5,7 可以得到高度 $h=2$ 的较平衡树。
• 顺序 1,2,3,4,5,6,7 会退化成高度 $h=6$ 的 skewed tree。

所以 BST 操作复杂度不是天然 $O(\log N)$：

4. Priority Queues and Binary Heaps#

4.1 Priority Queue ADT#

对象：

• A finite ordered list with zero or more elements.

操作：

PriorityQueue Initialize(int MaxElements);
void Insert(ElementType X, PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);

含义：每次删除最高优先级或最低优先级的元素。课程主要讲 min heap，所以 DeleteMin 删除最小值。

4.2 简单实现比较#

PPT 里特别说明：BST 看起来不错，但优先队列只需要一直删最小元，AVL 等平衡树有很多不需要的操作，而且指针实现更复杂。

4.3 Binary Heap 的两个性质#

Structure Property#

Binary heap 必须是 complete binary tree。

PPT 定义：

• A binary tree with $n$ nodes and height $h$ is complete iff its nodes correspond to the nodes numbered from $1$ to $n$ in the perfect binary tree of height $h$.

高度为 $h$ 的 complete binary tree 结点数范围：

所以：

顺序存储：

ElementType BT[n + 1];  // BT[0] not used

下标关系：

Heap Order Property#

Min tree：每个结点的 key 不大于它孩子的 key。

Min heap：

• complete binary tree
• 同时满足 min tree 性质

因此：

• 最小值在根 \(H->Elements[1]\)。
• 其他任意 key 的查找通常要线性扫描整个 heap，因为 heap 只保证父子局部有序，不保证左右子树整体排序。

4.4 Initialize#

课程模板使用 Elements[0] 作为 sentinel：

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue H;

    if (MaxElements < MinPQSize)
        return Error("Priority queue size is too small");

    H = malloc(sizeof(struct HeapStruct));
    if (H == NULL)
        return FatalError("Out of space!!!");

    H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
    if (H->Elements == NULL)
        return FatalError("Out of space!!!");

    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;
    return H;
}

Elements[0] 不存真实数据，设成比所有元素都小的值，用来让上滤停止。

4.5 Insert: Percolate Up#

思路：

1. 新元素只能先放到数组末尾，因为要保持 complete binary tree。
2. 如果新元素比 parent 小，parent 下移。
3. 一路向上，直到 parent 不大于新元素。
4. 最后把新元素放入空位。

课程模板：

void Insert(ElementType X, PriorityQueue H) {
    int i;

    if (IsFull(H)) {
        Error("Priority queue is full");
        return;
    }

    for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2) {
        H->Elements[i] = H->Elements[i / 2];
    }
    H->Elements[i] = X;
}

注意 PPT 说这个写法 “Faster than swap”，因为它不是每层交换，而是一路挪 parent，最后一次性放入 \(X\)。

复杂度：

4.6 DeleteMin: Percolate Down#

思路：

1. 保存根结点最小值。
2. 取最后一个元素 LastElement。
3. 删除最后一个位置以维持 complete binary tree。
4. 从根开始向下找较小的 child。
5. 若 LastElement 大于较小 child，则 child 上移。
6. 找到合适位置后放入 LastElement。

课程模板：

ElementType DeleteMin(PriorityQueue H) {
    int i, Child;
    ElementType MinElement, LastElement;

    if (IsEmpty(H)) {
        Error("Priority queue is empty");
        return H->Elements[0];
    }

    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for (i = 1; i * 2 <= H->Size; i = Child) {
        Child = i * 2;
        if (Child != H->Size &&
            H->Elements[Child + 1] < H->Elements[Child]) {
            Child++;
        }

        if (LastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }

    H->Elements[i] = LastElement;
    return MinElement;
}

易错点：

• \(Child \ne H->Size\) 是为了确认右孩子存在。省略后可能访问不存在的右孩子。
• \(i * 2 \le H->Size\) 表示当前结点至少有左孩子。

复杂度：

4.7 Other Heap Operations#

PPT 强调：除了 minimum，heap 中查找任何 key 都要线性扫描。

常见扩展：

BuildHeap 不是做 $N$ 次 Insert。$N$ 次 Insert 是 $O(N \log N)$，PPT 中强调太慢。

从数组建堆的写法：

for (int i = H->Size / 2; i >= 1; --i) {
    PercolateDown(i, H);
}

为什么是 $O(N)$：

PPT 定理：

所有下滤成本加起来是线性的，所以：

4.8 d-Heaps#

d-heap：所有结点有 $d$ 个孩子。

问题：是不是 $d$ 越大越好？不是。

PPT 给出的原因：

1. DeleteMin 需要 $d-1$ 次比较才能找最小 child，所以复杂度约为：

1. 二叉堆的 \(*2\) 和 /2 可以用 bit shift，\(*d\) 和 /d 不一定。
2. 当优先队列太大，不能完全放进主存时，d-heap 会比较有意思。

5. Segment Tree#

5.1 动机#

PPT 问题：

给定数组 A[1000000]，需要频繁计算任意区间 [L, R] 的和。

朴素查询：

ElementType Query(ElementType A[], int L, int R) {
    ElementType sum = 0;
    for (int i = L; i <= R; ++i) {
        sum += A[i];
    }
    return sum;
}

复杂度：

如果 query 很频繁，这个代价太高。

5.2 结构#

Segment tree 把数组区间递归拆成左右两半：

• 根表示整个区间 [0, n-1]。
• 每个内部结点表示一个区间 [start, end]。
• 左孩子表示 [start, mid]。
• 右孩子表示 \([mid+1, end]\)。
• 叶子结点表示单个元素 [i]。

对 sum segment tree，结点值是对应区间的和。

PPT 示例数组：

A = [7, 2, 5, 3, 8]
root [0,4] = 25
[0,2] = 14
[3,4] = 11
[0,1] = 9
[2] = 5
[3] = 3
[4] = 8

线段树可以用数组存储：

int tree[2 * N];   // PPT 简化写法

实际写题时常用：

int tree[4 * MAXN];

因为非 $2^k$ 长度时，4N 是更稳的数组空间上界。

空间复杂度：

PPT 中完整二叉树视角写作 $O(2N - 1)$。

5.3 Build#

void Build(int node, int start, int end) {
    if (start == end) {
        tree[node] = A[start];
        return;
    }

    int mid = (start + end) / 2;
    Build(2 * node, start, mid);
    Build(2 * node + 1, mid + 1, end);

    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

复杂度：

PPT 注：build 只运行一次。

5.4 Query#

查询 [L, R] 时有三种情况：

代码：

int Query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) {
        return 0;
    }

    if (L <= start && end <= R) {
        return tree[node];
    }

    int mid = (start + end) / 2;
    int left_sum = Query(2 * node, start, mid, L, R);
    int right_sum = Query(2 * node + 1, mid + 1, end, L, R);

    return left_sum + right_sum;
}

复杂度：

严格说区间查询常写为 $O(\log N)$ 或 $O(\log N + k)$，本课程 PPT 记为 $O(\log N)$。

5.5 Update#

单点更新：令 \(A[idx] = val\)。

思路：

1. 从 root 开始判断 idx 在左区间还是右区间。
2. 递归直到叶子 [idx]。
3. 修改叶子值。
4. 回溯时重新计算沿途所有祖先结点。

代码：

void Update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }

    int mid = (start + end) / 2;
    if (start <= idx && idx <= mid) {
        Update(2 * node, start, mid, idx, val);
    } else {
        Update(2 * node + 1, mid + 1, end, idx, val);
    }

    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

复杂度：

5.6 不只用于 sum#

PPT notes：

Segment tree 不限于 sum，只要是区间 aggregation operator，都可以用类似结构：

• \(\sum\)
• min
• max
• average

注意：

• sum/min/max 都很自然。
• average 通常要维护 \((\sum, count)\)，最后再除，不是简单只存 average 就万事大吉。

5.7 Lazy Propagation#

PPT 只作为 self study 提到：

如果需要更一般的 RangeUpdate，比如：

add 10 to all numbers from index 2 to 1000

可以用 lazy propagation。

核心思想：

• 对完全覆盖的区间，不立刻更新所有叶子。
• 把更新信息暂存在当前结点的 lazy tag。
• 之后查询或继续下探时，再把 tag push down。

这部分如果考试不展开，知道用途和动机即可。

6. 和本仓库作业/项目的对应关系#

7. 常考抓手#

7.1 建树类题#

常见条件：

• preorder + inorder 可以唯一恢复二叉树。
• postorder + inorder 可以唯一恢复二叉树。
• preorder + postorder 一般不能唯一恢复，除非附加条件。

postorder + inorder 建树的关键：

• postorder 最后一个是 root。
• 在 inorder 中找到 root，左边是 left subtree，右边是 right subtree。
• 如果倒着读 postorder，顺序是 root, right, left，所以递归时要先建 right，再建 left。

7.2 BST 题#

看到 BST 先想：

• inorder 一定是升序。
• FindMin 走最左链。
• FindMax 走最右链。
• 删除两个孩子的结点时，用右子树最小或左子树最大替换。
• 复杂度看高度，不是自动看 $\log N$。

7.3 Heap 题#

看到 heap 先想：

• 数组下标从 1 开始更方便。
• parent: \(i / 2\)
• left child: \(2 * i\)
• right child: \(2 * i + 1\)
• Insert 是 percolate up。
• DeleteMin 是 percolate down。
• BuildHeap 从 \(N / 2\) 到 1 下滤，总复杂度 $O(N)$。

7.4 Segment Tree 题#

固定三件套：

Build(node, start, end)
Query(node, start, end, L, R)
Update(node, start, end, idx, val)

Query 三种 overlap：

• no overlap：返回单位元，sum 是 0，min 是 INF，max 是 -INF。
• total overlap：直接返回当前结点。
• partial overlap：递归左右孩子后 merge。

8. 一页速记#