平衡木 【balanced tree】 バランス木
木構造は単一の根ノードを起点に「親ノードは複数の子ノードを持つことができる」という規則に従ってノードを連結したデータ構造で、根から末端の葉に至るまでに通過する階層の数を「深さ」という。
平衡木はこの階層の深さがどの葉もなるべく均等になるように調整した木構造である。ノードの追加や削除の際に一定のルールで木を再構成し、深さ等しく保たれるように操作する。根からどの葉までたどってもほぼ同じ数のノードを経由するため、探索などの処理をする際に平均の計算時間を短縮することができる。
二分木を平衡にした構造を「平衡二分木」（balanced binary tree）という。そのうち、どのノードの値も左の子ノードより小さく、右の子ノードより大きくなるように値を配置した「平衡二分探索木」が二分探索に適したデータ構造としてよく用いられる。多分木の平衡木である「B木」（Bツリー）やその派生構造も実用上重要である。
(2022.5.31更新)
共有ボタンをタップ