- •Вопрос 33. Необходимые условия возникновения тупика
- •Вопрос 34. Подходы к задаче о предотвращении тупика
- •Вопрос 35. Определение графа повторно используемых ресурсов
- •Вопрос 36. Для решения каких задач используется граф пир?
- •Вопрос 37. Алгоритм редукции графа пир
- •Вопрос 38. Основная теорема о тупике
- •Вопрос 39. Задача распознавания тупика для систем с единичными ресурсами
- •Вопрос 40. Задача распознавания тупика для систем в выгодном состоянии
- •Вопрос 41. Задача обхода тупика
- •Вопрос 42. Вывод системы из тупика
- •Вопрос 43. Граф потребляемых ресурсов
- •Вопрос 44. Редукция графа пр
- •Вопрос 45. Граф обобщенных ресурсов
- •Вопрос 46. Файлы. Организация файлов
- •Вопрос 47. В-деревья
- •Вопрос 48. Операции в в-деревьях
Вопрос 47. В-деревья
В-дерево – структура данных, дерево поиска. Каждый элемент представляет собой массив значений, отсортированных в нужном порядке.
Пусть t – порядок дерева.
В каждой вершине количество записей не превышает 2t.
В дереве не должно быть пустых вершин. Для всех вершин, кроме корневой количество записей должно быть больше либо равно t. В корневой вершине должна быть как минимум 1 запись.
Все терминальные вершины (листы) располагаются на 1 уровне.
Если вершина содержит m элементов и не является терминальной, то количество потомков равно m+1.
Вопрос 48. Операции в в-деревьях
Поиск элемента:
Если элемент содержится в корне, то он найден. Иначе необходимо определить интервал и идти к соответствующему потомку. Повторяем, пока не дойдем до листа.
Добавление ключа
Будем называть деревом потомков некоего узла поддерево, состоящее из этого узла и его потомков.
Вначале определим функцию, которая добавляет ключ K к дереву потомков узла x. После выполнения функции во всех пройденных узлах, кроме, может быть, самого узла x, будет меньше , но не меньше , ключей.
Если х - не лист,
Определяем интервал, где должен находиться K. Пусть y - соответствующий сын.
Рекурсивно добавляем K к дереву потомков y.
Если узел y полон, то есть содержит ключей, расщепляем его на два. Узел получает первые из ключей y и первые его потомков, а узел - последние из ключей y и последние его потомков. Медианный из ключей узла y попадает в узел х, а указатель на y в узле x заменяется указателями на узлы и .
Если x - лист, просто добавляем туда ключ K.
Теперь определим добавление ключа K ко всему дереву. Буквой R обозначается корневой узел.
Добавим K к дереву потомков R.
Если R содержит теперь ключей, расщепляем его на два. Узел получает первые из ключей R и первые его потомков, а узел - последние из ключей R и последние его потомков. Медианный из ключей узла R попадает вo вновь созданный узел, который становится корневым. Узлы и становятся его потомками.
Удаление ключа
Если корень одновременно является листом, то есть в дереве всего один узел, мы просто удаляем ключ из этого узла. В противном случае сначала находим узел, содержащий ключ, запоминая путь к нему. Пусть этот узел - .
Если - лист, удаляем оттуда ключ. Если в узле осталось не меньше ключей, мы на этом останавливаемся. Иначе мы смотрим на количество ключей в следующем, а потом в предыдущем узле. Если следующий узел есть, и в нём не менее ключей, мы добавляем в ключ-разделитель между ним и следующим узлом, а на его место ставим первый ключ следующего узла, после чего останавливаемся. Если это не так, но есть предыдущий узел, и в нём не менее ключей, мы добавляем в ключ-разделитель между ним и предыдущим узлом, а на его место ставим последний ключ предыдущего узла, после чего останавливаемся. Наконец, если и с предыдущим ключом не получилось, мы объединяем узел со следующим или предыдущим узлом, и в объединённый узел перемещаем ключ, разделяющий два узла. При этом в родительском узле может остаться только ключей. Тогда, если это не корень, мы выполняем аналогичную процедуру с ним. Если мы в результате дошли до корня, и в нём осталось от 1 до ключей, делать ничего не надо, потому что корень может иметь и меньше ключей. Если же в корне не осталось ни одного ключа, исключаем корневой узел, а его единственный потомок делаем новым корнем дерева.
Если - не лист, а K - его -й ключ, удаляем самый правый ключ из поддерева потомков -го сына , или, наоборот, самый левый ключ из поддерева потомков -го сына . После этого заменяем ключ K удалённым ключом. Удаление ключа происходит так, как описано в предыдущем абзаце.