AVLツリーのローテーション効率

Question

AVLツリーローテーションのBig O効率は、具体的には何ですか？

例えば、 - O（logN）を挿入して - O（1）を検索すると、 - ？が挿入されます。 （http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml

を - （それは再バランスにする必要がある場合）

のバランスをとるために、私はそれがO（logN個）だろうと思ったが、私はそれはO（1）の主張サイトを見つけました - 私はそれを読み違えていない限り、これはまた、2-3ツリーの同じでしょうか？）の助けを

事前に感謝

Answer 1

あなたが言うように複雑さが（n個のログ）Oです。この記事では、それぞれのリバランシング操作の一定時間、つまりO（log n）回の回転を行う必要がある間、それぞれの回転を意味すると考えています。真実が何であれ、対数をとると複雑さが増します。