time-complexity - 2 ～ 3 ツリーでの挿入と削除の時間の複雑さ

Question

2-3 ツリーでの挿入操作と削除操作が常に O(logn) の複雑さを持つのはなぜですか? 数学的な証明はありますか?

Answer 1

• レベルでキーを挿入する場合、最悪の場合、 + 1ノードを分割する必要があります (各レベルとルートに 1 つずつ)。
• 最大レベル数のキーを2-3 tree含むは、各内部ノードが 1 つのキーと 2 つの子を持つバイナリ ツリーの形式をとります。
• そのようなツリー = (2^(+1)) − 1では、 は最低レベルの番号です。
• これ + 1 = log( + 1)は、分割が最悪のケースであることがわかることを意味し log ます。
• 2-3 treeそのため、最悪の場合、挿入に時間がかかり ます。
• 同様に、検索と削除に 時間がかかることも証明できます。