AVL樹輪轉效率

Question

AVL樹輪轉的大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）次旋轉。無論事實如何，複雜性就像你說的對數一樣。