Изменения

Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь по склону вверх (ведь после этого вершина будет лежать в чьем-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>.

Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей <tex>(1, 1), \ldots, (n, n)</tex>, будет равна <tex>n</tex>. Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.