Almost-perfectly balanced binary search trees

Revision en3, by ilyaraz, 2015-09-30 18:44:39

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? Is time per insert possible?

For instance, AVL trees achieve height around and red-black trees — .

What do you think?

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


  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)