Сбалансированное дерево в котором каждый порождающий элемент имеет не более 2-х потомков наз-ся двоичным или бинарным деревом .направления от порождающего элемента дерева к порожденному элементу могут быть левыми и правыми .все узлы связанные с данным узлом посредством левой привязки образуют левое под дерево , а узлы связанные посредством правой привязки-правое поддерево.двоичные деревья очень удобны в работе.
Построение двоичного дерева из произвольного
Для каждого порождающего узла уничтожаются все исходящие из него ребра кроме самого левого все оторвавшиеся порожденные того же уровня связываются с левым поражденным указателями на подобные элементы
//рисунок пример
Левое направление идет к узлу в котором размещена запись меньшая чем запись в порождающем узле , а правое направление ведет к узлу с записью имеющий больщий луч
Для построения симметричного дерева необходима предварительная обработка исходной последовательности данных ,которая выполняется в два этапа:
1 этап : исходная последовательность данных записи упорядоивается по возростанию или убыванию значений величины полей
2 этап : определяются ключи размещаемые в узлах различных уровней дерева
в корневом узле разместится ключ расположенный в центре упорядоченной последовательности, т .е.ключделящий ее пополам .ключи делящие пополам левую и правую последовательности размещаются в узлах 2-го уровня левого и правого поддеревьев. Процедура деления вновь получаемых отрезков последовательности и отыскание ключей соответствующих уровней продолжается до тех пор пока дерево не будет построенно полностью.
//рисунок 2
10,7,21,33,37,34,36,40,80,90,50,52
7,10,21,33,34,36,37,40,50,52,80,90 36-корневой элемент
//рисунок 3
Свойства: пути в дереве от корня до любой вершины имеют одинаковую минимальную длину
Для характеристики степени приближения сбалансированого дерева к симметричному виду используют понятие ОБЬЕМ ДЕРЕВА:
Сумма от n*L(n) где n меняется от 0 до N,
Где N- количество уровней дерева , L(n)-число узлов на этом уровне
Высота дерева определяется как максимальный уровень всех его вершин Уровень вершины (листа i) определяется длиной пути от корневой вершины до вершины i
При обработке двоичных структур наиболее типичной яв-ся операция обхода
Эта процедура при выполнении которой каждый узел обрабатываетс ровно 1 раз .произвольное бинарное дерево можно обходить восходящим нисходящим и смещанными обходами .способы обхода различаются точкой входа в дерево ,направлением движения по дереву ,временем обработки корневого узла относительно первого обработанного.
В роли корневого может выступать любой уровень дерева имеющий порожденный. В каждом случае это будет корень соответсвующего под дерева .
Нисходящий обход: первым читается корень ,узлы читаются в процессе движения вниз и влево ,если пути влево нет то движение продолжается по ближайшему правому пути,при этом сразу после просмотра очередного узла просматриваются слева на право исходящие из него ветви: 32,21,7,10,33,34,,52,37,50,80,60,90
Восходящий обход: чтение начинается с левого листа ,каждый узел читается после того как прочитаны его левый и правый порожденные узлы. 10,7,33,34,21,50,37,60,90,80,52,36
Смешанный обход первым читается левый лист ,затем следует последовательно подьемы и спуски , каждый узел читается лишь тогда когда полностью обойденно его левое поддерево, после чего обходится его правое под дерево. 7,10,21,33,34,36,37,50,52,60,80,90
В результате смешанного подхода получается последовательность упорядоченная по возростанию значений ключей.
СЕТЕВАЯ МОДЕЛЬ ДАННЫХ (смд)
В основе смд лежит возможность представления связей между данными в графической форме .наиболее развитой смд является КОДАСИЛ. В ОСНОВЕ ЭТОЙ МОДЕЛИ ЛЕЖАТ ПОНЯТИЯ
Сущность и связь ,а к основным типам структур данных относят элемент данных ,агрегат ,запись,набор. Сущность это некоторая абстракция реально существующего обьекта,предметной области ,процесса или явления. Набор однородных обьектов и явлений определяет тип сущности .каждый конкретный обьект в наборе представляет экземпляр сущности .связи между сущностями фиксируются заданным множеством отношений .при анализе связей часто используют бинарные связи,связи между двумя сущностями.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.