Каждый элемент O (n), и есть n элементов. Даже если O (n) для каждого элемента является «увеличивающимся по ходу» n, вы все равно получаете 0 + 1 + 2 + 3 ... (n-1), то есть n (n-1) / 2 = O ( п ^ 2).
Другими словами, предположим, что мы добавляем 10, 20, 30, 40:
Шаг 1: пустое дерево, вставить 10:
10
Шаг 2: сравните 20 с 10; больше, поэтому дерево становится:
10
\
20
Шаг 3: сравните 30 с 10; больше, так что двигайтесь вниз к узлу с 20.
сравнить 30 с 20; больше, поэтому дерево становится:
10
\
20
\
30
Шаг 4: сравнить 40 с 10; больше, так что двигайтесь вниз к узлу с 20.
сравнить 40 с 20; больше, так что двигайтесь вниз к узлу с 30.
сравнить 40 с 30; больше, поэтому дерево становится:
10
\
20
\
30
\
40
Обратите внимание, как мы получаем еще одно сравнение каждый раз - поэтому первый элемент берет 0 сравнений, второй - 1, третий - 2 и т. Д., Суммируя n (n-1).
Конечно, это только в том случае, если вы вставляете в порядке сортировки (от малого к большому или от большого к маленькому). Вставка в порядок, в котором происходит уравновешивание дерева, будет значительно дешевле.