FEアルゴリズムとプログラミング · データ構造

先行順

Preorder

せんこうじゅん

木をたどる順序の一つで、節→左部分木→右部分木の順に処理する方法。前順・行きがけ順ともいう。数式の木に適用するとポーランド記法（前置記法）が得られる。

共有:

他の資格での定義

木構造のすべての節をたどる方法（走査）の一つで、節、左部分木、右部分木の順に訪問する。根を最初に訪問するため、木の構造の複製などに使われる。

Past Exams

過去問で 3 回出題（応用情報技術者試験 3）

出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。「選択肢」は、問題文ではなく選択肢に出たものです。用語名で照合しているため、関係の薄い問題が含まれることがあります。

各ノードが最大2つの子ノードを持つ木構造。左の子と右の子に分かれる。2分探索木、ヒープ、式木など多くの応用がある。探索や整列の効率的な実装に使われる。

左の子ノードの値が親より小さく、右の子ノードの値が親より大きいという条件を満たす2分木。探索・挿入・削除の平均計算量がO(log n)で効率的。バランスが崩れるとO(n)に悪化する。

親ノードの値が子ノードの値以上（最大ヒープ）または以下（最小ヒープ）という条件を満たす完全2分木。最大値または最小値の取得がO(1)で可能。優先度付きキューやヒープソートの実装に使用される。

1つのノードが複数のキーと子ノードを持てるバランス木。全ての葉ノードが同じ深さにあり、データベースのインデックスやファイルシステムで使用される。ディスクアクセスを最小化するために設計された。

任意のノードにおいて左右の部分木の高さの差が1以下であることを保証する自己平衡2分探索木。挿入・削除時に回転操作でバランスを保つため、最悪でもO(log n)の探索性能を維持する。

根から下の階層まで隙間なく節が詰まり、最下層だけ左詰めになっている2分木。高さがlog nに抑えられるので処理が効率的で、配列だけで親子関係を表現できる。ヒープはこの形を利用している。