[prev] 52 [next]

Insertion at Root (cont)

Analysis of insertion-at-root:
  • same complexity as for insertion-at-leaf:  O(height)
  • tendency to be balanced, but no balance guarantee
  • benefit comes in searching
    • for some applications, 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

    ⇒ more on this later (real balanced trees)