Добавление ключа

Общий алгоритм поиска

Свойства Б-дерева

Б-деревья

Правила корректировки признака баланса

Общий алгоритм добавления вершины в сбалансированное дерево

1. Производится добавление новой вершины, в которой признак баланса устанавливается в 0 и флаг баланса в true.

2. После этого производится возврат от добавленной вершины к корню, в процессе которого корректируются признаки баланса вершин. Процесс заканчивается:

- Достигли корня и обработали все дерево. Дерево является сбалансированным.

- При корректировке признака баланса получено недопустимое значение (2 или -2), следовательно, в данной вершине возник дисбаланс и выполняется балансировка дерева по рассмотренным ранее схемам.

1. Если флаг баланса “false”, то признак баланса не изменятся.
2. Если флаг “true”:

- Если в вершину пришли с правого поддерева, то признак увеличивается на 1. Если с левого, то уменьшается на 1.

- Если признак равен 0, то флаг устанавливается в ‘false’.

(рисунок)

Б-деревья относятся к классу сильно ветвящихся деревьев.

Дерево строится на основе следующего типового элемента, который является вершиной дерева:

	k1	k2	…	kn
p0	p1	p2	…	pn

Вершина дерева содержит n ключей и (n+1) указателей.

Указатель p₀ указывает на поддерево, содержащее ключи, меньше k₁, p_n указывает на ключи, большие k_n, p_i указывает на ключи, большие k_i и меньшие k_i+1.

p₀<k₁, p_n > k_n, k_i+1 < p_i > k_i

Ключи отсортированы в порядке возрастания.

1. Все листья дерева находятся на одном уровне.
2. Все вершины дерева, кроме корня, имеют от n/2 до n ключей.

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

1. Указатель на текущую вершину устанавливается на корень.
2. Если указатель пустой, то поиск завершен с ошибкой и переход к п.5.
3. Производится поиск заданного ключа среди вершин текущей вершины (применяется двоичный поиск). Если ключ найден, то установка признака успешного поиска и переход к п.5.
4. Если ключа нет, то указателю на текущую вершину присваивается значение соответствующего указателя по значению ключа. Переход к п.2.
5. Конец.

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

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

Если вершина содержит все n ключей (т.е. нет свободного места), то происходит разделение ключей на два множества (пополам) и создается новый лист с вынесением среднего ключа в вершину-родитель.

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

4.6 Древовидная таблица

Древовидная таблица строится на основе двоичного упорядоченного дерева, в котором ключ является кодом вершины и вершина имеет поле для хранения информации. может строится на основе динамического списка и на основе массива записей, в котором имеются поля:

	Ключ	информация	ЛП	ПП
		…
		…	-1	-1
		…	-1
		…	-1	-1
..	…	…	…	…

Раздел 3: Системы программирования низкого уровня

Классификация систем программирования

Классификацию выполним по степени взаимодействия программной системы с аппаратной частью компьютера.

Система программирования	Назначение и состав	Используемые языки	Языки разработки
1. Операционная система	Предназначена для обеспечения работоспособности компьютера, выполнения программ, организации обмена данными и управления памятью.	Языки управления заданиями	Assembler, C (для визуализации)
2. Системы программирования низкого уровня	Предназначены для обеспечения разработки и выполнения несложных программ. Состав: ассемблер (транслятор), редактор связей (компоновщик), загрузчик, простой текстовый редактор, отладчики, библиотека.	Ассемблер (+ иногда дополнительные языки)	Ассемблер, в настоящее время С
3. Системы программирования на универсальных языках	Предназначены для разработки программных продуктов в различных областях.	Языки высокого уровня (C, Paskal)	Раньше Ассемблер, сейчас С, Paskal
4. Системы программирования на специализированных языках	Разработка прикладных программ. Состав: СУБД, САПР, системы удаленного доступа.	Специализированные языки (SQL, FoxPro, GPSS, HTML и т.д.)	Универсальные языки
5. Прикладные программы	Предназначены для решения конкретных задач пользователя.	Специализированные языки, реже – универсальные языки

Дата добавления: 2014-01-15