Для каждой из операций (проверки, добавления и исключения)
количество действий не превосходит 
. Для
<< ровно подстриженного>> дерева (когда все листья на одной
высоте) высота по порядку величины равна логарифму числа вершин.
Однако для кривобокого дерева все может быть гораздо хуже: в
наихудшем случае все вершины образуют цепь и высота равна числу
вершин. Так случится, если элементы множества добавляются в
возрастающем или убывающем порядке. Можно доказать, однако, что
при добавлении элементов << в случайном порядке>> средняя высота
дерева будет не больше 
. Если этой
оценки << в среднем>> мало, необходимы дополнительные действия по
поддержанию << сбалансированности>> дерева. Об этом смотри в следующем
пункте.
pvv
1/8/1999