2

私は b ツリーについて学ぼうとしていますが、見つけることができるすべてのソースでは、b ツリーのプロパティを保持しながらツリーから要素を削除する方法についての議論が省略されているようです。

誰かがアルゴリズムを説明したり、それがどのように行われたかを説明するリソースを教えてくれますか?

4

4 に答える 4

3

ウィキペディアのページに説明があります。 B ツリー - 削除

于 2011-03-03T20:16:29.110 に答える
2

まだ入手していない場合は、Carmen & al Introduction to Algorithms 3rd Editionを強くお勧めします。

操作は当然 B ツリーのプロパティに由来するため、説明しません。

ノード内の要素数には下限があるため、要素を削除するとこの不変条件に違反する場合は、要素を復元する必要があります。これには通常、隣接する要素とのマージ (またはその要素の一部の盗用) が含まれます。

隣人とマージする場合は、同じアルゴリズムをトリガーする親ノードの要素を削除する必要があります。そして、トップに到達するまで再帰的に適用します。

B-Tree にはリバランス機能がありません (少なくとも私が見たものはそうではありません) ので、赤黒ツリーや AVL ツリーを維持することははるかに簡単です。

于 2011-03-03T20:15:33.580 に答える
0

どの b-tree について話しているのですか? リンクされた葉があるかどうか？また、アイテムを削除するにはさまざまな方法があります (上から下、下から上など)。B-trees、Shadowing、およびClones（ファイルシステム固有の関連するものがたくさんありますが）は、このペーパーが役立つかもしれません。

于 2011-03-03T20:22:32.523 に答える
0

CLRS (第 2 版) からの削除例は、http://ysangkok.github.io/js-clrs-btree/btree.html から入手できます。

「Init book」を押してから、削除ボタンを順番に押してください。それはすべてのケースをカバーします。各ボタンを押す前に、新しいツリーの状態を予測してみてください。また、すべてのケースがどのように一意であるかを認識してください。

于 2013-12-29T23:50:39.677 に答える