Insertion at Root (cont)
Analysis of insertion-at-root:
- same complexity as for insertion-at-leaf O(depth)
- although more actual work for each insertion
- tendency to be balanced, but no balance guarantee
- benefit comes in searching
- for some apps, search favours recently-added items
- insertion-at-root ensures these are close to root
- could even consider "move to root when found"
- effectively provides "self-tuning" search tree
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}