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


Поиск вершины с ключом Х

p: = Root

DO (p ≠ NIL)

IF (p→Data < x) p: = p→Right

ELSEIF (p→Data > x) p: = p→Left

ELSE OD { p→Data = x }

OD

IF (p ≠ NIL) <вершина найдена>

ELSE <вершина не найдена>

Нетрудно видеть, что максимальное количество сравнений при поиске равно Сmax = 2h, где h высота дерева.

10.2 Идеально сбалансированное дерево поиска

Двоичное дерево называется идеально сбалансированным (ИСД), если для каждой его вершины размеры левого и правого поддеревьев отличаются не более чем на 1.

На рисунке приведены примеры деревьев, одно из которых является идеально сбалансированным, а другое – нет.

 

 

 


Рисунок 30 Примеры ИСД и неИСД

Отметим некоторые свойства идеально сбалансированного дерева.

Свойство 1. Высота ИСД с n вершинами минимальна и равна

hИСД(n) = hmin (n) =élog(n+1)ù.

Свойство 2. Если дерево идеально сбалансировано, то все его поддеревья также идеально сбалансированы.

Задача построения идеально сбалансированного дерева поиска из элементов массива А = (а1, а2, … , аn) решается в два этапа:

1. Сортировка массива А.

2. В качестве корня дерева возьмем средний элемент отсортированного массива, из меньших элементов массива строим левое поддерево, из больших – правое поддерево. Далее процесс построения продолжается до тех пор, пока левое или правое поддерево не станет пустым.

Пример. Построить ИСДП из элементов массива А. Пусть n = 16, а элементы массива это числа в 16-ричной системе счисления.

 

А: В 9 2 4 1 7 Е F A D C 3 5 8 6

 

Аупор:1 2 3 4 5 6 7 8 9 А В С D E F

Рисунок 31 Построение ИСДП

Приведем на псевдокоде алгоритм построения ИСДП. Функция ИСДП (L, R) возвращает указатель на построенное дерево, где L, R – левая и правая границы той части массива, из элементов которой строится дерево.

 



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


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

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

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

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