Subject: Re: building trees
From: Matthew Cary (cary@cs.washington.edu)
Date: Tue May 14 2002 - 16:24:33 PDT
There's actually an easier way to see that doing n inserts into an
initially empty, balanced, tree takes n log n time.
Let's just consider inserting the last n/2 items. If the tree at this
point is perfectly balanced, then it's a tree of height log n - 1, and all
of the last n/2 items insered will have to be inserted on the last row.
Hence it takes n/2 * (log n - 1) = 0.5 n log n - 0.5 n = Theta(n log n),
just to insert the last n/2 items, and so doing n inserts from the top of
any tree will take n log n time, whether the tree is just a BST, or AVL,
or even a heap.
The reason for this is something I said at the beginning of the quarter,
that most of the nodes in a tree are at the bottom. Hence when inserting
from the top, most of the nodes inserted are the worst case nodes. The
genius of Floyd's Heapify algorithm is that the nodes at the bottom of the
tree are the cheap ones to deal with, so the overall running time is
asympototically faster.
Note that this is why Heaps make a better priority queue than AVL trees.
What I said last week in class was wrong; the slides on the web are being
changed.
Note also that splay trees can be faster, because inserts occurr at the
top of the tree, so you don't need to go all the way to the bottom to
insert.
This archive was generated by hypermail 2b25 : Tue May 14 2002 - 16:24:42 PDT