Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья.

В практическом программировании для организации хранения данных и доступа к ним часто используется механизм, который называют ассоциативной памятью. При использовании ассоциативной памяти данные делятся на порции (записи), и с каждой записью ассоциируется ключ. Ключ – значение из некоторого вполне упорядоченного множества. Записи могут иметь произвольную природу и различные размеры. Доступ к данным осуществляется по ключу, который выбирают простым, компактным и удобным для работы.

Пример:Пример ассоциативной памяти. Банковский счет: ключ – номер счета, запись – финансовая информация.

Ассоциативная память должна поддерживать три основные операции: 1) Добавить (ключ, запись); 2) Найти (запись по ключу); 3) Удалить (ключ). Для представления ассоциативной памяти используют следующие структуры данных: 1) Неупорядоченный массив; 2) Упорядоченный массив; 3) Дерево сортировки (бинарное дерево, каждый узел которого содержит ключ и обладает следующим свойством: значение ключа во всех узлах левого поддерева меньше, а во всех узлах правого поддерева больше, чем значение ключа в узле). 4) Таблица расстановки, или хэш-таблица.

 

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

Пример: На рисунке приведены две диаграммы деревьев, которые изоморфны как упорядоченные, ориентированные и свободные деревья, но не изоморфны как бинарные деревья.

 

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

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

Наибольший эффект при поиске дают выровненные деревья. Ордерево – выровненное, если все узлы, степень которых меньше 2, располагаются на одном или двух последних уровнях.

Пример: На рисунке показаны диаграммы выровненного (а) и невыровненного (б) деревьев.

Бинарное дерево – сбалансированное (подровненное), если для каждого узла высота левого и правого поддеревьев отличается не более, чем на единицу.

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