データ構造のトーナメントツリー徹底解説！勝者ツリーと敗者ツリーの違い

本記事では、データ構造の一つであるトーナメントツリーについて、勝者ツリー（Winner Tree）と敗者ツリー（Loser Tree）の違いを交えながら詳しく解説します。

トーナメントツリーとは？

トーナメントツリーとは、n個の外部ノード（葉）と n−1 個の内部ノードから構成される完全二分木です。外部ノードは選手（プレイヤー）を表し、内部ノードは2人の選手が対戦した結果の勝者を表します。スポーツのトーナメント表をイメージすると理解しやすく、この木は「セレクションツリー（選択木）」とも呼ばれます。

トーナメントツリーの主な性質

• 根付き木である： 親から子へ向かう有向パスが存在し、親を持たない要素（根）は必ず1つだけです。
• 親子間の大小関係が一定： 親の値は子の値以下であることが基本ですが、比較演算子は任意のものを使用できます。ただし、木全体を通じて親と子の相対的な大小関係が不変である必要があります。
• 穴（ホール）の存在： ノード数が2の冪乗でない場合、木には「穴」が含まれることがあり、穴は木の任意の場所に現れます。
• 二分ヒープの一般化： トーナメントツリーは二分ヒープをより汎用的に拡張した構造です。
• 根が全体の勝者： 木の根には、トーナメント全体の勝者（最小値または最大値）が格納されます。

トーナメントツリーには、以下の2種類があります。

• 勝者ツリー（Winner Tree）
• 敗者ツリー（Loser Tree）

勝者ツリー（Winner Tree）

勝者ツリーとは、各ノードがその2つの子のうち小さい方（または大きい方）を表す完全二分木のことです。根には木全体の中で最小（または最大）の値が保持され、トーナメント全体の勝者、すなわちすべての系列の中で最小または最大のキーが求まります。また、勝者ツリーは O(log n) の時間で構築できることも容易に確認できます。

例： キーとして「3, 5, 6, 7, 20, 8, 2, 9」が与えられた場合、最小値を求める勝者ツリーは次のように構成されます。

敗者ツリー（Loser Tree）

敗者ツリーも、n人のプレイヤーに対する完全二分木であり、n個の外部ノードと n−1 個の内部ノードを持ちます。大きな違いは、内部ノードに試合の敗者を格納する点です。そして、全体の勝者は別途 tree[0] に保存されます。

敗者ツリーは、対応するノードに試合の敗者を記録する代替的な表現方法です。その最大の利点は、勝者を出力した後に木を再構成する際、葉から根までの経路上のノードだけを調べればよく、経路上のノードの兄弟を参照する必要がないという点にあります。これにより、再構築処理が効率化されます。

敗者ツリーの構築手順

敗者ツリーを作成するには、まず勝者ツリーを構築する必要があります。

例： キーとして「10, 2, 7, 6, 5, 9, 12, 1」が与えられた場合、まず最小値の勝者ツリーを作成します。

次に、各内部ノードに試合の敗者を格納していきます。

まとめ

トーナメントツリーは、複数の系列から最小値や最大値を効率的に選択するための強力なデータ構造です。勝者ツリーは直感的で理解しやすい一方、敗者ツリーは再構成時の比較回数を削減できるため、外部ソートなどの実用場面で高い性能を発揮します。用途に応じて両者を使い分けることが重要です。