リバランスアルゴリズム

リバランスアルゴリズムは、次の方法で実行できます-

Day-Stout-Warrenアルゴリズム

Day-Stout-Warrenアルゴリズムを使用して、実際にリバランス方法を実装できます。ノード数は線形です。

以下は、擬似コードでの基本的なDSWアルゴリズムのプレゼンテーションです。

• 「疑似ルート」と呼ばれるノードが割り当てられ、ツリーの実際のルートが疑似ルートの正しい子になります。
• 引数として疑似ルートを使用してツリーをソートされたリンクリストに変換するために、tree-to-vine関数を呼び出します。
• vine-to-tree関数を呼び出して、ソートされたリンクリストをツリーに再度変換します。疑似ルートとツリーのサイズ（要素の数）を引数として使用します。
• 疑似ルートの右の子に等しいツリーの実際のルートを構築する必要があります。
• 最後に、疑似ルートを破棄する必要があります。

「コピーオンライト」ツリー

線形化可能性の欠如に耐えられる場合（つまり、値を書き込みますが、値が見つからなかった直後に検索すると、最終的には検出されますが、100ミリ秒から10秒後に）、「コピーオンライト」ツリーを適用できます。すべての書き込みは（リバランスを使用して）1つのスレッドによって実行され、同時実行制御なしでスレッドを読み取ることで実装できる読み取り専用コピーにツリーを定期的にコピーします。アトミックに公開する必要があります。

同時スキップリスト

もう1つのオプションは、同時スキップリストを実装することです。これは、対数平均のケース検索/削除/挿入時間を提供し、より簡単に並列化できます。 Javaを実装する場合は、標準のロックフリー実装があります。同時スキップリストとバランスの取れた検索ツリーの詳細については、こちらをご覧ください。特に、同時リバランス用に最適化された二分探索木として示される有彩色ツリーについての言及を得ることができます。