💻 CSC3200 Final Revision C++ 数据结构(非线性)

November 27, 2025

C++ 数据结构(非线性) ：树、堆、图

六、树 Tree

树的抽象定义

一棵树是若干“节点”的集合，满足：

可以是空的（没有任何节点）。
如果非空：有一个特殊的节点 r (root, 根)；根下面以有向边 (directed-edge) 连着 0 个或多个子树 T1, T2, …, Tk，每个子树本身也是树。
树 = “一个根 + 若干棵子树”，而每棵子树又是同样的递归结构。

树的基本性质：

一个有 N 个节点的树一定有 N-1 条边
树中的节点不是根就是叶，不可能同时是两者。

树相关的术语：

父节点 parent：A 是 B 的 parent，当且仅当有一条边 A → B。
子节点 child：相同情况下，B 是 A 的 child。
兄弟 sibling：同一个父节点的不同子节点是 sibling。
叶子 leaf：没有任何子节点的节点 (整个结构最底层的点)。
路径 path：节点 n1 → n2 → … → nk，一连串从父到子的边。路径长度是这条路径上边的数量而不是节点数。
深度 depth：某个节点到根的路径长度。根的深度是 0。
高度 height：某个节点的高度 = 从它出发顺着边往下能到达的最远叶子的路径长度。一棵树的高度 = 根节点的高度。
祖先 / 后代 ancestor / descendant：A 到 B 有路径，则 A 是 B 的祖先，B 是 A 的后代。如果 A ≠ B，叫做“proper ancestor / descendant”（真祖先/真后代）。

特殊的，二叉树 (Binary Tree) 指的是所有根最多有两个子树 T_L、T_R的树。

树的基础实现

一个通用树节点的结构如下：

struct TreeNode {
    Object element;           // 存的东西不限制数据类型
    TreeNode *firstChild;     // 指向“第一个 (最左边) 的孩子”
    TreeNode *nextSibling;    // 指向“下一个 (右侧) 兄弟”
};

每个节点有不定个数的孩子（2 个、5 个、100 个都可能），用 left/right 两个指针只能实现二叉树；但用 std::vector<TreeNode*> children 也可以代替
firstChild / nextSibling 的好处是：任意树都能用固定两个指针表示；遍历“该节点的所有子节点”时，从 firstChild 开始，通过 nextSibling 一直向右走即可；例如“打印一个节点所有孩子”：

void printChildren(TreeNode *p) {
    for (TreeNode *child = p->firstChild; child != nullptr; child = child->nextSibling) {
        cout << child->element << endl;
    }
}

以下是二叉树的节点结构：

struct tree_node {
    Object element;
    tree_node *left;
    tree_node *right;
};

树与递归

回忆计算阶乘的递归函数：

int fact(int n) {
    if (n == 0) {        // 基本情况（base case）
        return 1;
    } else {             // 递归拆分
        return n * fact(n - 1);
    }
}

同样的套路可以直接套到树上：

基本情况：树是空的（指针是 NULL / nullptr）
否则：对“子树”递归自己 典型模式：

if (树是空的) {
    // 直接返回一个简单结果
} else {
    // 把问题拆成：左子树 / 右子树 / 所有子树 ...
    // 对每棵子树递归调用
    // 最后把结果组合起来
}

后面所有“遍历、查找最大值、统计叶子数、高度”等函数，其实都是这个范式的实例。

树的遍历顺序

“遍历 traversal”就是“按照某种顺序访问每个节点一次”。

前序 (preorder) 逻辑：

Algorithm preOrder(v)
    visit(v)
    for each child w of v
        preOrder(w)

先根然后从左到右对每个子节点递归做同样的事。对于二叉树：根、左、右

void preorder(tree_node *p) {
    if (p != NULL) {
        cout << p->data << endl;     // 1. 先访问根
        preorder(p->left);     // 2. 再遍历左子树
        preorder(p->right);    // 3. 最后遍历右子树
    }
}

你可以这么理解：打印带目录结构的大纲，先打标题再打各子章节：1→1.1→1.1.1→1.1.2→1.2→…

后序 (postorder) 逻辑：

Algorithm postOrder(v)
    for each child w of v
        postOrder(w)
    visit(v)

先左到右子树再处理根，向右的兄弟继续。对于二叉树：左、右、根

void postorder(tree_node *p) {
    if (p != NULL) {
        postorder(p->left);    // 1. 左子树
        postorder(p->right);   // 2. 右子树
        cout << p->data << endl;     // 3. 根
    }
}

你可以这么理解：计算一个文件夹占用空间，先把所有子目录和文件的空间加完，最后追溯回根目录记一个总数。重要应用：按指针删除整棵树。

中序 (inorder) 逻辑：

Algorithm inOrder(v)
	if(v == NULL) return
	inOrder (v.left)
	visit(v)
	inOrder (v.right)

先左子树再处理根，最后处理右边子树。对于二叉树：左、根、右

void inorder(tree_node *p) {
    if (p != NULL) {
        inorder(p->left);      // 1. 左子树
        cout << p->data << endl;     // 2. 根
        inorder(p->right);     // 3. 右子树
    }
}

重要应用：如果这棵树是“二叉搜索树” (BST，后面会讲)，中序遍历输出的序列就是“从小到大排序好的元素”。

七、二叉树 Binary Tree

上文提到过，二叉树是所有根节点最多有两个子树的树。

高度与高度-节点定律

讲义定义：

空树高度 = -1。
非空树 T：根记为 r，左子树 T_L，右子树 T_R；高度 height(T) = 1 + max(height(T_L), height(T_R))，也就是最长路径长度。求高度的递归函数如下：

int height(tree_node *p) {
    if (p == NULL) return -1;  // 空树
    int hl = height(p->left);
    int hr = height(p->right);
    return 1 + std::max(hl, hr);
}

最大/最小高度的结论

高度为 h 的二叉树，最多能有 $2^{(h+1)} - 1$ 个节点。证明：第 0 层最多 1 个、第 1 层最多 2 个……第 h 层最多 $2^h$ 个，所有层加起来即可。
有 N 个节点的二叉树，它的“最小可能高度”约等于 $⌈log_2(N+1) - 1⌉$。证明：把上一条“最大节点”公式倒过来解 h。当每一层都填满，高度最小 (叫“ 完全二叉树”)；缺一点点也不会改变高度，所以要取上整。
有 N 个节点的二叉树，它的“最大可能高度”显然等于 $N-1$。
有 N 个节点的二叉树的数量符合卡塔兰数： C_N = ${\frac{1}{N+1}}{2N\choose N}$

满二叉树（full binary tree）：每个节点要么 0 个孩子，要么 2 个孩子；不存在只有一个孩子的节点。

