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