假设图 G 的每个切割都包含一条横跨该切割的唯一轻量级边（即最小权重的边）。我们需要证明 G 存在一棵唯一的最小生成树。

要证明在连通图G=(V,E)中，如果e是某条环路上权重最大的边，则图G'=(V,E-{e})中存在一棵最小生成树，这棵生成树同时也是G的最小生成树，我们可以按照以下步骤进行：...

我在前面的文章中，已经详细讲解了二叉搜索树（二叉搜索树的模拟实现-CSDN博客）、AVL树（AVL树模拟实现-CSDN博客）的模拟实现，终于，我要讲解红黑树啦~~~，让我们进入正题吧...

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。...

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述...

AVL树，是一种“平衡”的二叉搜索树，关于搜索树的介绍和模拟，我已经在该篇文章（二叉搜索树的模拟实现-CSDN博客）介绍过，想复习或者了解二叉搜索树的读者可以去看看哦...

四、利用练习 21.4-2 ，请给出一个简单的证明，证明在一个不相交集合森林上使用按秩合并策略而不使用路径压缩策略的运行时间为 O(m lgn) 。21.4-2 的内容是：“证明：每个结点的秩最多为 ⌊lgn⌋ 。”。如果要写代码，请用go语...

三、给出一个包含 m 个 MAKE-SET 、UNION 和 FINDSET 操作的序列(其中有 n 个是 MAKE-SET 操作)，当仅使用按秩合并时，需要 Ω(mlgn) 的时间。如果要写代码，请用go语言。...

一、用按秩合并与路径压缩启发式策略的不相交集合森林重做练习21.2-2。如果要写代码，请用go语言。

二、对定理 21.1 的整体证明进行改造，得到使用链表表示和加权合并启发式策略下的 MAKE-SET 和 FIND-SET 的摊还时间上界为 O(1)，以及 UNION 的摊还时间上界为 O(lgn)。如果要写代码，请用go语言。...