バランスドツリー(平衡木)
バランスドツリーはルートノードからリーフノードの距離(高さ)をできるだけ等しくしたツリー構造です。
「高さを等しくする」とはツリーの高さを低くするということです。なぜ低くするのかというと、探索にかかる計算量を少なくするためです。ツリーの探索はルートからリーフに向かって各ノードで何らかの判断や処理を行います。高さが高くなればノードの数も多くなるので処理も増えることは直感的に理解できますよね。ですから低ければ低いほど処理が減って探索が速くなるのです。
バイナリーサーチツリーではノードの値の大小によって子ノードの位置を特定し、探索を効率的に行うようになっていますが、時には右ばかり(または左ばかり)に伸びるツリーが出来ることもあります。そうなった場合ノードをたどる回数も増えるので効率が悪くなるというわけです。こういった事態を解消するために考え出されたのがバランスドツリーなのです。
プログラムでバランスドツリーを実現するには、ノードの挿入/削除操作のたびにツリーを再構築して高さをバランスよく保つようにします。
