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

概要

順序木（ordered tree）とは、データ構造の一つである木構造(ツリー)のうち、各ノードに数値などが割り当てられ、その大小によって順序が存在するもの。

木構造はグラフ構造のうち要素に親子関係があり、親が複数の子を持つことができるようなものを意味し、根ノード（root node）を頂点として階層的に枝分かれしていく構造となる。

順序木はこのうち、ノードに整数などの数値や何らかの順序性のあるデータが格納され、親ノードと子ノード、あるいは親から見て複数の子ノードの間に順序を付けて区別するものを指す。コンピュータ上で扱うデータのほとんどは何らかの順序性を持つため、ほとんど順序木となる。

順序木のうち、親子関係にあるノードの値が常に「親≧子」あるいは「親≦子」となるように構築したものを「半順序木」（partially ordered tree）あるいは「ヒープ」（heap）という。根ノードが最大または最小となる特徴があり、高速な整列アルゴリズムである「ヒープソート」などに応用される。

(2024.7.31更新)

他の辞典による解説 （外部サイト）

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる