- •1. Структурная схема микропроцессора (на примере i8086). Назначение регистров.
- •3. Организация основной памяти.
- •3. Структура и характеристики оперативной памяти
- •4. Модель osi
- •5. Стек протоколов tcp/ip
- •6. Классификация компьютерных сетей
- •7. Данные и модели данных
- •8. Модель данных «сущность-связь»
- •Ограничения целостности
- •9. Реляционная модель данных
- •10. Основные направления исследования в области ии
- •11. Метод резолюции в лппп.
- •12. Продукционная модель
- •13. Основные парадигмы языков программирования.
- •14. Основные понятия ооп: инкапсуляция, наследование, полиморфизм
- •1. Инкапсуляция
- •2. Полиморфизм
- •3. Наследование
- •15. Понятие алгоритма.
- •16. Понятие о временной и емкостной сложности алгоритма
- •17. Машина Тьюринга: детерминированная и недетерминированная
- •18. Понятие формального языка и формальной грамматики
- •19. Основные понятия теории графов.
- •20. Понятие количества информации и энтропии. Теорема Шеннона.
- •21. Деревья в теории графов.
- •22. Модели линейного программирования (постановка задачи, математическая модель, решение графическим методом).
- •23. Двойственность в задачах линейного программирования.
- •25. Элементы теории игр.
- •2. Подпрограммы. Процедуры и функции
- •3. Массивы
- •4. Записи
- •5. Работа с Динамическими данными
- •6. Динамические структуры данных. Линейные списки.
- •7. Динамические структуры данных: двоичные деревья
- •8. Работа с файлами
- •9.Операции целочисленной арифметики
- •10. Системы счисления. Перевод чисел из одной системы счисления в другую
- •11. Язык sql. Назначение и основные команды.
- •Манипулирование данными
- •Простые запросы
- •12. Алгоритмы внутренней сортировки.
- •13. Алгоритмы внешней сортировки
- •14. Нахождение кратчайших путей в графе
- •15. Поиск в ширину
- •16. Поиск остова и минимального остова.
- •17. Линейная модель работы информационно-поисковой системы.
- •18. Хеширование
- •Основные достоинства в-дерева
- •20. Логические вопросно-ответные системы:выполнение запросов различных типов.
- •21. Поиск в семантической сети.
- •22. Принципы динамического программирования. Иллюстрация на примере.
- •23. Адресация в Интернете
- •Доменные имена
- •Общий вид формата url-адреса
- •Как работает dns-сервер
- •24. Основные сервисы в сети Интернет.
- •Word Wide Web (www) - "Всемирная паутина"
- •Поиск информации в сети
- •VoIp сервис
- •Мессенджеры
- •25. Использование html. Структура Web(html) страницы.
7. Динамические структуры данных: двоичные деревья
Граф называется связным, если между двумя вершинами в нем существует маршрут (вершины называются взаимодостижимыми). Деревом называется связный граф, не содержащий циклов.
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями. В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева - левое поддерево и правое поддерево.
Д воичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n) = C • log2n (в худшем случае O(n) = n).
Пример. Для набора данных 9, 44, 0, –7, 10, 6, –12, 45 построить двоичное дерево поиска.
Согласно определению двоичного дерева поиска число 9 помещаем в корень, все значения, меньшие его — на левое поддерево, большие или равные — на правое. В каждом поддереве очередной элемент можно рассматривать как корень и действовать по тому же алгоритму. В итоге получаем
Выделим типовые операции над двоичными деревьями поиска:
добавление элемента в дерево;
удаление элемента из дерева;
обход дерева (для печати элементов и т.д.);
поиск в дереве.
Поскольку определение двоичного дерева рекурсивно, то все указанные типовые операции могут быть реализованы в виде рекурсивных подпрограмм (на практике именно такой вариант чаще всего и применяется). Отметим лишь, что использование рекурсии замедляет работу программы и расходует лишнюю память при её выполнении.
Пусть двоичное дерево поиска описывается следующим типом
Type
BT=LongInt;
U = ^BinTree;
BinTree = Record;
Inf : BT;
L, R : U;
End;
Покажем два варианта добавления элемента в дерево: итеративный и рекурсивный.
Существует несколько способов обхода (прохождения) всех узлов дерева. Три наиболее часто используемых из них называются обход в прямом (префиксном) порядке, обход в обратном (постфиксном) порядке и обход во внутреннем порядке (или симметричный обход). Каждый из обходов реализуется с использованием рекурсии.
По сравнению с предыдущими задача удаления узла из дерева реализуется несколько сложнее. Можно выделить два случая удаления элемента x (случай отсутствия элемента в дереве является вырожденным):
1) узел, содержащий элемент x, имеет степень не более 1 (степень узла — число поддеревьев, выходящих из этого узла);
2) узел, содержащий элемент x, имеет степень 2.
Случай 1 не представляет сложности. Предыдущий узел соединяется либо с единственным поддеревом удаляемого узла (если степень удаляемого узла равна 1), либо не будет иметь поддерева совсем (если степень узла равна 0).
Намного сложнее, если удаляемый узел имеет два поддерева. В этом случае нужно заменить удаляемый элемент самым правым элементом из его левого поддерева.
Примечание. Если элемент повторяется в дереве несколько раз, то удаляется только первое его вхождение.
Идеально сбалансированное дерево – дерево в котором высоты правого и левого поддеревьев равны.
АВЛ-деревья (сбалансированные деревья) – в каждом элементе которого высоты поддеревьев отличаются не более чем на 1.
АВЛ-балансировка по определению требует, чтобы для каждого узла высота его правого поддерева отличалась от высоты левого не более чем на единицу.
Для любого АВЛ-дерева высоты k с п узлами выполняется соотношение k + 1 < logα п = logα 2 log2 n ≈ 1,44 • log2 n, что обеспечивает «логарифмическую трудоемкость» выполнения основных операций с АВЛ-деревом.
Идея балансировки двоичных деревьев поиска принадлежит Г. М. Адельсону-Вельскому и Е. М. Ландису, предложившим в 1962 г. класс сбалансированных деревьев, называемых с тех пор АВЛ-деревьями. Баланс поддерживается с помощью процедуры вращения. Для его восстановления в дереве с п узлами после добавления или удаления узла может потребоваться Ө(logn) вращений.
Замечательная сторона АВЛ-деревьев в том, что мы их можем поддерживать всегда в сбалансированном виде:
Пусть дан массив 5 3 2 6 1 8 7, отсортируем его и поделим на две части 1 2 3 5 6 7 8
Построим дерево
П ример: добавим элемент 13
hL = hR – баланс не нарушен
hL = hR +1 – баланс нарушится если добавим влево
hR = hL +1 – баланс нарушится если добавим вправо
|hL - hR| ≥ 2 – баланс нарушен
Корень сдвигаем по левому поддереву:
Добавим элемент 15:
=> => =>
Еще один класс деревьев поиска, называемых 2-3-деревьями, был предложен Дж. Хопкрофтом в 1970 г. Здесь баланс поддерживается за счет изменения степеней узлов. Обобщение 2-3-деревьев предложили Д. Байер и Е. Мак-Крейт. Их деревья называются Б-деревьями.
Красно-черные деревья предложил Д. Байер, назвав их симметричными двоичными Б-деревьями. Л. Гибас подробно изучил их свойства и предложил использовать для наглядности красный и черный цвета.
Из многих других вариаций на тему сбалансированных деревьев наиболее интересны расширяющиеся деревья, которые придумали Д. Слеатор и Р. Тарьян. Эти деревья являются саморегулирующимися. Хорошее описание расширяющихся деревьев дал Тарьян. Расширяющиеся деревья поддерживают баланс без использования дополнительных полей (типа цвета). Вместо этого расширяющие операции, включающие вращения, выполняются при каждом обращении к дереву Учетная стоимость в расчете на одну операцию с деревом для расширяющихся деревьев составляет О (log n).