路径压缩和按等级合并如何相互补充?
How do path compression and union by rank complement each other?
我一直在阅读联合查找问题。两个主要改进是路径压缩和按等级联合。据我了解,按等级联合用于确定如何组合不相交的树。如果我们有两棵不相交的树 T1 和 T2,那么我们将等级较小的树的根连接到等级较高的树。如果我们不使用路径压缩,那么等级就是树的深度。这是有道理的,因为我们不想增加树的深度,因为它直接影响查找和联合。
我的问题是当我们也使用路径压缩时。我一直在读到这两个优化相互补充,但我没有看到。由于路径压缩,等级不再是树的深度(它成为深度的上限)。假设T1有2个分支(令T1的秩为3),T2的深度为2,秩为2。现在假设我们对T1下面标有“*”的叶子进行查找操作(路径压缩)。现在,如果我们合并 T1 的根和 T2 的根,那么 T2 将附加到 T1 的根(因为等级不会通过查找更新)。生成的树的深度为 3。但是如果将 T1 附加到 T2,我们可以获得更好的性能。
T1: o (Rank = 3) T2: o (Rank = 2)
/ \ |
o o o
| |
o o
|
*
在 T1("*") 的叶子上找到后,然后在 T1 和 T2 的根上并集,我们得到
T1: o (Rank = 3) T2: o (Rank = 2)
/| |\ |
* o o o o
|
o
Result of T1 union T2
o
/ | | |\
* o o o o Rank = 3 and Max Depth = 3
|
o
|
o
我在这里遗漏了什么吗?路径压缩和按等级合并如何相互补充?我知道等级只是树深度的上限,但我看不到按等级合并如何提高结构的整体性能。这比随机组合根的并集好在哪里?
提前感谢您的帮助。
按等级合并确保树的最大深度为 log N,因此它在每个操作上设置了 O(log N) 的最坏情况上限。
没有任何特殊联合的路径压缩规定每个操作的摊销成本的上限为 O(log N),但不限制最坏情况成本。 (摊销成本甚至可能有更严格的限制,但我知道如何证明 O(log N))
将两者结合使用,您可以得到最坏情况下的 O(log N) 限制 和 分摊界限提高到 O((N)),这实际上是常数。这样两种优化是互补的。
你是对的,有些操作序列按等级联合并不是绝对最优的,但是保证比没有它的情况要好,这就是计数。我们通常不会花精力优化 最佳 案例性能。我们优化了最差或平均情况。
问题中的图形 T2,如果您使用 rank/weight 的并集,则无法首先形成。
自己用 3 个节点试试,看看能不能画出图 T2。这是不可能的。连图T1都无法一开始就形成
您可以从 N 个节点的示例开始,如果您从头开始按 rank/weight 进行合并,您实际上会看到它会给出最佳合并结构(一些操作序列可能不会给出最好的合并,但大多数时候它会给出最好的结果)。
换句话说,rank/weight 的联合有助于查找方法(in-turn 使用路径压缩来进一步优化),这使得查找操作几乎是恒定时间操作。
我一直在阅读联合查找问题。两个主要改进是路径压缩和按等级联合。据我了解,按等级联合用于确定如何组合不相交的树。如果我们有两棵不相交的树 T1 和 T2,那么我们将等级较小的树的根连接到等级较高的树。如果我们不使用路径压缩,那么等级就是树的深度。这是有道理的,因为我们不想增加树的深度,因为它直接影响查找和联合。
我的问题是当我们也使用路径压缩时。我一直在读到这两个优化相互补充,但我没有看到。由于路径压缩,等级不再是树的深度(它成为深度的上限)。假设T1有2个分支(令T1的秩为3),T2的深度为2,秩为2。现在假设我们对T1下面标有“*”的叶子进行查找操作(路径压缩)。现在,如果我们合并 T1 的根和 T2 的根,那么 T2 将附加到 T1 的根(因为等级不会通过查找更新)。生成的树的深度为 3。但是如果将 T1 附加到 T2,我们可以获得更好的性能。
T1: o (Rank = 3) T2: o (Rank = 2)
/ \ |
o o o
| |
o o
|
*
在 T1("*") 的叶子上找到后,然后在 T1 和 T2 的根上并集,我们得到
T1: o (Rank = 3) T2: o (Rank = 2)
/| |\ |
* o o o o
|
o
Result of T1 union T2
o
/ | | |\
* o o o o Rank = 3 and Max Depth = 3
|
o
|
o
我在这里遗漏了什么吗?路径压缩和按等级合并如何相互补充?我知道等级只是树深度的上限,但我看不到按等级合并如何提高结构的整体性能。这比随机组合根的并集好在哪里?
提前感谢您的帮助。
按等级合并确保树的最大深度为 log N,因此它在每个操作上设置了 O(log N) 的最坏情况上限。
没有任何特殊联合的路径压缩规定每个操作的摊销成本的上限为 O(log N),但不限制最坏情况成本。 (摊销成本甚至可能有更严格的限制,但我知道如何证明 O(log N))
将两者结合使用,您可以得到最坏情况下的 O(log N) 限制 和 分摊界限提高到 O((N)),这实际上是常数。这样两种优化是互补的。
你是对的,有些操作序列按等级联合并不是绝对最优的,但是保证比没有它的情况要好,这就是计数。我们通常不会花精力优化 最佳 案例性能。我们优化了最差或平均情况。
问题中的图形 T2,如果您使用 rank/weight 的并集,则无法首先形成。
自己用 3 个节点试试,看看能不能画出图 T2。这是不可能的。连图T1都无法一开始就形成
您可以从 N 个节点的示例开始,如果您从头开始按 rank/weight 进行合并,您实际上会看到它会给出最佳合并结构(一些操作序列可能不会给出最好的合并,但大多数时候它会给出最好的结果)。
换句话说,rank/weight 的联合有助于查找方法(in-turn 使用路径压缩来进一步优化),这使得查找操作几乎是恒定时间操作。