木構造

https://scrapbox.io/files/639e837261bf84001d00d421.png

木構造とは

グラフ理論における閉路のない連結なグラフのこと

よく出る用語

次数(degree)

ノード

各木の頂点のこと

根(root)

木の特別な頂点。子しか持たないノード。

葉(leaf)

根以外の次数1の点のこと

深さ(depth)

根からの道の長さのこと

高さ(height)

最大の道の長さのこと

親(parent)

ある頂点に対して根に向かう道で一番近い頂点のこと

子(child)

頂点vを親とする頂点wを頂点vの子と呼ぶ

部分木(subtree)

ある頂点に対してvの子孫からなる部分グラフを頂点vにおける部分木と呼ぶ

祖先(ancestor)

ある頂点の親たちのこと

子孫(descendant)

ある頂点の子供たちのこと

データ

葉の値のこと

キー

葉ではないノードの中に含まれる値のこと

種類