Статья 2302

Изучение подобных вопросов называется анализом сложности.
Методы анализа сложности можно продемонстрировать на примере построения бинарного дерева - структуры данных, часто применяемой в тех случаях, когда важен быстрый поиск информации. Такое дерево обладает двумя характерными свойствами, каждый узел имеет, самое большее, два подузла, а ключи, которые идентифицируют эти узлы, устроены так, чтобы у любого узла меньший ключ соответствовал левой ветви. Поиск по заданному ключу может быть очень эффективным, сравнение в каждом узле показывает, какую ветвь выбрать - левую или правую, поэтому после прохождения каждого узла число остающихся вариантов сокращается вдвое.
Эффективность максимальна, когда дерево сбалансировано, когда каждый узел имеет ровно два подузла. Средняя длина пути - ожидаемое число ключевых сравнений - равняется в этом случае логарифму числа узлов по основанию 2. В наихудшем случае, когда дерево вырождается в простой список, в котором каждый узел связан лишь с одним подузлом, средняя длина пути в два раза меньше числа узлов. Отсюда следует как будто, что надо заботиться о том, чтобы дерево оставалось сбалансированным в процессе своего роста. Однако балансировка сама по себе требует значительной работы. Поэтому возникает вопрос, окупится ли такая дополнительная работа ускорением поиска. Как это ни удивительно, во многих случаях ответ отрицательный.
Предположим, значений ключей прочитано в случайном порядке и включено в дерево, изначально пустое. Ключи упорядочиваются слева направо по мере их размещения, однако не делается попыток сбалансировать растущее дерево. Можно построить единую процедуру как для заведения нового ключа, так и для поиска уже имеющегося. Такая процедура находит на дереве место, к которому подходит данный ключ, и вставляет его, если его там нет.