锦标赛树 (胜者树)

什么是锦标赛树？

锦标赛树是一种完全二叉树，其中每个节点代表一个玩家。最后一层有 n-1 个节点（外部节点），用于表示所有玩家，其余节点（内部节点）表示他们之间的胜者或败者。它也被称为选择树。

以下是锦标赛树的一些重要性质

1. 每个内部节点的值始终等于其子节点之一。
2. 锦标赛树可能存在空洞。节点少于 2 ^ (n+1) -1 的锦标赛树包含空洞。空洞代表玩家或队伍的缺席，可以存在于树的任何位置。
3. 锦标赛树中的每个节点都与其前驱和后继相连，并且所有节点之间存在唯一的路径。
4. 它是一种二叉堆（最小堆或最大堆）。或者我们可以说它是堆的应用。
5. 根节点代表比赛的获胜者。
6. 要找出获胜者或败者（最佳玩家），我们需要进行 N-1 次比较。

锦标赛树的类型

每场比赛都存在一个败者和一个胜者。因此，有两种方法可以表示这两种想法：

1. 胜者树，和
2. 败者树

什么是胜者树？

在锦标赛树中，当内部节点代表比赛的获胜者时，得到的树称为胜者树。每个内部节点存储其子节点中的最小值或最大值，具体取决于获胜标准。当获胜者是较小的值时，胜者树称为最小胜者树，当获胜者是较大的值时，败者树称为最大胜者树。

比赛的获胜者始终是所有玩家或值中的最小值或最大值，可以在 O(1) 时间内找到。创建胜者树所需的时间是 O(Log N)，其中 N 代表玩家的数量。

问：八名玩家参加一场比赛，每名玩家用数字 1 到 8 表示。这些玩家的配对如下：

A 组：1, 3, 5, 7 (比赛：1 - 7 和 3 - 5)

B 组：2, 4, 6, 8 (比赛：2 - 6，和 4 - 8)

获胜标准 - 数值最大的玩家赢得比赛。表示此锦标赛树的胜者树（最大胜者树）。

胜者树（最大胜者树）如下图所示。

这里形成的树是一个最大堆，所有父节点的值都等于或大于其子节点，获胜者是 8，这是所有玩家中最大的。

我们可以从中观察到，每个锦标赛树都是一棵二叉树，但反之不然，因为在锦标赛树中，获胜者总是等于其子节点之一，但在二叉堆中，父节点不总是等于其子节点。

什么是败者树？

在锦标赛树中，当内部节点用于表示两者之间的比赛的败者时，得到的树称为败者树。当败者是较小的值时，败者树称为最小败者树，当败者是较大的值时，败者树称为最大败者树。

它也被称为最小或最大败者树。这里也应用了相同的思想，败者（或父节点）总是等于其子节点之一，并且败者总是所有玩家中最大的或最小的，可以在 O(1) 时间内找到。此外，创建败者树所需的时间是 O(Log N)，其中 N 是玩家的数量。

问：八名玩家参加一场比赛，每名玩家用数字 1 到 8 表示。这些玩家的配对如下：

A 组：1, 3, 5, 7 (比赛：1 - 7 和 3 - 5)

B 组：2, 4, 6, 8 (比赛：2 - 6，和 4 - 8)

获胜标准 - 数值最大的玩家赢得比赛。表示此锦标赛树的败者树（最小败者树）。

得到的败者树（最小败者树）如下图所示。

这里得到的树是一个最小堆，父节点的值小于或等于其子节点，1 是比赛的总败者。

找出第二名

在胜者树中，获胜者位于树的顶部。现在的问题是如何找出比赛的第二名。这里需要注意的是，第二名只被第一名打败。要找出第二名，我们需要检查与第一名进行的最后两场比赛（或比较）。让我们通过一个例子来看看这个想法。

这里，8 是比赛的获胜者，当我们寻找第二名时，我们发现 7 是第二名。

锦标赛树的应用

1. 它可以找到数组中的最大或最小值。
2. 它通常用于排序。
3. 它可以用于 M 路归并。
4. 它用于查找已排序数组的中位数
5. 它也用于卡车装载问题

如何使用锦标赛树查找 N 个已排序数组的中位数？

锦标赛树的一个应用是查找 N 个已排序数组的中位数。最小胜者树用于高效查找中位数。

我们将数组放在锦标赛树的叶子节点，并将获胜者放入内部节点。

让我们通过一个例子来理解这一点。

假设有三个已排序的数组如下：

A = {12, 14, 15, 16, 17, 19}

B = {4, 5, 8, 10}

C = {1, 3, 6, 7, 9}

的大小分别为 6、4 和 5。

排序合并后的数组 = {1, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 17, 19}

元素总数 = 15

中位数 = (N + 1) / 2 = (15 + 1) / 2 = 8。

第八个元素是中位数 = 10。树的高度使用 Log₂(M) 计算，其中 N 是数组的数量。我们取计算值的上限。这里，Log₂(3) = 1.585 @ 2。所以，我们需要构造的树的高度为 2，有 4 个叶子节点，如下图所示。

现在，第一个锦标赛树的最小胜者树如下所示。

这里需要注意的是，在最后一个叶子节点我们填充了无穷大，这样与它进行的比赛总是由另一个元素获胜，当数组中的元素用完时，我们在该叶子节点中填充无穷大。

在这里，来自数组 C 的 1 是锦标赛的获胜者。所以，下一个元素 = 3 来自数组 C 替换它。

第二场锦标赛的最小胜者树如图所示。

这里，3 是锦标赛的总获胜者。在下一场比赛中，来自数组 C 的 6 将替换它。

第三场锦标赛的最小胜者树如图所示。

这里，4 是锦标赛的总获胜者。所以，在下一场比赛中，来自数组 B 的 5 将替换它。

为了找到中位数元素，在本例中是第八个元素。我们需要总共进行八场锦标赛。我们对剩余的锦标赛遵循相同的步骤，相应的树如下所示。

在第 8 场锦标赛之后，我们得到数组的中位数。

将大小为 n₁, n₂, n₃, …... n_n 的 N 个已排序数组合并成一个已排序数组的时间复杂度是 O((n₁ + n₂ + ….. + n_n) * Log₂N)，而查找中位数的时间复杂度是 O(m * Log₂N)，其中 m 是中位数的位置。

当 N 个数组的大小相等时，合并它们的时间复杂度变为 O(M * Log₂N)，其中 m 是数组的大小。