Поиск по дереву

Ранее мы рассматривали построение бинарного дерева, в котором все левосторонние потомки некоторого узла с ключом key имели ключи, которые < key, а все правосторонние потомки имели ключи >= key[3].

Прохождение такого бинарного дерева в симметричном порядке дает файл, упорядоченный по возрастанию значения ключа. Такое дерево может быть использовано для бинарного поиска. Алгоритм поиска ключа keyв бинарном дереве представляется следующим образом. Предполагаем, что каждый узел дерева содержит четыре поля: поле k, в котором хранится значение ключа данной записи; поле r, в котором хранится сама запись; поля left и right, которые являются указателями на поддеревья:

class item

{

public:

item *left; item *right ;

int k; char r;

};

void main()

{

item * p; // создается объект р

item * search=NULL;

…

while( p!=NULL)

{

if (p->k==key) search=p;

if( p->k>key) p=p->left;

if (p->k<key) p=p->right;

}

Отметим, что бинарный поиск фактически использует отсортированный массив как некоторое неявное дерево бинарного поиска. Средний элемент этого массива можно представить как корень такого дерева. Левую (верхнюю) половину массива (все те элементы, которые меньше чем средний элемент) можно рассматривать как левое поддерево, а правую (нижнюю) половину (все те элементы, которые больше чем средний элемент) можно рассматривать как правое поддерево.

Отсортированный массив может быть получен из дерева бинарного поиска при помощи прохождения этого дерева в симметричном порядке и вставки каждого элемента последовательно в некоторый массив по мере того, как он встречается в дереве. С другой стороны, для некоторого заданного отсортированного массива можно построить несколько соответствующих ему деревьев бинарного поиска. Рассматривая средний элемент массива как корень некоторого дерева и рассматривая рекурсивно оставшиеся элементы как левые и правые поддеревья, мы получим некоторое относительно сбалансированное дерево бинарного поиска (рис. 4.4). Рассматривая первый элемент массива в качестве корня дерева, а каждый последующий элемент как правого сына его предшественника, мы получим сильно разбалансированное дерево (рис. 4.5).

Преимущество использования дерева бинарного поиска перед отсортированным массивом заключается в том, что структура дерева позволяет выполнять эффективно операции поиска, вставки и удаления.

Рис. 4.4

Рис. 4.5