Двоичное дерево поиска - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

пример двоичного дерева поиска

Рис. 7 Пример двоичного дерева поиска

Двоичное дерево поиска (binary search tree, BST) -- это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

    - Оба поддерева -- левое и правое, являются двоичными деревьями поиска. - У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X. - В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X.

Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.

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

Для целей реализации двоичное дерево поиска можно определить так:

    - Двоичное дерево состоит из узлов (вершин) -- записей вида (data, left, right), где data -- некоторые данные, привязанные к узлу, left и right -- ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) - ссылки на родительский элемент. - Данные (data) обладают ключом (key), на котором определена операция сравнения "меньше". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на нее. - Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[x] ? key[right[x]], т. е. ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нем алгоритмов поиска и сортировки.

Двоичное дерево поиска применяется для построения более абстрактных структур, таких как множества, мультимножества, ассоциативные массивы.

Похожие статьи




Двоичное дерево поиска - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

Предыдущая | Следующая