Для организации поиска в основной памяти особое значение имеют упорядоченные двоичные (бинарные) деревья (как, например, на рисунке 4.3). В каждом таком дереве естественно определяются левое и правое поддеревья. Двоичное дерево называется идеально сбалансированным, если число вершин в его левом и правом поддеревьях отличается не более, чем на 1 (легко видеть, что при соблюдении этого условия длины пути до любой листовой вершины дерева отличаются не больше, чем на 1). Примеры идеально сбалансированных деревьев показаны на рисунке 4.5.
Двоичные деревья обычно представляются как динамические структуры (см. раздел 1.7) с базовым типом записи T, в число полей которого входят два указателя на переменные типа T.
При использовании в целях поиска элементов данных по значению уникального ключа применяются двоичные деревья поиска, обладающие тем свойством, что для любой вершины дерева значение ее ключа больше значения ключа любой вершины ее левого поддерева и больше значения ключа любой вершины правого поддерева (рисунок 4.6). Для поиска заданного ключа в дереве поиска достаточно пройти по одному пути от корня до (возможно, листовой) вершины (рисунок 4.7). Высота идеально сбалансированного двоичного дерева с n вершинами составляет не более, чем log n (логарифм двоичный), поэтому при применении таких деревьев в качестве деревьев поиска (рисунок 4.8) потребуется не более log n сравнений.
Применение деревьев как объектов с динамической структурой особенно полезно, если допускать выполнение не только операции поиска по значению ключа, но и операций включения новых и исключения существующих ключей. Если не принимать во внимание потенциальное желание поддерживать идеальную балансировку дерева, то процедуры включения и исключения ключей очень просты. Для включения в дерево вершины с новым ключом x по общим правилам поиска ищется листовая вершина, в которой находился бы этот ключ, если бы он входил в дерево.
Возможны две ситуации: (a) такая вершина не существует; (b) вершина существует и уже занята, т.е. содержит некоторый ключ y. В первой ситуации создается недостающая вершина, и в нее заносится значение ключа x. Во второй ситуации после включения ключа x эта вершина в любом случае становится внутренней, причем если x > y, то ключ x заносится в новую листовую вершину - правого сына y, а если x < y - то в левую. Четыре потенциально возможных случая проиллюстрированы на рисунке 4.9.