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.

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


 

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

35788. МОЙ ВЫБОР. Рабочая тетрадь проекта по профессиональному самоопределению 102 KB
  И мы надеемся рабочая тетрадь Мой выбор поможет Вам в этом так как проблема выбора профессии рано или поздно встаёт перед любым человеком. Правильный выбор профессии можно назвать той ступенькой которая поможет Вам добиться творческих успехов достичь поставленных целей найти смысл своей жизни. Только серьёзные размышления о своём месте в жизни и активная деятельность по выбору профессии приведут Вас к верному решению. Основная цель рабочей тетради – помочь Вам понять себя свои особенности цели в жизни и на основе этого сделать...
35789. Мой выбор. Творческий проект По самоопределению 92 KB
  Обоснование выбора профессии Профессиональное самоопределение – важный и ответственный шаг в жизни каждого человека. Но осуществить добровольный выбор профессии очень не просто. Общая характеристика профессии. Общение с людьми также важно в профессии журналист.
35790. Лялька - мотанка 3.57 MB
  Коли нам запропонували теми для творчого проекту, я вирішила обрати саме «Лялька - мотанка в українському стилі». Адже мотанка — прадавній оберіг українського народу. Вона несе в собі сонячну енергетику, тепло людських рук, любов і турботу, з якою створена. Головне призначення ляльки — берегти душу свого власника від зла й нечистих помислів.
35791. Творческий проект «Сорочка» 5.51 MB
  Расчет себестоимости изготовления изделия План Изготовления изделия Изготовления изделия и проверка качества Самооценка и оценка 1.Задачи Провести исследование и разработать эскиз моего проектного изделия. Изготовить выкройку швейного изделия. Подобрать ткань для изделия.
35792. Выбор профессии 168 KB
  Появление профессии Определение интересов и склонностей Обоснование выбора Алгоритм профессион. самопределения Формула профессии Выявление индивидуальных характер. Выбор профессии – это большая ответственность которую очень важно осознать как можно раньше.
35794. Кружка. Творческий проект 158.5 KB
  4 Технологическая карта № детали № операции Название операции Эскиз Инструмент и приспособления 1 1 Выбрать заготовку с учётом припуска на обработку Линейка 2 Прострогать базовую сторону Верстак рубанок 3 Разметить и прострогать заготовку по толщине Линейка рубанок карандаш 4 Разметить и прострогать по ширине Линейка рубанок карандаш 5 Отторцевать заготовку Угольник карандаш подкладка 6 Разметить и отпилить заготовку по длине Верстак линейка угольник карандаш ножовка 7 Разметить заготовку по чертежу Линейка угольник карандаш...
35795. Вышивка своими руками. Творческий проект 1.18 MB
  Вышивание крестом – один из самых распространенных видов народного искусства. История возникновения вышивки крестом уходит далеко в глубь веков когда появился первый стежок сделанный первобытными людьми при скреплении шкуры убитого мамонта. Материалом для вышивки крестом служили: жилы животных нити льна хлопка конопли шелка шерсти а так же применяли натуральный волос. Особой популярности вышивка крестом достигла в Западной Европе в XVI столетии.
35796. Метод проектів на уроках трудового навчання (обслуговуюча праця) 461 KB
  Проектна технологія — практика особистісно зорієнтованого трудового навчання в процесі конкретної навчально-трудової діяльності учня, на основі його вільного вибору та з урахуванням інтересів. У свідомості учня це має такий вигляд: «Я знаю, для чого мені потрібно все, що я пізнаю, і де я можу ці знання застосувати». Для педагога це прагнення знайти розумний баланс між академічними і прагматичними знаннями, уміннями та навичками.