完全二叉树（complete binary tree）：除最后一层外，每一层都是满的；最后一层的节点都连续地靠左排列。同时“满且完全”的情况：比如高度为 2、节点数为 7 的完美小树。

二叉搜索树 BST

对每个节点 X：

左子树里所有值 < X.element；
右子树里所有值 > X.element；
左右子树本身也都是 BST。

所以二叉搜索树的中序输出恰好是从小到大排列的所有元素

这就相当于可以把数组里的二分法转换到树形结构上：查找、插入、删除平均高度只要 O(log N)。

二叉节点类

template <class T>
class BinaryNode {
    T element;
    BinaryNode *left;   // 左子节点
    BinaryNode *right;  // 右子节点
    BinaryNode(const T & theElement, BinaryNode *lt,
               BinaryNode *rt)
        : element(theElement), left(lt), right(rt) { }
};

实例化时像 new BinaryNode<int>(5, nullptr, nullptr) 这样。

查找 find(x, t) 函数

template <class T>
BinaryNode<T>* find(const T &x, BinaryNode<T> *t) const {   // t 是根节点
    if (t == NULL) return NULL;
    else if (x < t->element) return find(x, t->left); 
    // 目标小于当前节点 -> 去左子树
    else if (t->element < x) return find(x, t->right);      
    // 目标大于当前节点 -> 去右子树
    else return t;     // 否则就是相等 -> 找到了
}

这就是“递归版的二分法查找”：每一步把问题规模减半（只在左子树或右子树继续找）。

找最小、最大项函数

最小值 = 最左下的节点；最大值 = 最右下的节点。是否递归都能做。递归思路：

template <class T>
BinaryNode<T>* findMin(BinaryNode<T> *t) const {
    if (t == NULL) return NULL;
    if (t->left == NULL) return t;  // 没有左孩子 -> 自己就是最小
    return findMin(t->left);        // 否则一直往左找
}

非递归思路 (while loop)：

template <class T>
BinaryNode<T>* findMax(BinaryNode<T> *t) const {
    if (t != NULL)
        while (t->right != NULL)
            t = t->right;
    return t;
}

插入 insert(x, t) 函数

从根 t 开始，像 find 一样往下走，找不到就可以创造叶子；
如果遇到相同的值，什么也不做 (不允许重复)；
如果走到空指针位置（NULL），说明这里应该是新节点的位置，就 new 一个节点挂上去。注意 BinaryNode<T>* & t 是“指针的引用”，允许在函数里修改指针本身

template <class T>
void insert(const T &x, BinaryNode<T>* &t) const {
    if (t == NULL) {
        t = new BinaryNode<T>(x, NULL, NULL);  // 新建根/子节点
    } else if (x < t->element) insert(x, t->left);  // 插入到左子树
    else if (t->element < x) insert(x, t->right);  // 插入到右子树
    else ; // 重复值：不做任何事
}

每层递归都在“缩小范围”：只往一边走；当 t 为 NULL 时，把 t 改成一个新节点，相当于“在这里长出了一棵子树”。

删除 remove(x, t) 函数的三种情况

删除的核心难点就是“保持 BST 性质不变”，分三类：

删除叶子节点（无孩子）：直接把父节点指向它的指针设成 NULL，然后删掉这个节点。
删除只有一个孩子的节点：让父节点直接指向它的孩子，绕过这个要删的节点，然后 delete 它。(类似于链表的删除)
删除有两个孩子的节点：随便删会导致左右子树丢失

标准做法：找到“右子树里最小的节点”，即中序遍历的下一项；用这个值覆盖当前节点的 element 参数；然后在“右子树”里把那个 successor 节点删除 (它最多只有左子节点)。

template <class T>
void remove(const T &x, BinaryNode<T>* &t) const {
    if (t == NULL) return;
    if (x < t->element) remove(x, t->left);  // 去左子树
    else if (t->element < x) remove(x, t->right);  // 去右子树
    else if (t->left != NULL && t->right != NULL) {
        // 情况3：有两个孩子
        t->element = findMin(t->right)->element;  // 用中序遍历后继值替换
        remove(t->element, t->right);  // 删掉右子树里的那个后继节点
    } else {  // 情况1/2：最多只有一个孩子
        BinaryNode<T> *oldNode = t;
        t = (t->left != NULL) ? t->left : t->right;  // t 指向唯一孩子或空
        delete oldNode;
    }
}

情况 3 有另一种处理，也就是 “找左子树里最大的节点”，即中序遍历的上一项。因为左树 max、根、右树 min 在中序遍历时是连续项，用两个相邻替换根的位置都是可以的：

