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

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

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) = h_min (n) =élog(n+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 – левая и правая границы той части массива, из элементов которой строится дерево.