В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа [c.161]
Упорядоченное бинарное дерево формируется из неупорядоченного массива записей по специальному алгоритму. Этот алгоритм создает дерево из первой записи массива, затем -дерево из первых двух записей, из первых трех записей и так далее до исчерпания всех записей массива. [c.162]
В процессе поиска данных по совпадению в упорядоченном бинарном дереве просматривается некоторый путь по дереву, начинающийся всегда в его корне. Искомое значение ключа q сравнивается со значением корня р(1). Если p(l)>q, просмотр дерева продолжается по левой ветви корня, если p(l)<=q - по правой. Для произвольной записи дерева с ключом p(i) результаты сравнения означают [c.163]
Для определения среднего числа сравнений при поиске записи в упорядоченном бинарном дереве рассмотрим ситуацию, когда требуемая запись не найдена, что равноценно вставке записи с искомым значением в дерево. Ненайденный ключ может с одинаковой вероятностью попасть в один из М+1 интервалов, образованных ключами, находящимися в дереве. Неудачный поиск закончится всегда на нулевом адресе связи. [c.163]
Если обозначить через Е(М) сумму длин всех ветвей дерева с учетом выхода на нулевые адреса связи, то среднее число сравнений при поиске в упорядоченном бинарном дереве С(М) составит [c.164]
При замене натурального логарифма на двоичный (1п2 = 0,7) получаем оценку числа сравнений при поиске в упорядоченном бинарном дереве [c.164]
При формировании упорядоченного бинарного дерева в среднем производится [c.164]
Включение новой записи при корректировке упорядоченного бинарного дерева означает выполнение одного шага алгоритма формирования дерева с включаемой записью на входе. [c.164]
При исключении полной записи решается задача о подстановке на ее место другой записи, такой, что ее ключ не нарушает общей упорядоченности бинарного дерева - такие записи называются соседними. Соседняя слева запись - это запись с ключом, который непосредственно меньше ключа данной записи, а ключ соседней справа записи равен или непосредственно больше, чем ключ данной записи. [c.165]
Мы приходим к окончательному выводу, что абсолютно безупречного метода организации данных не существует. Однако минимальное время обычно считается более важным критерием, чем минимальная дополнительная память, и тогда лучшим методом организации данных в оперативной памяти ЭВМ необходимо признать упорядоченное бинарное дерево. [c.168]
Как можно использовать упорядоченные бинарные деревья для подсчета частоты встречаемости слов в тексте [c.186]
Какими способами можно объединить два упорядоченных бинарных дерева в одно Выберите из них лучший способ и представьте соответствующий алгоритм. [c.186]
Для последовательного массива и упорядоченного бинарного дерева известен алгоритм поиска по совпадению. Как использовать этот алгоритм для поиска по условию p(i)>q [c.186]