Деревья

Бинарные деревья

Вы когда-нибудь задавали себе вопрос – как устроены индексы в СУБД? А может быть, у вас возникала потребность в применении высокопроизводительных алгоритмов доступа к данным? На эти и некоторые другие вопросы призван ответить ряд статей под общим названием «Высокопроизводительные алгоритмы». В этом цикле речь пойдет о деревьях, хешах и тому подобному. Первая статья посвящена деревьям. Вернее, бинарным деревьям.

Как известно, для ускорения доступа к информации применяется индексы. Есть много типов индексов битовые, кластерные хеш-индексы, но, наверное, самым популярным и распространенным являются индексы на основе бинарных деревьев.

Деревья

Массивы и связанные списки определяют коллекции объектов, доступ к которым осуществляется последовательно. Такие структуры данных называют линейными (linear) списками, поскольку они имеют уникальные первый и последний элементы и у каждого внутреннего элемента есть только один наследник. Линейный список является абстракцией, позволяющей манипулировать данными, представляемыми различным образом — массивами, стеками, очередями и связанными списками.

Во многих приложениях обнаруживается нелинейный порядок объектов, где элементы могут иметь нескольких наследников. Например, в фамильном дереве родитель может иметь нескольких потомков (детей). На Рис. 1 показаны три поколения семьи. Такое упорядочение называют иерархическим.

Рис.1.

В этой статье мы рассмотрим нелинейную структуру, называемую деревом (tree), которая состоит из узлов и ветвей и имеет направление от корня к внешним узлам, называемым листьями. Эти структуры подобны коммуникационной сети, показанной на Рис. 2, требуют особых алгоритмов и применяются в специальных приложениях.

Рис. 2