else if (t->left != NULL && t->right != NULL) {
    t->element = findMax(t->left)->element; 
    remove(t->element, t->left);

BST 的效率与退化

BST 的效率和插入时的无序性成正比。
平均情况下，树的高度 ≈ ⌈log2(n+1)-1⌉：查找/插入/删除平均 O(log N)。
但是，如果完全按“升序”插入：每次新节点都会变成“上一节点的右孩子”，整棵树退化成单链，平均复杂度 O(N)，类似于链表。

这就是为什么需要平衡树 (AVL、红黑树) 的原因。

TreeSort——用树进行二分法排序

思路：

先把数组里的 n 个元素逐个插入到 BST 中；
再对 BST 做一次中序遍历（inorder），按访问顺序把元素写回数组。

复杂度：插入 n 个元素平均每次 O(log N)，共 O(N log N)。最坏情况下，如果数组本身就有序会退化成 O(N^2)。中序遍历 O(N)。

所以 TreeSort平均 O(N log N)，和快排同一个量级；但是实现复杂，实际工程用得少。

保存一个 BST 要比保存一个数组占据的内存大很多。所以你可以保存数组，并在代码中完成数组和 BST 的相互转换。BST 转数组很简单，直接中序遍历即可；而用升序数组生成 BST 的方法如下 (二分法)：

单向指针

template <class T>
void createBST(Node *&p, int n, T *data) {
	static int idx = 0;
	if (n > 0) {
		p = new BinaryNode<int>(0, NULL, NULL);
		createBST(p->left, n / 2, data);
		p->element = data[idx++];
		createBST(p->right, (n - 1) / 2, data);
	}
}
int *data = {1, 2, 3, 4, 5, 6, 7};
int *ptr;
createBST(ptr, 7, data);

头尾双向指针

template<class T>
BinaryNode<T>* BSTer(const T* arr, int init, int end) {
    if (init > end) return nullptr;
    int mid = (init + end) / 2;
    auto* root = new BinaryNode<T>(arr[mid]);
    root->left  = BSTer(arr, init, mid - 1);
    root->right = BSTer(arr, mid + 1, end);
    return root;
}

八、平衡二叉搜索树 AVL

为了防止树退化的情况出现，需要给二叉树定义平衡限制：对于任意节点，其左右子树高度差不超过一：|height(left) - height(right)| ≤ 1。这样除了便利以外的操作都趋近于 O(log₂n)

可是在插入/删除操作后，平衡可能被破坏：插入/删除节点所在路径可能过长/过短。平衡树经常需要平衡判断，所以成员应引入高度：

template <class T>
class AvlNode {
    T element;
    AvlNode *left;
    AvlNode *right;
    int height; 
    // ......
    int height(const AvlNode<T> *t) return t == NULL ? -1 : t->height;
    // t 不是空指针就返回“height”成员参数
}

通过左右旋转 “保持平衡”

如果修改最深的出现不平衡的节点，这个节点更高处的不平衡也会解决。在最深不平衡点处，可以通过旋转父子节点改变树高。

左右旋

我们把父节点与右子节点交换位置叫做左旋；与左子节点交换位置叫做右旋： 左旋 L leftRotate(root, root->right)：父节点拿走右子节点的左子树 (作为自己的右子树) 并成为右子节点的左子树。这降低父节点的左树、升高子节点的右树。

AVLNode<T> *leftRotate(AVLNode<T> *root) {
	AVLNode<T> *son = root->right;
	AVLNode<T> *T = son->left;

	son->left = root;
	root->right = T;   // 顺序不能反！否则会断
	// 更新高度参数
	root->height = height(root);
	son->height = height(son); 
	return son;    // 返回新的根
}

示意图：

     root                    son
    /    \                  /   \
   A     son        ->    root   Target
        /   \            /    \
       T    Target      A      T

这样，右子节点的右子树就被抬高了。

右旋 R rightRotate(root, root->left)：父节点拿走左子节点的右子树 (作为自己的左子树) 并成为左子节点的右子树。这降低父节点的右树、升高子节点的左树。

AVLNode<T> *rightRotate(AVLNode<T> *root) {
	AVLNode<T> *son = root->left;
	AVLNode<T> *T = son->right; 

	son->right = root;
	root->left = T; 

	root->height = height(root);
	son->height = height(son);
	return son;
}

示意图：

        root                   son
       /    \                 /   \
     son     A     ->     Target   root
    /   \                         /    \
Target   T                       T      A

这样，左子节点的左子树就被抬高了。

四种情况与 “顺反结构”

我们以 “某个子树过长” 为例，一共有四种不平衡可能：

左子节点的左子树过长：LL 右单旋
右子节点的右子树过长：RR 左单旋
左子节点的右子树过长：LR 左右双旋
右子节点的左子树过长：RL 右左双旋

注意：怎么旋转不是猜出来的，失衡只可能发生在插/删点到根的路径上。我们需要一个 LminusR() 函数来记录平衡系数，如 height(n->left) - height(n->right) ≤ ±1就正常，否则就失衡，需要重平衡。

从插/删节点往父节点方向检查直到发现第一个“失衡点” n，这个节点 n 的哪个子树过高，其过高侧的子节点又是哪个子树过高？如果 LminusR(n)>1，说明左树过长，检查 LminusR(n->left) ≥ 0 就说明属于 LL 情况，右旋 n；<0 说明属于 LR 情况先左旋 n->left 变成 LL 情况再右旋 n。反之 LminusR(n)<1 也一样分为 RR (左旋 n) 和 RL (右旋 n->right 变成 RR 再左旋 n) 两种情况

这些情况中，因为 1 与 2 以及 3 与 4 两组分别是对称的，故情况类似。1 和 2 可以通过单此旋转重新平衡，而 3 和 4 需要两次旋转。以 3 为例，gson 树过长，追溯发现属于(Left, Right) 反式情况——需要先左旋(son, gson)，再右旋(root, gson)：

        root               root             gson
  (往右)/    \             /    \           /    \
     son     B   ->     gson    B   ->  son      root
    /   \(往左)         /    \          /   \    /    \
   A    gson         son     T2       A     T1 T2     B
       /    \       /   \
      T1     T2    A     T1

所有四种不平衡可能现在都可以统一处理：

int balanceFactor(AVLNode<T> *node) {
    return height(node->left) - height(node->right);
}   // 失衡系数，{-1, 0, 1} 属于正常值；大于零说明左子树更高。
AVLNode<T> *rotateNode(AVLNode<T> *node) {
	int balance = balanceFactor(node);
	if (balance > 1 && balanceFactor(node->left) >= 0)  // Case 1
		return rightRotate(node);
	if (balance < -1 && balanceFactor(node->right) <= 0)  // Case 2
		return leftRotate(node); 
	if (balance > 1 && balanceFactor(node->left) < 0) {  // Case 3
		node->left = leftRotate(node->left);
		return rightRotate(node);
	} 
	if (balance < -1 && balanceFactor(node->right) > 0) {  // Case 4
		node->right = rightRotate(node->right);
		return leftRotate(node);
	}
	return node;
}

核心思想：索引失衡点。用 “左树高与右树高的差” 为标准，判断属于哪种情况。临界情况：balanceFactor(node->left) = 0 说明过高那一侧子树的两个子树是等高的，只需要单次旋转把整个子树抬起来，所以算 1、2 情况。

AVL 的插入/删除函数

等同于 BST 的插入函数 + 更新高度参数 + 检查是否要重平衡：

AVLNode<T> *insert(AVLNode<T> *node, T key)
{   // 1. 像普通 BST 一样从根开始往下搜索并插入
    if (node == nullptr) return new AVLNode<T>(key);
    if (key < node->key) node->left = insert(node->left, key);
    else if (key > node->key) node->right = insert(node->right, key);
    else return node;  // 不插重复值
    // 2. 更新当前节点高度
    node->height = 1 + max(height(node->left), height(node->right));
    // 3. 计算平衡因子，必要时做旋转
    int balance = balanceFactor(node);
    if (balance < -1 || balance > 1)
        node = rotateNode(node);
    return node;
}

删除函数几乎完全一样，直接照抄 BST 的删除函数，并补充更新高度和检查平衡 (照抄插入函数的) 即可。

九、红黑二叉搜索树

抽象定义

RBTree 和 AVL 的关系

它也是有平衡限制的二叉搜索树；也通过“局部旋转 + 一些规则”来维护 O(log N)；
但它不要求高度差 ≤ 1，只用“颜色规则”来限制；
相比 AVL，红黑树插入/删除时旋转次数更少 (平衡要求不那么严格)；因为插删更频繁、代码更“局部”，所以标准库里经常采用红黑树 (如 C++ std::map/std::set 的实现)。

注意：

红黑树中，一个节点 “黑” 和 “空” 是几乎等价的，在判断中可以一起处理。
红黑树最奇怪的一点是，其对 “叶子” 的定义与一般的树是完全不同的。在红黑树中，叶子代表 NIL(空占位节点)——任意节点如果没有左或右子节点就会伸出空节点，现在把它们做叶子，因为 黑 ≡ 空，NIL 都是黑的。以下是一个合法的红黑树，符合五条要求：

红黑树的五条性质

Node Color：每个节点非红即黑。
Root Property：整个树的根节点始终是黑色。
所有叶子 (NIL) 视为黑色。
Red Property：红节点不能有红孩子 (没有“连续红”)。
Black Property：从任何一个节点到所有后代叶子的所有路径上，所经过的“黑节点数量”都相同。称为相同 “黑高度” (black height)。

这些规则保证了：

在最长路径上，红节点的数量 ≤ 黑节点数量；因此总高度 $h ≤ 2\ bh$；
结合“给定黑高度时的最少节点数”为 $N ≥ 2^{bh} - 1$ 这一点，可以推出来：

高度 $h ≤ 2 log_2(N + 1)$。
红黑树不可能瘦得像一条链，最多“比完全平衡树高两倍”，所以依然是 O(log N)。

红黑树的节点结构

enum COLOR { RED, BLACK };  // 枚举类的索引类似于数组（可以加减自增）
template<class T>
class RBNode {
public:
    T val;
    COLOR color;  // 高度限制变成了颜色限制
    RBNode *left, *right, *parent;  // 双向链表
    RBNode(T val) : val(val) {
        parent = left = right = NULL;
        color = RED;    // 插入时默认是红色
    }
};

多了一个 color 字段；
保留 parent 指针，便于做旋转时找到父节点。

左右旋与 moveDown 辅助函数

首先回忆：左旋 x 代表将 x 与 x->right 进行位置交换；

左旋示意（保持中序 xayb）：

    x                  y
     \                / \
      y      ->      x   b
     / \              \
    a   b              a

简化代码示意：

bool Node::isOnLeft() return this == parent->left;  
// 判断当前 this 节点是 parent 的左孩子还是右孩子
void moveDown(Node *nParent) { // 抬高 nParent，与 this 交换位置
    if (this->parent) {  // 如果父节点不为空...nParent 占据 this 原本的位置
        if (isOnLeft()) parent->left = nParent;
        else parent->right = nParent;
    }
    nParent->parent = parent;  // 更新：nParent 变成 parent 的子节点
    this->parent = nParent;    // 更新：this 变成 nParent 的子节点
}
void leftRotate(Node *x) {    // x 是父节点
    Node *y = x->right;       // y 是 x 的右孩子
    if (x == root) root = y;  // 如果 x 是整个树的根，根要更新为 y
    x->moveDown(y);           // 把 y 提上来、x 压下去
    x->right = y->left;       // 把 y 的左子树挂到 x 的右边
    if (x->right != NULL) x->right->parent = x; 
    y->left = x;              // x 成为 y 的左孩子
}

其实也可以用 BST 的旋转函数，但为 RBTree 的节点有 parent 参数，可以用另一种做法，两者核心思路是一致的。右旋类似，只是左右反过来。核心不变：保持 BST 中序顺序不变，只是“翻转父子关系”。

插入函数：先按 BST 插，再“修颜色 + 旋转”

先像普通 BST 一样寻找并插入新节点，颜色默认红色，其他要求先不管。区别是为了保护树根必须是黑色这一条要求，需要用户传入根指针：

// 先做 BST 插入，返回新插入节点；重复则返回 nullptr
template <class T>
RBNode<T>* bstInsert(const T& x, RBNode<T>* &p, RBNode<T>* parent) {
    if (!p) {
        p = new RBNode<T>(x);
        p->parent = parent;
        return p;
    }
    if (x < p->val) return bstInsert(x, p->left,  p);
    if (x > p->val) return bstInsert(x, p->right, p);
    return nullptr; // 不插重复
}
// 对外 insert：只传 root
template <class T>
bool insert(const T& x, RBNode<T>* &root) {
    RBNode<T>* node = bstInsert(x, root, nullptr);
    if (!node) return false;   // 重复
    fixColor(root, node);      // 这是纠正颜色的函数，后续继续定义
    return true;
}

修复颜色冲突 fixColor

插入只可能违反 Red Property 或 Root Property，需要分情况处理：

如果新节点的父亲是黑色：所有红黑性质都依然满足，不需要调整。所以只需要在函数中加上一个总条件：

while (node != root && node->parent && node->parent->color == RED) {}
// 只需处理新节点的父节点不黑也不空的情况
root->color = BLACK; // 所有新节点默认是红色，故需要保证根永远黑

如果父亲是红色：必然违反 Red Property，需要分情况修复：

(1) 父亲的兄弟，叔叔 U 也是红：把父亲和叔叔都染黑，祖父染红；然后将祖父作为当前节点递归往上处理直到根。

if (uncle && uncle->color == RED) {
	parent->color = uncle->color  = BLACK;
	grand->color  = RED;
	node = grand;
}

(2) 父亲的兄弟，叔叔 U 是黑 (或空)：类似于 AVL，有四种左右手情况。观察插入节点以及其父节点、祖父节点，分辨插入节点的顺反性质——反式两次旋转 (先旋转父、再交换颜色地旋转祖父)；顺式一次旋转(交换颜色地旋转祖父)，大体与 AVL 类似。

修复颜色的总代码如下：

template <class T>
void fixColor(RBNode<T>* &root, RBNode<T>* node) {
    while (node != root && node->parent && node->parent->color == RED) {
        RBNode<T>* parent = node->parent;
        RBNode<T>* grand  = parent->parent;
        if (!grand) break;
        // parent 是 grand 的左孩子 (L-)
        if (parent == grand->left) {
            RBNode<T>* uncle = grand->right;
            // Case 1: uncle 红，变色上推
            if (uncle && uncle->color == RED) {
                parent->color = uncle->color  = BLACK;
                grand->color  = RED;
                node = grand;
            } 
            else {  // Case 2: uncle 黑/空
                // Case 2.1: node 是反式孩子(LR)，左旋 parent 变成 LL
                if (node == parent->right) {
                    node = parent;
                    leftRotate(root, node);
                    parent = node->parent;
                    grand  = parent->parent;
                }
                //  Case 2.2: node 是顺式孩子(LL)，右旋 grand
                parent->color = BLACK;
                grand->color  = RED;
                rightRotate(root, grand);
            }
        }
        // parent 是 grand 的右孩子(R-)
        else {  // Case 1: uncle 红，变色上推
            RBNode<T>* uncle = grand->left;
            if (uncle && uncle->color == RED) {
                parent->color = uncle->color  = BLACK;
                grand->color  = RED;
                node = grand;
            } 
            else {  // Case 2: uncle 黑/空
                // Case 2.1: node 是反式孩子(RL)，右旋 parent 变成 LL
                if (node == parent->left) {
                    node = parent;
                    rightRotate(root, node);
                    parent = node->parent;
                    grand  = parent->parent;
                }
                // //  Case 2.2: node 是顺式孩子(RR)，左旋 grand
                parent->color = BLACK;
                grand->color  = RED;
                leftRotate(root, grand);
            }
        }
    }
    root->color = BLACK; // 根永远黑
}

整体逻辑如下：

       / 父黑/空 -> 保持根黑，break。
Node 〈        / 叔红 -> 叔、父、祖父，颜色反转；并将祖父作为 Node 递归；
       \ 父红 〈
               \ 叔黑 -> 从 Node 回溯：XY双旋，Y换色；XX单旋换色。

删除函数：双黑 (double black) 思路

删除过程也分两步：

按 BST 删除；
删红无所谓，如果删了黑节点，就会造成路径上黑节点缺少 1：用逻辑上“这个位置是 double black”来表示；然后根据“兄弟节点的颜色、兄弟孩子的颜色”分类讨论：

(1) 兄弟为红：旋转父亲，交换父亲(B)和兄弟(R)，并把兄弟涂黑、父亲涂红。因为交换后的新兄弟节点是原本兄弟(R) 的子节点，一定黑或空，进入情况 (2)。

(2) 兄弟为黑：
- 兄弟孩子全黑或空：兄弟涂红，把 double black 上移；
- 兄弟存在红孩子：类似于红黑树的插入函数，根据这个红侄子与其父、祖父的关系的顺反性，旋转 1/2 次。酌情调整颜色，结束。

详细插删不要求完全掌握，理解整体思路即可：通过局部旋转和颜色翻转，保证那五条红黑性质重新成立。

对比 AVL 与红黑树

AVL：更接近理想平衡，查找更快一些；但插入/删除时旋转更频繁，代码更复杂。
红黑树：平衡要求稍弱，高度最多大约是 AVL 的 2 倍；插入/删除旋转次数少，实际表现更稳定也更常用；对“更新频繁的场景”更适合。

十、回溯 (Backtracking) 与 “隐式树”

虽然回溯不是真正实现“树的结构”，不需要用树节点这些具象化的树构件，但是整套思想完全是用树解题。

每个“决策状态”是一个节点；
每个“选择”生成一个新的状态，是这节点的一个子节点；
一直到“叶子节点”就是某个完整方案（可能成功，可能失败）。

递归版泛型回溯伪代码：

bool solve(Node n) {
    if (n 是叶子) {
        return (n 是一个满足条件的解);
    } else {
        for (每一个 n 的子节点 c) {
            if (solve(c)) return true;
        }
        return false;
    }
}

非递归版用栈模拟：

栈里存的是“当前路径上的节点”；
当走到一个“没路可走”的叶子，就弹出（回溯），尝试兄弟节点。

这里的“Node”未必真的是树节点结构体，也可以是：

一个棋盘状态 (比如 N 皇后里的 x[i] = j)：

void NQueens(int i, int n)  // 初次调用 NQueens(1, N)
	for (int j = 1, j<=n, j++) {  // 枚举第 i 行的列
	    if (isSafe(i, j)) x[i] = j;
	        if (i == n) printResult(x);  // n 行都放好了
	        else NQueens(i+1, n);
	}
}

