}}
== Построение дерева за линейное время ==
Пусть дан массив <tex>A[1..N]</tex>. Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение <tex>A[i]</tex>, начнем обход из вершины <tex>A[i-1]</tex> к корню, пока не найдем вершину <tex>x</tex>, для которой <tex>x < A[i]</tex>. Тогда правого сына <tex>x</tex> назначим левым сыном <tex>A[i]</tex>, а <tex>A[i]</tex> {{---}} правым сыном <tex>x</tex>. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более <tex>n</tex> раз и итоговая асимптотика алгоритма <tex>O(n)</tex>.
== Сложность ==
Выше описан алгоритм построения дерева за <tex>O(n)</tex>.
