Алгоритм на псевдокоде


Алгоритм А1(Root – указатель на корень дерева)

Обозначим

V.use – логическая переменная в структуре вершины дерева, которая показывает, что данная вершина была использована при построении дерева;

V.w – вес вершины.

 

Root : = NIL

DO (i = 1,...,n)

V[i].use = ЛОЖЬ

OD

DO (i = 1,...,n)

max:=0, Index:=0

DO (j = 1,...,n)

IF (V[j].w > max и V[j]. use=ЛОЖЬ)

max:=V[j].w

Index:=j

FI

OD

V [index].use :=ИСТИНА

Добавление в СДП (Root, V[index])

OD

Рассмотрим пример построения дерева почти оптимального поиска для символов строки К У Р А П О В А Е Л Е Н А В И К Т О Р О В Н А. Всего символов в строке 23, т.е. W=23. Различные символы определяют различные вершины дерева. Частоты вхождения символов (веса) приведены в таблице.

Таблица 3 Частоты вхождения символов в строку

К У Р А П О В Е Л Н И Т

Посчитаем средневзвешенную высоту построенного дерева

P=4.1+3.2+3.3+2.3+2.4+1.4+1.4+2.5+ +2.5+1.5+1.6+1.6=78

hср=P/W=78/23=3,39

 

Рисунок 59 Дерево, построенное приближенным алгоритмом А1

Второй алгоритм (А2) использует предварительно упорядоченный набор вершин. В качестве корня выбирается такая вершина, что разность весов левого и правого поддеревьев была минимальна. Для этого путем последовательного суммирования весов определим вершину Vk, для которой справедливы неравенства:

и .

Тогда в качестве "центра тяжести" может быть выбрана вершина Vk, Vk-1 или Vk+1, т. е. вершина, для которой разность весов левого и правого поддерева минимальна. Далее действия повторяются для каждого поддерева

 



Дата добавления: 2022-02-05; просмотров: 241;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.