一个数组（比如“黑白棋子移动”里的 int board[]）。

十一、堆 Heap：优先队列(Priority Queue)

抽象定义

堆是 “按优先级处理元素”，但不把所有元素整体排序的数据类型。典型模式是：不断插入新任务，然后每次取出当前最小或最大的任务处理，比如排序、打印机队列、操作系统调度、路由计算等。这里讨论的堆与内存的堆无关，一般是指二叉堆 (Binary Heap)。

优先队列支持两类核心接口

insert：插入一个元素
deleteMin / deleteMax：删除并返回最小/最大元素

三种实现的对比

堆主要有三种实现：链表、BST (AVL/RB)、二叉堆 (binary heap)。

链表：不排序插入快 O(1)，但找最值 O(N)；保持排序则插入变 O(N)。
BST：平均 O(log N)，最坏 O(N)，自平衡 BST 最坏也能 O(log N)，但 BST 提供了很多优先队列不需要的能力。
vector (二叉堆)：最优解，insert O(log N)，deleteMin O(log N)，findMin O(1)。

因此堆是一种专为优先队列设计的结构：只为了最低成本地插、删顶和看顶。

二叉堆 (Binary Heap)

堆不是“内存里的 heap”，这里专指二叉堆。它有两条性质：结构性 + 有序性。
堆必须是一棵完全二叉树（complete binary tree），并用动态数组形式存储。复习：完全二叉树是每一层都尽量填满，最后一层从左到右填的二叉树。
重要结论：高度 h 约等于 ⌊log N⌋，所以树高是对数级。这就是堆操作能做到 O(log N) 的根本原因。

