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.

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


 

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

34002. Проблема истины. Критерий истины 36.5 KB
  Критерий истины. Объективное и субъективное знание = Ю такие же истины. истины разные формы объетивной истины.
34003. Специфика философского знания. Структура философского знания 24 KB
  Философия существует в виде знания которое необходимо специфицировать например на основе сопоставления с научным знанием. Их соотношение можно изобразить графически: Под физическим знанием в широком смысле понимается знание которое может быть проверено опытным путем. Философское знание по большей части есть умозрительное знание в котором субъективнооценочный момент выражен неизмеримо сильнее чем в научном знании. Философия же есть только знание.
34004. Антропология 25 KB
  в изучении человека никогда не будет поставлена точка что никогда очевидно не удастся создать унифицированную теорию человека.Сущность человека нельзя точно и строго зафиксировать как например сущность лошади собаки змеи и т. Универсальность человека многомерна.1она означает разнообразие и многообразие человека и человечества во времени и пространстве.
34005. Понятие человека 38 KB
  Изучая поведение разных животных и человека К. Практически все инстинкты у социализированного человека поставлены под контроль общества и моральнопсихологических механизмов саморегуляции. при помощи которой сдерживаются агрессивные импульсы умиротворяется и облагораживается эмоциональноволевая сфера человека.
34006. Основные антропологические парадигмы 31.5 KB
  Проблема человека одна из центральных тем философии. В разных философских традициях и школах по разному трактуется феномен человека. Христианская антропология зиждется на ряде основополагающих постулатов: а человек есть триединство духовного душевного и телесного;б человек есть образ и подобие Божие;в онтологическая ущербность человека наступившая после грехопадения прародителей человечества Адама и Евы;г онтологический грех человека искупается жертвенной смертью Иисуса Христа каждый имеющий в своем сердце веру в Спасителя...
34007. Человек как духовное существо. Проблема смысла жизни, смерти и бессмертия 24 KB
  И эта неудовлетворенность содержит в себе причины творческой деятельности Поэтому призвание задача каждого человека всесторонне развивать все свои способности и по мере возможностей вносить свой личный вклад в историю в прогресс общества его культуры. Смысл жизни общва и челтва в целом. Буддизм: чел живет для того чтобы прервать цепь перерождений и никогда больше не возрождаться. Христво восхождением чел к богу.
34008. Этология Конрада Лоренца 34.5 KB
  Изучая поведение разных животных и человека К.Зонди 18931986 швейцарский ученый развивая и продолжая традиции психоанализа наряду с индивидуальным и коллективным бессознательным выделил понятие родового бессознательного это влияние наследственности и рода предков на судьбу человека. Навязанная судьба которая складывается: а под влиянием генетической наследственности; б под действием генотрофизма развития психики человека под влиянием того или иного предка или родственника от которых может зависеть выбор профессии хобби...
34009. Религия как социокультурный феномен. Понятие Бога в философии и религии 40.5 KB
  Понятие Бога в философии и религии. Философия религии важный раздел философского знания поскольку религия составляет системообразующий элемент различных культур цивилизаций и обществ. Философию религии нельзя также отождествлять с религиозной философией. Философия религии это прежде всего рефлексия над религией как сложным социокультурным феноменом определение ее знания в жизни человека и общества.
34010. Предмет и задачи этики. Основные этические системы 44 KB
  Вся совокупность проблем в той или иной мере посвященных изучению этих вопросов была представлена особой философской теорией получившей название философия морали нравственности или этика. Термин этика происходит от древнегреческого слова ethos этос подразумевавший пространство совместного проживания людей или животных дом звериное логово птичье гнездо и т. Поэтому термин этика также введенный в употребление Аристотелем изначально приобрел двоякую направленность: 1 обозначение совокупности добродетелей правил и норм...