Статья 2303

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