big-o - AVLツリーの回転効率

Question

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

たとえば、挿入する場合：-O（logN）を使用して位置を検索します-O（1）を挿入します-？バランス調整用（再バランス調整が必要な場合）

O（logN）だと思っていたのですが、O（1）だと主張するサイトを見つけました-読み間違えない限り-http: //users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml

（これは2-3ツリーでも同じでしょうか？）

事前に助けてくれてありがとう

Answer 1

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