结构性：数组表示

堆用动态数组存储，节点 i (从 0 开始) 与父/子的索引下标关系：

parent(i) = (i−1)/2；left(i) = 2i+1；right(i) = 2i+2
这样所有节点都可以用 0～N 的连续整数表示，其索引逐行从左到右增大。如下图所示，可以轻易完成动态数组与完全二叉树相互转换：这个关系在类定义中表示为：

template<class T>
class MinHeap {
private:
    std::vector<T> data_;  // 用数组存完全二叉树（层序）
public:
    static std::size_t parent(std::size_t i) { return (i - 1) / 2; }
    static std::size_t left  (std::size_t i) { return 2 * i + 1; }
    static std::size_t right (std::size_t i) { return 2 * i + 2; }
};

有序性 (heap-order property)

对最小堆（MinHeap）：父亲 ≤ 孩子，往根方向值递减，最小值永远在根。
对最大堆（MaxHeap）反过来：父亲 ≥ 孩子，最大值永远在根。

注意：堆只保证 “父子有序”，不保证整棵树像 BST 那样左右有序，所以中序遍历不会得到排序序列。

二叉堆类接口

一个典型模板是：

theSize：当前元素数量
array：vector 存储堆
findMin：看根 O(1)
push / deleteMin：核心操作
buildHeap / percolateDown：内部维护结构

插入 (push) 与上滤 (siftUp) 函数

插入的想法：

把新元素先放到数组末尾 (完全二叉树的下一个空位)。如果它比父亲小，就向上交换，一直交换到合适位置：

