ご存知のように、挿入と削除にはすべて O(log n) が必要です。AVL ツリーには O(log n) が必要です。これは、挿入に O(log n)、バランスをとるためにローテーションに O(log n) が必要なためです。
RB ツリーには O(log n) が必要です。これは、挿入に O(log n) が必要なためです。INTRODUCTION TO ALGORITHMS THIRD EDITION では、RB-INSERT-FIXUP は、ケース 1(カラー フリップ) に対して O(log n) を必要とし、多くてもローテーションに2回。つまり、AVL には 2O(log n) が必要なようですが、RB ツリーには 2O(log n)+C が必要です。
なぜ RB ツリーは AVL よりも挿入が速いと思いますか? 色反転よりも回転に時間がかかるという理由だけで？回転とカラー フリップの両方に O(1) が必要ですが、カラー フリップよりも回転に時間がかかるのはなぜですか? ありがとう！：）
私があなたの質問を正しく理解していれば、はい、RB-Tree と AVL-Tree の両方がO(logn)時間内に検索、挿入、削除を提供するのは事実です。
AVL ツリーは、RB ツリーより厳密にバランスが取れています。これを達成するには、多くの回転が必要であり、時間がかかります。RB ツリーは、バランスをとるためのルールが弱いため、わずかにバランスが取れていないため、挿入と削除に必要な操作が少なくなります。結果として、AVL ツリーでのルックアップは RB ツリーより高速ですが、挿入と削除は RB ツリーの方が高速です。
編集
このブログ投稿をお読みください。ポイントは、RB ツリーは、挿入後に AVL ツリーよりも速くバランスを取ることです。はい、回転にはO(1)AVL ツリーで時間がかかります。多くても 2 回の回転を行う必要がありますが、回転のポイントを見つける必要があり、回転の時間は になりO(logn)ます。一方、RB ツリーでは、挿入後のリバランスは償却された定数時間で実行されます。つまり、O(1)カラー フリップの償却時間であり、 ではありませんO(logn)。