はじめに

どうも。aqualengthです。¹

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

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

目次

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

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

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

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

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];
};

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

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

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

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

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

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

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

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

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

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

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

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