Exercise #9
(cont)
Analysis of AVL trees:
trees are
height
-balanced; subtree depths differ by +/-1
average/worst-case performance of
O(logN)
require
extra data to be stored in each node
may not be
weight
-balanced; subtree sizes may differ
![[Diagram:Pics/trees/height-weight.png]](Pics/trees/height-weight.png)
![[prev]](icon/prev.gif){kind=icon}
![[index]](icon/up.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}