Оценка количества действий

Для каждой из операций (проверки, добавления и исключения) количество действий не превосходит $C\cdot(\hbox{\rm
высота дерева})$. Для << ровно подстриженного>> дерева (когда все листья на одной высоте) высота по порядку величины равна логарифму числа вершин. Однако для кривобокого дерева все может быть гораздо хуже: в наихудшем случае все вершины образуют цепь и высота равна числу вершин. Так случится, если элементы множества добавляются в возрастающем или убывающем порядке. Можно доказать, однако, что при добавлении элементов << в случайном порядке>> средняя высота дерева будет не больше $C\log(\hbox{\rm число вершин})$. Если этой оценки << в среднем>> мало, необходимы дополнительные действия по поддержанию << сбалансированности>> дерева. Об этом смотри в следующем пункте.



pvv
1/8/1999