平衡木 | Programming Place Plus　用語集

名称

• 平衡木　【balanced tree】
• バランス木　【balanced tree】
• バランスツリー　【balanced tree】

解説

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

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

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

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

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