Понятно, что в случае полного двоичного дерева мы получим сложность T(log(n)) (на каждом шаге размер дерева поиска будет сокращаться вдвое). Рассмотрим минимальное сбалансированное дерево (худший случай). Таким будет дерево, у которого для каждой вершины высота левого и правого поддеревьев различаются на 1. Для такого дерева можно записать следующую рекуррентную формулу для числа вершин (h – высота дерева):
Покажем, что h<log2(Nh). Для этого необходимо и достаточно показать, что 2h>Nh. Докажем последнее методом математической индукции.а) h=0: 20>N0=0; б) h=1: 21>N1=1; в) h>1: Пусть 2h-2>Nh-2 и 2h-1>Nh-1. Тогда 2h-2+2h-1>Nh-2+ Nh-1. И далее получаем 2h>1+2h-2+2h-1>1+Nh-2+ Nh-1=Nh, что и требовалось доказать.
Таким образом алгоритмы поиска/добавления/удаления элементов в сбалансированном дереве имеют сложность T(log(n)). Г.М. Адельсон -Вельский и Е.М. Ландис доказали теорему, согласно которой высота сбалансированного дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%.