// public：
void push(const T &value) {
   data_.push_back(value);     // vector 成员函数，插入在数组尾部
   siftUp(data_.size() - 1);
}
void siftUp(std::size_t idx) {   // 维护元素有序性
   while (idx > 0 && data_[idx] < data_[parent(idx)]) {
      std::swap(data_[idx], data_[parent(idx)]);
      idx = parent(idx);  // 下标更新，继续往上比
   }
}

siftUp: 当 idx>0 不是根且插入元素“比父亲更小，违反最小堆性质”，交换两个元素，并把 idx 移到父亲位置，再继续比较。
复杂度 O(log N)：每次 up 至少上升一层，最多上升树高 h≈log N。

删最小值与下滤 (siftDown) 函数

对于最小堆，删最小项的想法：根是最小值，删掉根后根位置出现空值。为了保持完全二叉树，把最后一个元素搬到根，再让它向下交换到合适位置：每次和两个孩子中更小的那个交换

void deleteMin() {
   if (empty()) return;   // this->empty()：vector 判断空数组的成员方法
   data_[0] = data_.back();
   data_.pop_back();  // 用末尾项的值覆盖根的值 (最小值)
   if (!empty()) siftDown(0);  // 填到根的值很可能过大，要进行下滤
}
void siftDown(std::size_t idx) {
   while (true) {  // 只有左右孩子都大于自己才停止下滤
      std::size_t l = left(idx);
      std::size_t r = right(idx);  // 当前节点的左右孩子
      std::size_t smallest = idx;
      if (l < size() && data_[l] < data_[smallest])  // 小心下标越界！！
          smallest = l;
      if (r < size() && data_[r] < data_[smallest])
          smallest = r;
      if (smallest == idx) break;
      std::swap(data_[idx], data_[smallest]);  // 交换值
      idx = smallest;  // 交换位置
   }
}

deleteMin：把末尾元素挪到根取代最小值，然后删掉末尾，从根向下恢复堆序。
siftDown：循环交换自己与左右孩子的较小项，直到左右孩子都比自己大。注意：每次交换先要确定左右孩子存在 l < size() 防止下标越界。
最多下沉 h 层，因此 O(log N)。

建堆函数 (BuildHeap)

把 N 个元素建堆有两种办法：

N 次 insert：每次 O(log N)，总共 O(N log N)。过于复杂，不做演示。
线性建堆：把数组按层序直接放入堆数组，然后从最后一个非叶子开始做 siftDown，总共 O(N)：

void BuildHeap(vector<T> &vec) {
   if (vec.empty()) return;
   data_.clear();   // 清空
   for (int i = 0; i < vec.size(); i++)
       data_.push_back(vec[i]);    // 无序写入
   for (int i = size() / 2 - 1; i >= 0; --i)  // 逆序进行所有父节点的下滤
   // 或者 （int i = (size()-1)/2-1;i >= 0;i--)
       siftDown(i);
}

关键在于 i = size()/2 - 1。因为数组末尾在 N−1，它的父亲下标 parent(N−1)=(N−2)/2=N/2−1，所以 N/2−1 正是最后一个非叶节点。从这个节点开始，按逆层序 (从下往上、从右往左) 对每个非叶子做 siftDown，就能保证它的子树先成为堆，再把它自己下滤到正确位置，最终全树成堆。

总成本是 O(N)：底层节点很多，但它们下滤的高度很小；高度大的节点很少。把所有节点下滤的“最大可能移动距离”加起来是线性级。

堆排序 heapsort

思路：这里以最大堆为例，优先队列能反复取出最大，因此可以排序：建堆后执行 N 次 deleteMax，堆排序最坏 O(N log N)。每次 deleteMax 后，把堆顶和当前数组末尾交换，堆规模减 1，下滤恢复最大堆。最后数组就是升序。标准 heapsort 代码：

template <class T>
void heapsort( vector<T> & a ) {   // 输入乱序数组
  for( int i = a.size() / 2; i >= 0; i-- )  // buildHeap
    percDown( a, i, a.size() );  // 最大堆的下滤函数
  for( int j = a.size( ) - 1; j > 0; j-- ) {
     swap( a[ 0 ], a[ j ] );  // deleteMax
     percDown( a, 0, j );
  }
}

第一段循环 for i = n/2 ... 0：和 buildHeap 一样，从最后非叶子开始下滤，在线性时间内把 a 变成最大堆。
第二段循环 for j = n−1 ... 1：

swap(a[0], a[j])：把当前最大值放到数组尾部的“已排序区”。

percDown(a,0,j)：只在前 j 个元素组成的堆里下滤（堆缩小），恢复最大堆。

复杂度分析：buildHeap O(N) + N 次 deleteMax O(N log N)，总 O(N log N)。平均性能一般比快排慢一些，但最坏情况稳定，不会退化到 O(N²)，所以是“保险算法”。

注意点

下标越界：siftDown 必须先判断 l/r < size()。
buildHeap 的起点必须是 size/2 − 1。
最小堆/最大堆只差比较符号方向。
堆序只保证父子有序，左右是无序的。
heap vs BST：

heap 不完全有序的，更适合“只要不断取最小/最大”的场景；

BST 完全升序，更适合需要区间查询、按序遍历、删除任意值等。
应用：求数组中 k 个最大元素：

用最大堆建堆，然后 deleteMax k 次 (O(k log n))，总共 O(n + k log n)。

这是非常经典的堆应用。

十二、图 graph

如果对图不熟悉，请先复习：图论基础。

抽象定义

图的定义：图 G = (V, E)，其中 V 是顶点集合，E 是边集合，每条边连接着两个顶点 (v, w)。
有向图与无向图：

如果边 (v, w) 是 (前体，后继) 有序对，意味着从 v 指向 w，w is adjacent to v (反之不成立)，这就是 directed graph。
反之就是 undirected graph，v and w adjacent to each other。没特别说明时 “graph” 指无向图。

路径、环与连通

路径：顶点序列 w1, w2, …, wN，只要相邻顶点之间都有边。
简单路径：不重复经过任何顶点。
环 cycle：起点终点同一个顶点；简单环不重复经过顶点。有向图里的这些概念完全类似，只是边必须方向一致。
连通图：任意两点之间都有路径。
完全图：任意两点之间直接有边。完全图一定连通，但连通图不一定完全。
DAG：有向无环图 directed acyclic graph。
强连通：在有向图中任意两点互相可达。
弱连通：忽略方向后连通，但考虑方向不一定可达。
加权图：如果边带权值（距离、成本、容量等等），就是 weighted graph。既可以无向也可以有向。

两种实现：邻接矩阵和邻接表

图只有两个基本功能：A. 判断一个点的邻接点、B. 判断两点间是否有边，为了路由和遍历。

邻接矩阵 adjacency matrix

n 个点编号 0~n-1，用 n×n 的二维数组 matrix，空间复杂度 O(|V|²)，适合稠密图 (边多)，擅长 B：用“表格查字典”的方式 O(1) 判断是否有边：

