「動く」辞書でフレーズを検索するスライディング ウィンドウ圧縮アルゴリズム (LZ77) を作成しています。
これまでのところ、各ノードが配列に格納される BST を作成しました。配列内のインデックスは、ウィンドウ自体の開始位置の値でもあります。
現在、BST を AVL ツリーに変換することを検討しています。私が見たサンプル実装には少し混乱しています。バランス係数のみを保存しているように見えるものもあれば、各木の高さを保存しているものもあります。
各ノードの高さおよび/またはバランス係数を保存することのパフォーマンス上の利点/欠点はありますか? これが非常に単純な質問である場合は申し訳ありませんが、高さのバランスを実装するために BST を再構築する方法をまだ視覚化していません。
ありがとう。
バランスは単に2つの高さの差であるため、整数の減算の実装が非常に遅い場合を除いて、パフォーマンスに大きな違いはありません。;）高さを格納するには、両方を単一のintに圧縮せずに、単にintとして格納する場合、より多くのメモリが必要になる場合があります。これは、バランスによって最大高さの実際的な制限が保証されるため、安全に実行できます。しかし、時期尚早の最適化、ご存知のとおり...高さがあると、利用可能なバランスしかない場合に追加のサブツリートラバーサルで計算する必要があるより多くの情報が利用可能になりますが、それは要件によって異なります。
ベン・ファフのBSTの優れた紹介について深く研究することをお勧めします：http：//www.stanford.edu/~blp/avl/libavl.html/