[prev] 94 [next]

AVL Trees (cont)

Analysis of AVL trees:
  • trees are height-balanced; subtree depths differ by +/-1
  • average/worst-case search performance of O(log n)
  • require extra data to be stored in each node ("height")
  • may not be weight-balanced; subtree sizes may differ

[Diagram:Pic/height-weight.png]