普通有向图matrix[i][j] = 1 表示 i 到 j 有边；无边记作 0。
加权图 matrix[i][j] = 权值；无边记为 ∞。
无向图矩阵对角对称：matrix[i][j] = matrix[j][i]。

邻接表 adjacency list

对每个顶点 i 维护一个链表/动态数组，存储所有与 i 相邻的顶点 j，对所有 i 组成一个映射表。空间 O(|V|+|E|)，适合稀疏图 (边少)，擅长 A： O(N) 遍历桶找边。无向图每条边会在表中出现两次。

图遍历：DFS 与 BFS

遍历的目标：从起点 v 出发访问所有可达点；如果图不连通，就只得到连通的部分。遍历要标记访问过的点，否则遇到环会死循环。

深度优先搜索 Depth First Search

思路：从某点开始，标记经过的点防止重复，走到不能走再回溯一步继续走，直到回溯回原点或全部点都走到过。
DFS 的思路类似于树的前序遍历 (但没有左右要求)，其回溯顺序说明可以用栈来实现。(函数递归利用了系统栈) 递归思路：

#include <vector>
const int MAXN = 1000;  // 最大顶点数
std::vector<int> adj[MAXN];  // 邻接表：数组套向量，adj[v] 是 v 的邻居
bool visited[MAXN] = {false};  // 标记是否访问过

void dfs_recursive(int v) {  // 从顶点 v 开始做 DFS
    visited[v] = true;              // 标记 v 已访问
    // 这里可以做“访问动作”，例如 printf("Visit %d\n", v);
    for (int u : adj[v]) {  // 遍历 v 的所有邻居 u
        if (!visited[u]) {
            dfs_recursive(u);  // 对没访问过的邻居递归 DFS
        }
    }
}

栈迭代思路：栈保证 LIFO，因此搜索波推到底后按层回溯。

const int MAXN = 1000;
std::vector<int> adj[MAXN];  // 邻接表：数组套向量
bool visited[MAXN];          // 是否访问过

void dfs_iterative(int start, int n) { // n 是顶点个数
	visited[MAXN] = {false};
    // “手写”一个栈：用数组 + top 指针
    int st[MAXN];  // 栈数组
    int top = -1;  // 栈空时 top = -1
    int nextChild[MAXN] = {0};  // “游标数组”，记录对每个顶点的邻接表扫描到哪
    // 把 start 压栈，并标记访问
    st[++top] = start;
    visited[start] = true;
    while (top >= 0) {   // 主循环：只要栈不空，就一直搜索
        int v = st[top];   // 栈顶点
        int &idx = nextChild[v];    // 引用：记录当前扫描到第几号邻居
        int deg = (int)adj[v].size();   // v 的度数 = 邻居个数
        // 跳过已经访问过的邻居
        while (idx < deg && visited[adj[v][idx]]) ++idx;
        if (idx == deg) {  // 没有未访问邻居，回溯
            --top;  // 对应 s.pop()
        } else {  // 找到了一个未访问的邻居 u
            int u = adj[v][idx];
            ++idx;  // 下次从下一个邻居开始查
            st[++top] = u;
            visited[u] = true;
            // std::cout << "Visit " << u << "\n";
        }
    }
}

想象一张六点有向图：a 作为 start，连接着 b、c、d，而 c 连着 e、f。栈 (左底右顶) 的逐步变化如下：a → ab → a → ac → ace → ac → acf → ac → a → ad → a → NULL ，出栈顺序为：b, e, f, c, d, a ，忽略 a 的话可以看出递归遍历

广度优先搜索 Breadth First Search

思路：从某点开始，一层层扩展，先访问所有距离 1 的点，再访问距离 2 的点……由近到远地遍历。
BFS 的思路类似于堆数组的遍历，其按层推进竖屏可以用队列来实现。队列迭代思路：队列保证 FIFO，因此搜索波前按层推进。

#include <vector>
#include <queue>
#include <iostream>
void bfs(int start, const std::vector<std::vector<int>> &adj) {
    int n = adj.size();
    std::vector<bool> visited(n, false);
    std::queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int w = q.front(); 
        q.pop();
        std::cout << "Visit " << w << '\n';   // 访问动作
        for (int u : adj[w]) {               // 枚举 w 的所有邻居 u
            if (!visited[u]) {
                visited[u] = true;           // 标记
                q.push(u);                   // 入队
            }
        }
    }
}

想象一张六点有向图：a 作为 start，连接着 b、c、d，而 c 连着 e、f。队列 (左头右尾) 的逐步变化如下：a → NULL → b → bc → bcd → cd → d → de → def → ef → f → NULL ，出队顺序为：a, b, c, d, e, f ，可以看出明显是逐层遍历

DFS 和 BFS 具体程序写法不必完全掌握，但要会理解遍历顺序，例如下图： a) [a, c, f, e, b, d, h, g] 或 [a, b, d, c, g, f, e, h] 等等

b) [a, b, c, d, f, g, e, h] 或 [a, c, b, g, f, e, h, b] 等等

路由：最短路问题

无权最短路

从起点 s 到所有点的最短路径，度量是边数，算法本质就是 BFS ——层数就是“最少边数”：

// include <...>   using std::...;
void unweighed_router(int s, const vector<vector<int>> &adj, vector<int> &dist, vector<int> &prev) {
    int n = (int)adj.size();
    dist.assign(n, -1);  // 长度设为 n，所有元素初始化为 -1：“未知/不可达”
    prev.assign(n, -1);
    queue<int> q;
    dist[s] = 0;         // s 到自己的距离是 0
    q.push(s);
    while (!q.empty()) {
        int v = q.front();   // first in
        q.pop();             // first out
        for (int w : adj[v]) {           // 扫描 v 的邻居 w
            if (dist[w] == -1) {         // 如果第一次到达 w
                dist[w] = dist[v] + 1;   // 最少边数 = 父节点 + 1
                prev[w] = v;             // 记录前驱，用于回溯路径
                q.push(w);
            }
        }
    }
}

有权最短路：Dijkstra 算法

边权非负的前提下，尽量贪心。从 s 开始，对所有相邻点，如果当前点的距离+边权重比记录值更小，就更新距离，跳过未到达过的点和距离记录不是最小的情况：

