Изменения
Нет описания правки
Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (0<<tex>e</tex><1) Э.П.поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(log(logn))</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(nlog(logn))</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.
==ОпределенияНеобходимая информация==
{{Определение
|id=def1def2.
|definition=
Алгоритм сортирующий <tex>n</tex> целых чисел из множества {0, 1, ..., <tex>m</tex> - 1} называется консервативным, если длина контейнера (число битв контейнере), используемое для хранения данных целых чисел является <tex>O(log(m + n))</tex>. Если используется большее число битдлина больше, то алгоритм не консервативный.
}}
