Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 60290
Реклама
Сейчас на сайте
Гостей: 5
На сайте нет зарегистрированных пользователей

Пользователей: 13,115
новичок: sborzabor
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование информационно-поисковой библиографической системы на gpss ...
Калькулятор на Delphi с переводом в другую систему исчисления + Блок схемы
Создание последовательности окон и передвижение окон по экрану на Turbo ...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Бинарные деревья


Бинарное дерево определяется рекурсивно как имеющее левое поддерево, корень и правое поддерево. Левое и правое поддеревья сами являются бинарными деревьями. На рис. 2.1 показан пример бинарного дерева.
Бинарное дерево
Бинарные деревья
Рис. 2.1

Такие деревья можно представить термами вида
бд(Лд, К, Пд),



где Лд - левое поддерево, К - корень, а Пд - правое поддерево. Для обозначения пустого бинарного дерева будем использовать атом nil. Бинарное дерево на рис. 2.1 имеет левое поддерево
бд(бд(nil, d, nil), b, бд(nil, е, nil))



правое поддерево
бд(nil,с, nil)



и записывается целиком как
бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)).




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

?- принадлежит(3000, b).




Прологу придется проверить все 1024 числа, прежде чем заключить, что такого числа нет:
нет



Представление множества бинарным деревом позволяет добиться лучшего результата. При этом бинарное дерево должно быть упорядочено таким образом, чтобы любой элемент в левом поддереве был меньше, чем значение корня, а любой элемент в правом поддереве — больше. Поскольку мы определили поддерево как бинарное дерево, такое упорядочение применяется по всем поддеревьям. На рис. 2.2 приведен пример упорядоченного бинарного дерева (дерево на рис. 2.1 является неупорядоченным).

Упорядоченное бинарное дерево
Упорядоченное бинарное дерево
Рис. 2.2

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

Линейное представление
Линейное представление
Рис. 2.3

Моделирование принадлежности множеству. Имея множество, описанное бинарным деревом, мы можем моделировать принадлежность множеству с помощью целевого утверждения принадлежит_дереву. При этом используется оператор @<, выражающий отношение “меньше, чем”, и оператор @>, выражающий отношение “больше, чем”.

/* Граничное условие: Х принадлежит
/* дереву, если Х является корнем.
принадлежит_дереву(Х, бд(Лд, Х, Пд)),
/* Рекурсивные условия
/* Х принадлежит дереву, если Х больше
/* значении корня и находится в правом
/* поддереве:
принадлежит_дереву(Х, бд(Лд, У, Пд)) :- X@Y,
принадлежит_дереву(Х, Пд).
/* Х принадлежит дереву, если Х меньше
/* значения корня и находится в левом
/* поддереве:
принадлежит_дереву(Х, бд(Лд ,У ,Пд)) :-X@Y,
принадлежит_дереву(Х, Лд).
Если множество из первых 1024 чисел описать с помощью сбалансированного бинарного дерева Т, то при ответе на запрос
?- принадлежит_дереву(3000, Т).




Пролог сравнит число 3000 не более чем с 11 элементами множества. прежде чем ответит:
нет



Конечно, если Т имеет линейное представление, то потребуется сравнение 3000 с 1024 элементами множества.

Построение бинарного дерева. Задача создания упорядоченного бинарного дерева при добавлении элемента Х к другому упорядоченному бинарному дереву формулируется следующим образом:
Граничное условие:
Добавление Х к nil дает бд(nil, Х, nil).
Рекурсивные условия:
При добавлении Х к бд(Лд, К, Пд) нужно рассмотреть два случая, чтобы быть уверенным, что результирующее дерево будет упорядоченным.
1. Х меньше, чем К. В этом случае нужно добавить Х к Лд, чтобы получить левое поддерево. Правое поддерево равно Пд, а значение корня результирующего дерева равно К.
2. Х больше, чем К. В таком случае нужно добавить Х к Пд, чтобы получить правое поддерево. Левое поддерево равно Лд, а значение корня - К.
Такой формулировке задачи соответствует программа:

/* Граничное условие:
включ_бд(nil, Х, бд(nil, Х, nil)).
/* Рекурсивные условия:
/*(1)
включ_бд(бд(Лд, К, Пд), Х, бд(Лднов, К, Пд)) :-
Х@К,
включ_бд(Лд,Х,Лднов).
/*(2)
включ_бд(бд(Лд, К, Пд), Х, бд(Лд, К, Пднов)) :-
Х@К,
включ_бд(Пд, Х, Пднов).



На запрос
?- включ_бд(nil, d, Т1), включ_бд(Т1, а, Т2).



будут получены значения
Т1=бд(nil, d, nil)
Т2=бд(бд(nil, а, nil), d, nil)




Процедуру включ_бд() можно использовать для построения упорядоченного дерева из списка:

/* Граничное условие:
список_в_дерево([], nil).
/* Рекурсивное условие:
список_в_дерево([Н | Т], Бд) :-
список_в_дерево(Т, Бд2),
включ_бд(Н, Бд2, Бд).




Заметим, что включ_бд не обеспечивает построения сбалансированного дерева. Однако существуют алгоритмы, гарантирующие такое построение.




Опубликовал Kest Октябрь 10 2010 21:38:14 · 0 Комментариев · 9473 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Отлично! Отлично! 100% [1 Голос]
Очень хорошо Очень хорошо 0% [Нет голосов]
Хорошо Хорошо 0% [Нет голосов]
Удовлетворительно Удовлетворительно 0% [Нет голосов]
Плохо Плохо 0% [Нет голосов]
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Delphi 7: Для про...
Ранги для форума
База игр
PHP 5
Мод "проверочный ...
Система баннеро-о...
Borland Delphi 8 ...
Программирование ...
Gold Submitter II...
HtmlLerz PRO
Применение фильтр...
Архив Апгрейтов с...
C++ Стандартная б...
Tenis [Исходник н...
Редактор анимаций
Приемы программир...
Профессиональное ...
Bitmap [для кнопок]
AddPage [Исходник...
45 уроков по дельфи

Топ загрузок
Приложение Клие... 100521
Delphi 7 Enterp... 91491
Converter AMR<-... 20099
GPSS World Stud... 15228
Borland C++Buil... 12967
Borland Delphi ... 9097
Turbo Pascal fo... 7110
Калькулятор [Ис... 5174
Visual Studio 2... 5030
FreeSMS v1.3.1 3558
Случайные статьи
Модуль CRT. Раблта...
Kак увеличить посе...
Клонирование устро...
Функция GetMaxMode...
связи
Типы данных. Целоч...
Пример обработки т...
Оператор switch дл...
Использование прог...
он будет отвечать ...
Как сконфигурирова...
Многопоточные очереди
Управление потоком...
Повышение информац...
Файлы в папке Wind...
Изменение цвета сл...
Обеспечение требуе...
Банкетные стулья К...
Метод основного до...
Зачем нужен цифров...
Отображение номера...
Асимметричная пере...
Применение средств...
7.5. Принципы
Временные меры чис...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?