Другими словами, двоичное дерево, обладающее свойством «формы», заканчивается не более чем на двух уровнях (то есть заключительные узлы расположены не более чем на двух уровнях), причем находящиеся на нижнем уровне узлы сгруппированы слева. В дереве не должно быть незанятых узлов. Если в нем содержится п узлов, ни один из них не может отстоять более чем на log2 п от корня. Вскоре мы увидим, как эти два свойства оказываются достаточно жесткими, чтобы мы могли найти наименьший элемент набора, но при этом допускают реорганизацию структуры при добавлении или удалении элемента.
Перейдем от абстрактных свойств куч к их реализации. Наиболее общее представление двоичных деревьев использует записи и указатели. Мы воспользуемся представлением, пригодным только для двоичных деревьев, обладающих свойством формы. Дерево, обладающее свойством формы и состоящее из 12 элементов, может быть представлено в 12-элементном массиве так, как это показано на рис. 14.3.
х[1]
*[6]
42]
х[3]
х[5]
*[4]
х[7]
х[8] х[9] х[10] х[11] х[12]
Рис. 14.3. Представление кучи с помощью массива
Обратите внимание, что для представления куч массивы нумеруются с единицы. Избежать проблем в языке С проще всего, объявив массив х[п+1] и забыв о нулевом элементе. В этом неявном представлении двоичного дерева его корень хранится в элементе х[1], узлы первого уровня — в элементах х[2] и х[3], и так далее. Типичные функции для такого дерева определяются следующим образом:
root = 1
value( i) = х[i]
1eftchi1d(i ) = 2*i
nghtchi1d(i ) = 2*i + 1
parent(i) = i /2
nul1(l ) = (i < 1) или (i > n)
Неявное дерево из n элементов обязательно будет обладать свойством формы: отсутствие элементов в нем просто не предусмотрено.
Опубликовал vovan666
April 17 2013 00:04:03 ·
0 Комментариев ·
2818 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
