読み方：じゅんじょぎ

順序木【ordered tree】順序付き木

概要

順序木とは、データ構造の一つである木構造のうち、各ノードの間に順序関係が定義されたもの。ノードに格納する値の大小や、同じ親を持つ子ノード間の位置関係に規則を設けることで、データの探索や挿入、削除を効率的に行える。

木構造（ツリー構造）とは、データ要素を階層的な親子関係で表現したデータ構造であり、最上位に一つの根ノードを置き、そこから下位のノードへ枝分かれしていく形をとる。一つの親ノードは複数の子ノードを持てるが、子ノードが持てる親は必ず一つである。

順序木では、「親ノードと子ノードの間」または「同じ親を持つ複数の子ノード間」に大小や前後といった順序が設けられる。子ノードの並び順を区別しない「無順序木」とは異なり、同じ親子関係を持つ木であっても子ノードの順序が異なれば別の構造として扱われる。コンピュータ上で扱うデータのほとんどは何らかの順序性を持つため、実務やプログラミングで利用される木構造の多くも順序木として管理される。

順序木のな派生形として「二分探索木」（binary search tree）がある。各ノードが持てる子を最大二つに限定した「二分木」（binary tree））のうち、左の子ノードには親より小さい値、右の子ノードには親より大きい値を配置する規則を設けたものである。この構造により、目的の値を根ノードから順にたどって効率的に探索する「二分探索」（binary search）が可能となり、データ検索システムなどで多用されている。

順序木のうち、親ノードの値が常に子ノードの値以上（最大ヒープ）、または以下（最小ヒープ）となるよう構築したものを「半順序木」（heap：ヒープ）という。根ノードが常に全体の最大値または最小値となる特徴があり、優先度付きキューの実装や、高速な整列アルゴリズムである「ヒープソート」（heap sort）に応用される。