【C++】順序統計アルゴリズムでリストからi番目に大きい数を求める方法

この記事では、順序統計アルゴリズム（Order-Statistic Algorithm）を用いて、指定されたリスト（配列）の中から i 番目に大きい数を求めるC++プログラムを紹介します。この手法は、二分探索木（BST）にデータを挿入し、各ノードにランク（順位）を割り当てることで、任意の順位の要素を効率的に取り出せる点が特徴です。

アルゴリズムの概要

全体の流れは「挿入 → ランク割り当て → 選択」の3つのステップで構成されています。それぞれの関数の動作を詳しく見ていきましょう。

1. Insert()：木へのノード挿入

引数として根（root）と挿入する値 d を受け取ります。

• 木が完全に空の場合は、新しいノードを根として挿入します。
• d が現在のノードの値より小さい場合は、ポインタを左の子へ移動します。
• d が現在のノードの値より大きい場合は、ポインタを右の子へ移動します。
• 同じ値が既に存在する場合は、そのノードのカウントを増やします。

2. AssignRank()：各ノードへのランク割り当て

中順走査（in-order traversal）を行うことで、昇順に並んだ順位（ランク）を各ノードに付与します。左の子 → 自身 → 右の子の順に処理し、訪問ごとにカウンタを増加させます。これにより、最小の要素がランク0、次がランク1となり、以降同様に順位が確定します。

3. Select()：k番目に小さい要素の検索

引数として根と検索対象の順位 k を受け取ります。

• 現在のノードのランクが k と一致すれば、そのデータを返して終了します。
• ランクが k より大きければ、左部分木へ移動します。
• ランクが k より小さければ、右部分木へ移動します。

サンプルコード

以下が完全なC++プログラムです。配列 {4, 7, 6, 1, 10, 3, 2, 15, 16, 20} から、ユーザーが指定した k 番目に大きい要素を出力します。

#include<iostream>
using namespace std;
static int cnt = 0;

struct nod // ノードの宣言
{
    int data;
    int rank;
    nod *l;
    nod *r;
};

nod* CreateNod(int d) // 新しいノードの作成
{
    nod *newnod = new nod;
    newnod->data = d;
    newnod->rank = 0;
    newnod->l = NULL;
    newnod->r = NULL;
    return newnod;
}

nod* Insert(nod* root, int d) // ノードの挿入
{
    nod *tmp = CreateNod(d);
    nod *t = root;
    if(root == NULL)
        root = tmp;
    else {
        while(t != NULL) {
            if(t->data < d ) {
                if(t->r == NULL) {
                    t->r = tmp;
                    break;
                }
                t = t->r;
            } else if(t->data > d) {
                if(t->l == NULL) {
                    t->l = tmp;
                    break;
                }
                t = t->l;
            }
        }
    }
    return root;
}

void AssignRank(nod *root) // 各ノードにランクを割り当てる
{
    if(root->l != NULL)
        AssignRank(root->l);
    root->rank = cnt;
    cnt++;
    if(root->r != NULL)
        AssignRank(root->r);
}

int Select(nod* root, int k) // k番目に小さい要素を選択
{
    if(root->rank == k)
        return root->data;
    else if(root->rank > k)
        return Select(root->l, k);
    else
        return Select(root->r, k);
}

void display(nod *root) // 木の内容を表示
{
    if(root->l != NULL)
        display(root->l);
    cout<<"\n data: "<<root->data<<" rank: "<<root->rank;
    if(root->r != NULL)
        display(root->r);
}

int main() {
    char c;
    int n, i, k, a[10]={4,7,6,1,10,3,2,15,16,20};
    nod *root = NULL;

    for(i = 0; i < 10; i++)
        root = Insert(root, a[i]); // insert() の呼び出し

    cout<<"Enter the value of k: ";
    cin>>k;

    AssignRank(root); // AssignRank() の呼び出し
    cout<<"\nRank associated to each node:-";
    display(root); // display() の呼び出し
    cout<<"\n\nThe kth Largest element is: "<<Select(root, 10-k);
    return 0;
}

ポイント：k番目に大きい＝(n−k)番目に小さい

このプログラムのSelect()関数は「k番目に小さい」要素を返すため、main関数内では Select(root, 10-k) と呼び出しています。全要素数 n が10個なので、「7番目に大きい要素」は「10−7＝3番目に小さい要素」と一致するという性質を利用しています。

実行結果

Enter the value of k: 7
Rank associated to each node:-
data: 1 rank: 0
data: 2 rank: 1
data: 3 rank: 2
data: 4 rank: 3
data: 6 rank: 4
data: 7 rank: 5
data: 10 rank: 6
data: 15 rank: 7
data: 16 rank: 8
data: 20 rank: 9
The kth Largest element is: 4

k = 7 を入力すると、各ノードに0〜9のランクが正しく割り当てられ、7番目に大きい要素として 4 が出力されます。

まとめ

順序統計アルゴリズムでは、二分探索木への挿入に O(log n)、ランク割り当てと選択にもそれぞれ木の高さに比例した時間でアクセスできるため、ソート全体を行わずに特定順位の要素を取得できます。ただし、挿入順序によっては木が偏り最悪計算量が O(n) になる点には注意が必要です。平衡二分探索木（AVL木や赤黒木）と組み合わせれば、常に安定した性能を実現できます。