Язык С++ и программирование на нем. Рейзлин В.И. - 152 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

154
дов. Организация этой таблицы должна быть такой, чтобы, во-первых, в
ней довольно быстро можно было находить элементы с данным значе-
нием (или устанавливать факт отсутствия его в таблице), и, во-вторых,
без особых затрат добавлять в таблицу новые элементы.
Этим требованиям удовлетворяет представление таблицы в виде
двоичного дерева, в вершинах которого расположены различные эле-
менты из данной последовательности и их коды.
Процесс построения двоичного дерева идет так: первое число и
его код образуют корень. Следующее число, которое нужно кодировать,
сравнивается с числом в корне, и если они равны, то дерево не разраста-
ется и код может быть взят из корня. Если новое число меньше первого,
то проводится ребро из корня влево вниз, иначе – вправо вниз. В обра-
зовавшуюся вершину помещаются это новое число и его код.
Пусть уже построено некоторое дерево и имеется некоторое число
x, которое нужно закодировать. Сначала сравниваем с x число из корня.
В случае равенства поиск закончен, и код x извлекается из корня. В про-
тивном случае переходим к рассмотрению вершины, которая находится
слева внизу, если x меньше только что рассмотренного, или справа
внизу, если x больше рассмотренного. Сравниваем x с числом из этой
вершины и т.д. Процесс завершается в одном из двух случаев:
1) Найдена вершина, содержащая число x.
2) В дереве отсутствует вершина, к которой надо перейти для вы-
полнения очередного шага поиска.
В первом случае из найденной вершины извлекается код числа x.
Во втором необходимо вычислить F(x) и присоединить к дереву вер-
шину, в которой расположены x и F(x). Пусть последовательность на-
чинается с чисел 8, 4, 13, 10, 14, 10. Тогда вначале дерево будет разрас-
таться следующим образом (рис. 9 а-д):
8, F(8) 8, F(8) 8, F(8) 8, F(8) 8, F(8)
4, F(4) 4, F(4) 13, F(13) 4, F(4) 13, F(13) 4, F(4) 13, F(13)
10, F(10) 10, F(10) 14, F(14)
а б в г д
Рис. 9. Разрастание двоичного дерева в задаче кодирования

Страницы