Программирование. Принципы и практика использования C++ Исправленное издание
вернуться

Страуструп Бьерн
Шрифт:
empty-line/>

Поскольку ключ хранится в члене класса

Node
с именем
first
, основное правило организации бинарного дерева поиска имеет следующий вид:

left–>first<first && first<right–>first

Иначе говоря, для каждого узла выполняются два условия.

• Ключ его левого подузла меньше ключа узла.

• Ключ узла меньше, чем ключ правого подузла.

Можете убедиться, что эти условия выполняются для каждого узла дерева. Это позволяет нам выполнять поиск вниз по дереву, начиная с корня. Забавно, что в литературе по компьютерным наукам деревья растут вниз. Корневым узлом является узел, содержащий пару (Orange, 99). Мы просто перемещаемся по дереву вниз, пока не найдем подходящее место. Дерево называется сбалансированным (balanced), если (как в приведенном выше примере) каждое его поддерево содержит примерно такое же количество узлов, как и одинаково удаленные от корня поддеревья. В сбалансированном дереве среднее количество узлов, которые мы должны пройти, пока не достигнем заданного узла, минимально.

В узле могут храниться дополнительные данные, которые контейнер может использовать для поддержки баланса. Дерево считается сбалансированным, если каждый узел имеет примерно одинаковое количество наследников как слева, так и справа. Если дерево, состоящее из N узлов, сбалансировано, то для обнаружения узла необходимо просмотреть не больше log2N узлов. Это намного лучше, чем N/2 узлов в среднем, которые мы должны были бы просмотреть, если бы ключи хранились в списке, а поиск выполнялся с начала (в худшем случае линейного поиска нам пришлось бы просмотреть N узлов). (См. также раздел 21.6.4.)

Для примера покажем, как выглядит несбалансированное дерево.

Это дерево по-прежнему удовлетворяет критерию, требующему, чтобы ключ каждого узла был больше ключа левого подузла и меньше ключа правого.

left–>first<first && first<right–>first

И все же это дерево является несбалансированным, поэтому нам придется совершить три перехода, чтобы найти узлы Apple и Kiwi, вместо двух, как в сбалансированном дереве. Для деревьев, содержащих много узлов, эта разница может оказаться существенной, поэтому для реализации контейнеров

map
используются сбалансированные деревья.

Разбираться в принципах организации деревьев, используемых для реализации контейнера

map
, необязательно. Достаточно предположить, что профессионалы знают хотя бы принципы их работы. Все, что нам нужно, — это интерфейс класса
map
из стандартной библиотеки. Ниже приведена его несколько упрощенная версия.

template<class Key, class Value, class Cmp = less<Key> > class map

{

// ...

typedef pair<Key,Value> value_type; // контейнер map хранит

// пары (Key,Value)

typedef sometype1 iterator; // указатель на узел дерева

typedef sometype2 const_iterator;

iterator begin; // указывает на первый элемент

iterator end; // указывает на следующий за последним

// элемент

Value& operator[](const Key& k); // индексирование

// по переменной k

iterator find(const Key& k); // поиск по ключу k

void erase(iterator p); // удаление элемента, на который

// указывает итератор p

pair<iterator, bool> insert(const value_type&);

// вставляет пару (key,value)

// ...

};

Настоящий вариант контейнера определен в заголовке

<map>
. Можно представить себе итератор в виде указателя
Node*
, но при реализации итератора нельзя полагаться на какой-то конкретный тип.

Сходство интерфейсов классов

vector
и
list
(см. разделы 20.5 и B.4) очевидно. Основное отличие заключается в том, что при перемещении по контейнеру элементами теперь являются пары типа
pair<Key,Value>
. Этот тип является очень полезным в библиотеке STL.

template<class T1, class T2> struct pair {

typedef T1 first_type;

typedef T2 second_type;

T1 first;

T2 second;

pair:first(T1),second(T2) { }

pair(const T1& x,const T2& y):first(x),second(y) { }

template<class U,class V>

pair(const pair<U,V>& p):first(p.first), second(p.second) { }

};

template<class T1,class T2>
pair<T1,T2> make_pair(T1 x, T2 y)

{