このテキストの歴史は次のとおりです。 子にはbtreeをプログラミングするタスクが与えられました。 私は時々彼を助けます。 これは些細なことだと決めました。 しかし、問題を迅速に解決する試みは失敗しました。 合理的な説明やコードの検索も無駄でした。 私の息子はずっと前にテストに合格しましたが、私の妄想的な性質のために問題を解決できました。 たぶん誰かが役に立つでしょう。
平衡型btree検索ツリー（使用済みツリー）
定義はしていません。 それを見つけることは難しくありません。 検索、キーの挿入は簡単です。
btreeからキーを削除する
ノードは、t-1キーを含む場合、空と呼ばれます。 キーを削除することはできません。 定義上、ルートは決して空ではありません。 また、すべてのノードが空の場合、サブツリーは空と呼ばれます。 空のツリーは一意に配置されます。 したがって、完全なノードは、キーの数が2t-1のノードと呼ばれます。 空のツリーのキーの数は明らかです
（t-1）*（1 + t + t ^ 2 + ... + t ^ h）= t ^（h + 1）-1、ここでhは木の高さ（ルートの高さ= 0）です。
btreeでのキーの挿入が明確な場合、削除はあいまいです。
見つかったキーが配置されているノードが葉の多い場合、ノードが空でない場合、キーはシフトされ、削除されたキーが置き換えられます。
ノードが空の場合、空にならないようにツリーを変換する必要があります。
左の葉の特定のキーのリーフノードを呼び出します。このリーフノードには、まずこのキーの左の子孫に移動し、次に最後の子孫のリーフノードに移動します。 同様に、右側の左側のシートが決定されます。 最初に正しいストリームへ、次にゼロの子孫へ。
ノードが葉のない場合、このキーには左右の子孫と親（ルートでない場合）があり、ノードの位置はiです。 btreeの定義により、左の子のすべてのキーは小さく、右の子のすべてのキーはこのキーより大きくなります。 btreeの定義に違反することなく、削除されたキーをどのキーで置き換えることができますか？
図では、青でマークされたキーはこれより小さく、黄色はこれより大きくなっています。 削除するキーは、最小の最大キーまたは最大の最小キーにのみ置き換えることができます。 図では、それぞれ赤と青で囲まれています。 最初は左側の右側のシートの最後のキーであり、2番目は右側の左側のシートの最初のキーです。 それらの1つが空でない場合は、削除するキーをそれらの1つに変更し、元のシートから置換キーを削除します。空でない場合は、リーフノードを空にしないタスクに戻ります。
このリーフノードを空にしないという問題を解決するために、マージと優勢の2つのbtree変換を検討してください。 このノードが空ではなく、このキーの両方の子孫が空の場合、マージ変換を実行できます。 このキーはそのノードから削除され、1つのノードがそのキーとその子孫から作成されます。 ルートが空になることはないため、すべてのノードが空で、ルートに1つのキーがある場合、マージが行われ、古いルートが削除されます。
2番目のBtree変換は利点です。 このキーの左側の右側のシートが空でない場合、右側の左側のシートがいっぱいでない場合は、右端を作成できます。 右側の左側のシートがいっぱいの場合は、分割を実行します。 このキーを右側の左側のシートのゼロ位置に挿入し、ユニット内のキーの数を増やします。 右側のシートの最後のキーを左側に置き、このキーを置き換えて削除します。
同様に、右側にも利点があります。 エッジの高さは1からツリーの高さまでです。
さて、実際には、このシートを空にしない方法のアルゴリズム。 このプロセスはツリー圧縮と呼ばれます。 右への圧着を検討してください。
左の兄弟は、現在の兄弟の左側にある同じレベルのノードです。 兄弟には共通の祖先と共通の祖先の鍵があります。 共通の祖先のキーを介して、キーが再重み付けされます。
左兄弟が空でない場合、キーを上回る。 問題は解決しました。 左の兄弟が空で、親が空でない場合、マージします。 問題は解決しました。 親と空の兄弟の両方が空の場合、再帰的に親から、次に左（任意の）兄弟からスピンを要求します。
同様に、左への圧着が行われます。 削除のあいまいさは、最初に右または左のどちらにクリンプできるかです。 また、最初にアドバンテージをリクエストしてから、マージすることもできます。
不本意を証明するために、しかし直感はそれが常に圧着されていることを示しています。
ツリーを再構築するときに、削除のために見つかったキーは、ツリーの他のノードでの合併の結果として表示される場合があることに注意してください。 しかし、彼は交換キーとの接触を失うことはできません。
結論の1つとして、キーの削除を高速化するには、リーフノードを空にしないことが望ましいと言えます。 つまり 重要な事柄からの彼の暇なときに、マージによってツリーの圧縮を行います。 圧倒する意味はありません。
最適化を提供することもできます。
Btree-ツリーは短くても幅が広い。 枝に沿って歩くことは頭上になります。 最適化のために、パラメータブランチの重み（その中のキーの数）を提供できます。 空の木の重量は1つの高さに対して一定であるため、枝に沿って歩いているときに重量を確認できます。 空のツリーの重量に等しい場合、そこで何もすることはありません。そうでない場合は、停止し、そこから1つのキーを確実に押します。 体重管理は簡単です。 キーが挿入されると、挿入パスに沿ったすべてのノードの重みが増加し、現在のノードとすべての親が削除されると、ルートまで減少します。
独自の用語。
私はこれに別れを告げ、私は疲れていないことを願っています。 C ++のリストが添付されています（最適化なしでコーミングされていません）。
PS証明が熟しました。
空でないシートが少なくとも1つある場合は、いつでも目的のシートに転送できます。 そうでなくて、シートの上に空でないものが少なくとも1つある場合は、マージを行います。 さらに誘導によって。 ルートが空になることはありません。
最適化オプションも登場しました。 キーを削除するノードが空ではなく、左右のすべての子孫が空の場合、キーは単に削除され、子孫が一緒に接着されます。 つまり ノードが空でない場合は、左右の最も近い子孫よりも遠くに行く必要はありません。
C ++ソース 。