先頭へ戻る

平衡木 | Programming Place Plus 用語集

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

木構造のうち、どの葉も深さが可能なかぎり一定になるように構築されているもののことです。

読み方は「へいこうぎ」です。

木構造の深さとは、根(一番上位の)から、葉(一番下位にある、子のいない節)までの距離(通過する節の数)のことです。葉は複数ありえるので、注目する葉によって深さが異なりますが、そのばらつきを可能なかぎり抑えたものが平衡木と呼ばれます。結果、すべての葉の深さは同じであるか、1つしか違わないかのいずれかになります。

平衡木になっていると、木全体として深さが低く抑えられるため、節を探索する際に辿らなければならない節の個数が平均的に少なくなり、高い探索効率が期待できます。ただし、節の追加や削除のたびに、木全体を再構築して平衡木であることを維持するコストがかかります。

ある節に対する子の数が2個以内のものを二分木と呼ぶなど、木構造を分類する考え方はほかにもあるため、たとえば「二分木でありつつ平衡木である」といったこともあります。


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー