71.Методы обработки файлов на физическом уровне. Алгоритм поиска по бинарному дереву.

Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказвается меньше ключа, поиск продолжается в левом поддереве, а в случае когда больше ключа - в правом поддереве. Увеличив уровень на 1 повторяют сравнение, считая текущий узел корнем.

Пример: Пусть дан список студентов, содержащий их фамили и средний бал успеваемости (см. таблицу). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычислятся как ([номер_записи] -1 ) * [длина_записи]. Пусть аргумент поиска "Петров". На рисунке показаны одно из возможных для этого набора данных бинарных деревьев поиска и путь поиска.

Таблица 1.1.
Студент	Балл
Васильев	4,2
Иванов	3,4
Кузнецов	3,5
Петров	3,2
Сидоров	4,6
Тихомиров	3,8

Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

Бинарные деревья особенно эффективны в случае когда множество ключей заранее неизвестно, либо когда это множество интенсивно изменяется. Очевидно, что при переменном множестве ключей лучше иметь сбалансированное дерево.

70.Слабые сущности в инфологической модели «Сущность-связь». Определение, пример, графическая интерпретация.

В модели «сущность—связь» определен особый тип сущности, называемый слабой сущностью (weak entity). К слабым сущностям относятся такие сущности, которые могут существовать в базе данных только в том случае, если в ней присутствует сущность некоторого другого типа. Сущность, не являющаяся слабой, называется сильной сущностью (strong entity). Чтобы разобраться в том, что такое слабые сущности, рассмотрим базу данных отдела кадров с классами сущностей СОТРУДНИКИ-ПОДЧИНЕННЫЙ. Предположим, что в соответствии с деловым регламентом, экземпляр сущности Сотрудник может существовать, не будучи связанным ни с одной сущностью класса ПОДЧИНЕННЫЙ, но сущность ПОДЧИНЕННЫЙ не может существовать вне связи с какой-либо сущностью класса СОТРУДНИК. Тогда сущность ПОДЧИНЕННЫЙ является слабой. Это означает, что данные о сущности ПОДЧИНЕННЫЙ могут появиться в базе данных только в том случае, если эта сущность имеет связь с какой-либо сущностью класса СОТРУДНИК.