// 省略 include ..., using ...
// 邻接表：adj[v] = { {neighbour, weight}, ... }
using Graph = vector<vector<pair<int,int>>>;
void dijkstra(int s, const Graph &adj, vector<int> &dist, vector<int> &prev) {
    int n = (int)adj.size();
    dist.assign(n, -1);   // -1 表示“未知/不可达”
    prev.assign(n, -1);
    using P = pair<int,int>; // {当前距离, 顶点}
    priority_queue<P, vector<P>, std::greater<P>> pq;
    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d != dist[v]) continue;  // 如果队列里的是旧距离，就跳过
        for (auto [w, wgt] : adj[v]) {
            if (dist[v] == -1) continue;  // 如果 v 本身不可达就跳过
            int alt = dist[v] + wgt;
            // w 还没到过 || 找到更短的距离 alt
            if (dist[w] == -1 || alt < dist[w]) {
                dist[w] = alt;
                prev[w] = v;
                pq.push({alt, w});
            }
        }
    }
}

复杂度：

用普通数组找最小 dist，O(|V|²)。
用优先队列，O(|E| log|V|)。

拓扑排序 Topological Sort

对于 DAG，输出一个线性序列，使得每条边 u→v 都满足 u 在 v 前面。DFS 版本：

对图做 DFS，记录每个点的“完成时间 finishing time”（某点所有后继都 DFS 完才算完成）。
每当一个点完成，就把它插到链表头部。
最终链表顺序就是拓扑序。在 DAG 中，若有 u→v，那么 DFS 中 v 的完成时间一定早于 u（v 要么被 u 深入时访问完成，要么先前完成），因此把完成晚的放前面，保证 u 在 v 前。复杂度 O(|V|+|E|)。

注意点

搜索和路径问题通用的常用成员：

visited：vector<bool> visited(n,false);
dist：vector<int> dist(n, -1); (也可以用 INFINITY)
path / predecessor：vector<int> prev(n, -1); 邻接表常用结构：

vector<vector<pair<int,int>>> adj; 
// adj[v] = {(w, weight), ...}

“对 w 所有邻接点 v” 就是：for (auto [w, wt] : adj[v]) { ... }
BFS 用 queue<int>；DFS 用 stack<int>；Dijkstra 用 priority_queue

小练习

请用二叉搜索树证明：${17\over 7} < log_27$。

→ 构建一个 7 节点 AVT 并使每个节点距离根的遍历距离的和为 17，根据遍历时间复杂度复杂度 O(logN) 得到答案
请把 std::vector 的用法 array[index]=value 写成操作符形式。

→ array.operator[](index) = value
请推导用 minimum heapsort 排序 N 个元素的时间复杂度 O 以及最小复杂度 Ω，它会向冒泡排序或树排序那样 “退化” 吗？

→ <buildHeap> O(N) + N x <deleteMin> O(log N) = O(N + NlogN) = O(NlogN)；最小复杂度也一样；不会退化，因为输入数据的有序性没有影响。
所有的平衡 BST 设计方案的根本目的是什么？

→ 防止树退化为链表导致 (除了遍历) 时间复杂度从 O(logN) 降为 O(N)。
请推导 N 节点的 RBTree 高度取值范围。

→ 红黑树高度、节点数与黑高的关系： $h ≤ 2\ bh\ ,\ N ≥ 2^{bh} - 1\ \to\ h ≤ 2 log_2(N + 1)$；同时，所有树高度与节点都有以下关系：$N≤ 2^{h+1}-1\ \to\ h≥log_2(N+1)-1$。所以红黑树高度关于 N 的取值范围为：$h∈[⌈log_2(N+1) - 1⌉,\ ⌊2 log_2(N + 1)⌋]$
DFS 的遍历顺序可以是三种树遍历中的哪一个？DFS 可以直接用递归实现说明递归和哪种数据结构逻辑相同？

→ 前序；递归本质上是在使用计算机 (内存) 的栈。
请找错：

#include <vector> <queue>     // 不能一行写两个 std 引用
// 漏写了 using std::vector; 和 using std::queue; 或者 using namespace std;
void bfs(int start, const vector<vector<int>> &adj) {
    int n = adj.size();    
    // vector 的 .size() 返回数据是 size_t 类，需要强制 (int)adj.size();
    vector<bool> visited[n] = {false};
    // 这个用法在只对初始化数组才有用，改成 vector<bool> visited(n, false);
    queue<int> q;
    visited[start] = true;
    q.push_back(start);   
    // 栈、队列、优先队列的插入末尾的函数名字是 .push()
    /*......*/
}

一个红黑树的部分结构如下，现在要在 (1) 插入 5，插在哪里，如何调整？要在 (2) 删除 5，如何调整？

 (1)      7(B)       (2)          4(B)
         /    \                  /   \ 
      6(B)   10(B)             2(B)   6(B)  
      /     /    \             /     /   \
    4(R)   8(R)   12(R)     1(B)   5(B)   9(B)
                                         /
                                       8(R)

(1) 作为 4 的右孩子；先左旋 4 然后右旋 6 并反转 5 和 6 的颜色。

(2) 右旋 9 然后左旋 6 并涂黑 8。

CSC3200

C++ 数据结构(非线性) ：树、堆、图

六、树 Tree

树的抽象定义

树的基础实现

树与递归

树的遍历顺序

前序 (preorder) 逻辑：

后序 (postorder) 逻辑：

中序 (inorder) 逻辑：

七、二叉树 Binary Tree

高度与高度-节点定律

最大/最小高度的结论

二叉搜索树 BST

二叉节点类

查找 find(x, t) 函数

找最小、最大项函数

插入 insert(x, t) 函数

删除 remove(x, t) 函数的三种情况

BST 的效率与退化

TreeSort——用树进行二分法排序

八、平衡二叉搜索树 AVL

通过左右旋转 “保持平衡”

左右旋

四种情况与 “顺反结构”

AVL 的插入/删除函数

九、红黑二叉搜索树

抽象定义

RBTree 和 AVL 的关系

红黑树的五条性质

红黑树的节点结构

左右旋与 moveDown 辅助函数

插入函数：先按 BST 插，再“修颜色 + 旋转”

修复颜色冲突 fixColor

删除函数：双黑 (double black) 思路

对比 AVL 与红黑树

十、回溯 (Backtracking) 与 “隐式树”

十一、堆 Heap： 优先队列(Priority Queue)

抽象定义

三种实现的对比

二叉堆 (Binary Heap)

结构性：数组表示

有序性 (heap-order property)

二叉堆类接口

插入 (push) 与上滤 (siftUp) 函数

删最小值与下滤 (siftDown) 函数

建堆函数 (BuildHeap)

堆排序 heapsort

注意点

十二、图 graph

抽象定义

两种实现：邻接矩阵和邻接表

邻接矩阵 adjacency matrix

邻接表 adjacency list

图遍历：DFS 与 BFS

深度优先搜索 Depth First Search

广度优先搜索 Breadth First Search

路由：最短路问题

无权最短路

有权最短路：Dijkstra 算法

拓扑排序 Topological Sort

注意点

小练习

十一、堆 Heap：优先队列(Priority Queue)