Almost-perfectly balanced binary search trees

Правка en2, от ilyaraz, 2015-09-30 09:50:13

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 give you height around and red-black trees — .

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)