Weight-balanced tree とは

コンピュータサイエンスでは、WBT(Weight-Balanced Binary Tree)は、ダイナミックセット、辞書(マップ)、シーケンスを実装するために使用できるタイプの自己バランス型バイナリ検索ツリーです。これらの木は、NievergeltとReingoldによって1970年代に有界なバランスの木、すなわちBB [α]の木として導入されました。彼らのより一般的な名前はクヌスのためです。
他の自己分散型ツリーと同様に、WBTは、ノードにバランスに関する簿記情報を格納し、挿入操作または削除操作によって妨げられたときにバランスを回復するために回転を実行します。具体的には、各ノードは、そのノードをルートとするサブツリーのサイズを格納し、左右のサブツリーのサイズは、互いにある程度の範囲内に保たれる。 AVLツリー(サブツリーの高さを格納する)と赤黒のツリー(架空の「カラー」ビットを格納する)のバランス情報とは異なり、WBTの簿記情報はアプリケーションにとって実際に有用なプロパティです。ツリーはそのルートのサイズと等しく、サイズ情報は、順序統計木の操作を実装するために必要な情報、つまり、セットのn番目に大きな要素を取得するか、ソートされた要素のインデックスを決定するために必要な情報です注文。
重量バランスのとれたツリーは、関数型プログラミングコミュニティで一般的であり、MIT Scheme、SLIB、およびHaskellの実装でセットとマップを実装するために使用されます。