Almost-perfectly balanced binary search trees

Правка en3, от 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 $\text{[math]}$ , where n is the total number of nodes, under insertions. How quickly can one insert? Is time $\text{[math]}$ per insert possible?

For instance, AVL trees achieve height around $\text{[math]}$ and red-black trees — $\text{[math]}$ .

What do you think?

avl trees, binary search tree, data structures, algorithms

История

Правки

Rev.	Кто	Когда	Δ	Комментарий
en3	ilyaraz	2015-09-30 18:44:39	9	Tiny change: 'AVL trees give you height ar' -> 'AVL trees achieve height ar'
en2	ilyaraz	2015-09-30 09:50:13	79
en1	ilyaraz	2015-09-30 09:40:18	666	Initial revision (published)