Almost-perfectly balanced binary search trees

Revision en1, by ilyaraz, 2015-09-30 09:40:18

Hi all,

I'm about to teach AVL trees for a section of 6.006, and while thinking it through, I came up with the following question, which, I strongly suspect, should be well-understood.

Say one wants to maintain a binary search tree with height , where n is the total number of nodes, under insertions. How quickly can one insert? Can one do it in time ?

For instance, AVL trees give you height around .

What do you think?

Tags avl trees, binary search tree, data structures, algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ilyaraz 2015-09-30 18:44:39 9 Tiny change: 'AVL trees give you height ar' -> 'AVL trees achieve height ar'
en2 English ilyaraz 2015-09-30 09:50:13 79
en1 English ilyaraz 2015-09-30 09:40:18 666 Initial revision (published)