algorithm - 2-3-4ツリーに挿入するときにノードが分割されるのはなぜですか？

Question

以下に示す2-3-4ツリー（JavaのData Structures＆Algorithm、第2版から）では、挿入すると、正しい子（子、分割を行わずに）の直後にスポットしますか？9983/92/10499C97

Answer 1

99をCに挿入すると、すべての不変条件が維持されるという点で問題ありませんが、挿入が途中で常に4ノードを拡張する場合、アルゴリズムは一般的に単純です。そうすれば、必要な持ち上げや回転の余地が常にあります。Cがすでに4ノードである場合を比較すると役立つ場合があります。

Answer 2

ツリーのバランスを保ち、パフォーマンスを保証します。挿入は再帰的であり、4ノード（3つの値と4つの子を持つノード）にヒットします。これにより、分割が実行されます。