русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Хранение в бинарном дереве алфавитного списка


Дата добавления: 2013-12-23; просмотров: 706; Нарушение авторских прав


Реализация дерева

Деревья

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

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

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

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

Если какого-то элемента в дереве нет, то в выделенной для него области памяти стоит отметка об этом.

Расположим записи в упорядоченном по алфавиту объеме информации последовательно. Среднюю из них поместим в корневой узел дерева. Остальное (без данного корневого элемента) дерево будем считать состоящим из левого и правого поддерева. Затем для каждой из оставшихся половинок (левой и правой) упорядоченного по алфавиту объема информационных записей опять находим средний элемент и помещаем в корень соответствующего левого или правого поддерева. И так продолжаем, пока не разместим в бинарном дереве все информационные записи.



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

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

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

Указатель на дерево содержит адрес его корневого блока.

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

 



<== предыдущая лекция | следующая лекция ==>
Реализация очереди | Модель OSI


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.