はじめに

どうも。aqualengthです。¹

この記事は、「木 Advent Calendar 2023」の21日目です。
昨日の記事は箱さんの木に関する数学の論文の紹介でした。
明日の記事はNullPointerExceptionです。

今日はC言語で木の実装をするときに使える(主に高速化の)テクニックを紹介していきます。
想定はC言語ですが、一部のテクニックを除きC言語以外の言語でも使えるテクニックになっています。
あくまでテクニックの紹介なので、具体的な実装については省略します。

目次

はじめに
目次
ポインタではなくインデックスを持つ
配列の構造体ではなく、構造体の配列で持つ
1-indexedで持つ
二重連鎖木
子だけでなく親の情報も持つ

ポインタではなくインデックスを持つ

適用範囲:グラフ全般

メモリ確保のコストやキャッシュヒット率を考えれば、ノード毎にメモリを確保するより必要な分まとめて確保する方が高速に動作します。

メモリ領域もヒープ領域以外にスタック領域を使うことが出来るため、高速化としてはかなり有効なはずです(未検証)

言語によってはポインタやオブジェクトを扱えないこともあるため、そのような言語を使う場合や移植性を高めたい場合にも有効です。

配列の構造体ではなく、構造体の配列で持つ

適用範囲:グラフ全般

参考:ダブル配列の豆知識

木を含むグラフ全般を実装するとき

struct tree{
	int node[N+1];
	unsigned left[N+1];
	unsigned right[N+1];
};

と実装するより

struct tree_node{
	int node;
	unsigned left;
	unsigned right;
}
struct tree{
	struct tree_node node[N+1];
};

のように実装した方がキャッシュヒット率が上がって高速になりやすい(らしい)です。

とはいえ、実装の手間が増えるわりには効果も大きくないため、別に前者で実装しても何ら問題はないです。

1-indexedで持つ

適用範囲:グラフ全般,完全二分木

いくつかのメリットがあります。

0番目の要素にデータ数やルートのインデックス,参照カウンタなどの情報を詰め込むことが出来る。
0という値を「値が存在しない」ことを示す特別な値として扱うことができる(ヌルポインタみたいなもの)
木を構造体の配列で持つ実装と相性が良い

二重連鎖木

適用範囲:多分木

テクニックと言えるかは微妙ですが、子の個数が不定の多分木を実装するときは

子の代表
兄弟
を持つのがセオリーです。
子の集合を配列ではなく連結リストで持つイメージです。

struct tree_node{
	int node;
	unsigned child;
	unsigned brother;
};

struct tree{
	struct tree_node node[N+1];
};

実装を見ると分かると思いますが、構造としては二分木と酷似しており、多分木を二分木として表現する方法と捉えることが出来ます。
このような実装を二重連鎖木と言います。

このテクニックはTrie(恐らくB木も)などの特定の子に定数時間でアクセスする必要がある場合には使えません。

子だけでなく親の情報も持つ

適用範囲:平衡木など

主に平衡二分探索木の実装で使うテクニックです。
言語によってはこのテクニックによって文字通り桁違いの速度差が出てきます。

本来、(平衡)二分探索木は親へのアクセスを必要としないデータ構造ですが、回転の操作では先祖の情報を遡る必要が出てきます。

遡るだけなら再帰呼び出しで実現可能ですが、再帰呼び出しには時間がかかります。

AVL木や赤黒木などの代表的な平衡二分探索木²は回転の計算量が定数であるため、対数時間の計算量がかかる検索の部分がネックになります。

再帰呼び出しを使う場合、参照のみだった検索にスタックへの書き込みが加わるため、平衡でない二分探索木より遥かに遅くなります。(ただし、merge/splitをサポートする一般的な平衡二分探索木³は左の子の要素数を持つ必要があるため、検索時に書き込みが発生します。とは言え、書き込みの回数を減らすのは重要です)

親の情報を持つ場合、検索自体にかかる追加の計算量はほぼ0なので、平衡でない二分探索木に匹敵するパフォーマンスを得ることが出来ます。

bloodという名前で活動する場合もあります ↩
乱択な平衡二分探索木やスプレー木がどうなのかは分かりません。 ↩
merge/splitが不要な場合は平衡二分探索木を使うまでもなくskiplistで十分です。まぁskiplistの実装は鬼難しいんですけど ↩