47288

Процедура построения почти полного дерева поиска и ее особенности

Доклад

Информатика, кибернетика и программирование

Бинарное дерево-это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом.

Русский

2014-03-31

82.69 KB

1 чел.

Процедура построения почти полного дерева поиска и ее особенности.

Бинарное дерево-это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом.

Эти подмножества называются левым и правым поддеревьями исходного дерева.

Каждый элемент бинарного дерева называется узлом дерева.

Почти полное бинарное дерево (ППБД) - это дерево, для которого существует неотрицательное целое число К такое, что:

1. Каждый лист в дереве имеет уровень К или К + 1.

2. Если некоторый узел дерева имеет правого потомка, уровеня К + 1, тогда все левые потомки этого узла, являющиеся листьями, также имеют уровень К + 1.

Примечание. В таком дереве, если у узла есть непосредственный правый потомок-сын, являющийся листом уровня К + 1, то его левый потомок-сын также является листом уровня К + 1.

Пример 3. У приведенного ниже дерева условия 1 и 2 выполняются. Число К = 2. Это ППБД и СБД. У него 6 листьев и 2*6 - 1 = 11 узлов.

B

C

D

E

G

H

L

I

M

F

A

Пример 4. У приведенного ниже дерева условия 1 и 2 выполняются. Число К = 2. Это ППБД и СБД. У него 6 листьев и 2 * 6 - 1 = 12 узлов


A

B

C

D

E

F

G

H

I

J

I

H

Пример 5. У приведенного ниже дерева число К = 2, но условие 2 не выполняются. Это не ППБД, но СБД. У него 6 листьев и 2*6 - 1 = 12 узлов. Действительно, у узла А есть правый потомок уровня 3 (узел К) и левый потомок уровня 2 (узел Е).

A

B

D

E

I

H

C

F

G

J

K

Важным свойством ППБД является возможность перенумеровать его узлы так, что корню назначается номер 1, левому сыну удвоенный номер отца, а правому сыну удвоенный номер отца плюс 1.

Выполним такую нумерацию для дерева в примере 6.

1

2

3

4

5

6

7

8

9

10

Пример 6.

При такой схеме нумерации каждому узлу ППБД присвоен уникальный номер, который однозначно определяет позицию узла внутри дерева. Дыр в нумерации не допускается.


 

А также другие работы, которые могут Вас заинтересовать

46990. Статистика населения. Перестрахование как операция по достижению финансовой устойчивости страховщика 44.64 KB
  Статистика населения. Статистика населения это древнейшая отрасль статист науки которая изучает население и процессы связанные с его динамикой с колич кач стороной в конкр условиях общественного развития. Статистика населения использует свои методы с целью более полного изучения анализа и прогнозирования населения страны регионов и т. К основным демографическим показателям относятся: численность и состав населения число родившихся и умерших число браков и разводов численность прибывших и выбывших из страны.
46991. Инновации в профессиональном образовании. Психология профессионального обучения и социально-профессионального воспитания 42.5 KB
  Психология профессионального обучения и социальнопрофессионального воспитания Наиболее общим понятием является научение которое определяется как целесообразное изменение деятельности и поведения в процессе выполнения какихлибо действий: физических умственных.Происходит все более качественное выполнение действий при ослабевающем временами произвольном внимании устраняются лишние движения появляются возможности положительного переноса навыка. 4 Высокоавтоматизированный навык точное экономное устойчивое выполнение действий 5...
46994. СТРАТЕГИЧЕСКИЙ МЕНЕДЖМЕНТ 43.1 KB
  Участники процесса стратегического управления Генеральный директор на фирме как капитан корабля является самым влиятельным и ответственным менеджером по стратегии. Вицепрезиденты по производству маркетингу финансам кадрам и другие функциональные руководители тоже несут ответственность за разработку и осуществление стратегии. Функциональные руководители принимают деятельное участие в предложении в разработке ключевых направлений общей стратегии работая вместе с исполнительным директором и добиваясь выработки консенсуса они повышают...
46995. Бюджетирование и контроль деятельности центров ответственности 36.39 KB
  Расходы УОК делятся на постоянные и переменные. К постоянным относятся арендные платежи командировочные расходы расходы на проведение семинаров съездов почтовые представительские издержки и другие. Переменные расходы УОК фонд оплаты труда ФОТ с налогами закупка материалов оплата услуг сторонних организаций. расходы.
46996. Работа редактора над научно-популярным изданием 43 KB
  Работа редактора над научно-популярным изданием Научно-популярное издание издание которое содержит сведения о теоретических и или экспериментальных исследованиях и предназначено для популяризации и пропаганды основ и достижений науки и техники культуры и результатов прикладной деятельности среди широких масс читателей в доступной для них форме. Тематика научно-популярных изданий может быть весьма широкой. В общем предметом содержания научнопопулярного издания можно считать все что имеет отношение к науке и научным исследованиям. Целевое...
46998. Предмет и содержание курса «История Беларуси». Основные подходы к изучению истории 43.26 KB
  Кроме пашни древнее население Беларуси имело огороды и сады . 4 Экономическое развитие и социальные отношения в Беларуси в 1416 вв. На территории Беларуси продолжается процесс формирования и совершенствования феодальных отношений.