title: AVL Tree Rotation Efficiency
body: <p>What is the Big O efficiency of the AVL tree rotation specifically?</p>
  
  <p>For example when inserting:
  - O(logN) to search for the position
  - O(1) to insert
  - ? for balancing (if it needs to be re-balanced)</p>
  
  <p>I thought it would be O(logN) but I found a site which claims it's O(1) - unless I have misread it - <a href="http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml" rel="nofollow">http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml</a></p>
  
  <p>(Would this also be the same for a 2-3 tree?)</p>
  
  <p>Thanks for the help in advance</p>