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.

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


 

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

30716. Развитие социально-политического кризиса в Европе в начале 1920-х гг 22 KB
  : сильный рост промышленного правительства в США Франции в результате 1 мировой войны они обогатились. Основой промышленного подъема был технический прогресс новые технологии новые отрасли автомобили Увеличение концентрации и централизации капитала усиления мощи корпораций смена промышленности и банков – рост финансового капитала. Рост благотворительности для поддержания социальной стабильности.
30717. ФРГ: переход к новой «восточной политике». Договор с СССР от 12 августа 1970 г 27 KB
  Брандт – с 1969 канцлер ФРГ лидер социалдемократов. Подтверждалось что Западный Берлин не является частью территории ФРГ и устанавливался тройной механизм взаимоотношений между компетентными органами ГДР Западного Берлина и ФРГ по вопросам регулирования транзитных перемещений граждан транспортного телефонного и телеграфного сообщения и пр. Но Западный Берлин имел международные соглашения заключенные ФРГ поэтому ФРГ получила право представлять интересы жителей Западного Берлина в международных организациях по вопросам не...
30718. Причины, особенности и основные последствия мирового экономического кризиса 1929 – 1933 гг 23 KB
  Мировой экономический кризис 19291933 годов носивший название Великой депрессии наиболее сильно затронул такие страны как Великобритания США Франция Канада и Германия. Важным фактором обусловившим всемирный характер великой депрессии стал процесс перемещения экономического центра из Западной Европы в США. Последствиями Великой депрессии стали: ухудшение уровня жизни фермеров и мелких торговцев; уменьшение уровня производства; рост числа безработных; возрастание сторонников фашистских организаций.
30719. Исторический опыт Народных фронтов (Франция, Испания, Чили) 23.5 KB
  Народный фронт представляет собой политический союз который как правило объединяет левые и центральные силы для осуществления противодействия правым силам представителей власти. Основной целью возникновения народных фронтов стала борьба за защиту экономических интересов рабочего класса и противопоставление войне и фашизму. Самый первый народный фронт был образован во Франции в 1935 году который объединил в себе все левосторонние партии.
30720. Общее и особенное в политике британских консерваторов и лейбористов в 1920-е гг 23 KB
  Консервативная партия Великобритании – одна из двух ведущих политических партий страны образовавшаяся в 1867 году на базе партии тори. К 1930му году в Великобритании стала ясной гибель радикального социализма тогда на первый план выдвинулся либерализм который настаивал на прямом вмешательстве государства в экономику и передаче государству целого ряда социальных функций. Внутреннюю политику консерваторов Великобритании 1920 1930х годов можно охарактеризовать как стремление сохранить существующую ранее универсальность и...
30721. Основные этапы первой мировой войны. Факторы поражения германо-австрийского блока 27.5 KB
  В июле 1914 г Германия и Австровенгрия начинают первую мировую войну. Германия хотела сначала вывести из строя Францию чтобы прекратить борьбу на два фронта: Западном и Восточном. 1 этап – вторжение в Бельгию где Германия потерпела поражение: в Восточной Пруссии – Германия воевала с русскими армиями; в Галиции и Польше – где победы достались русским. Германия и АвстроВенгрия были экономически истощены под влиянием революций в России среди военных германии и Австрии усилилась антивоенная агитация народ устал от...
30722. «Новый курс» Результата и его историческое значение 24.5 KB
  Его основная цель состояла в оздоровлении экономики и восстановления доверия граждан к государству. Политика Рузвельта получила название Новый курс который он восстановил государственное регулирование экономики и социальных отношений. Законом об оздоровлении национальной экономики вся промышленность была разделена на 17 групп по отраслям и регулировалась нормативными актами кодексами чести определявшими объем выпуска товаров уровня заработной платы распределение рынков сбыта продолжительность рабочего времени и др....
30723. Эволюция и крах бюрократических режимов в стране ЦЮВЕ 26.5 KB
  было сформировано коалиционное правительство в ГДР. Чехословакия и ГДР несколько условно могут быть отнесены к государствам с довольно высоким уровнем развития Польша Венгрия Хорватия и Словения – страны среднего развития а Болгария Румыния четыре другие республики бывшей Югославии Сербия Черногория Македония Босния и Герцеговина Албания – низкого. По решению парламентов ГДР и ФРГ с 1 июля 1990 г. ГДР прекратила свое существование вместо нее появились пять новых федеральных земель ФРГ.
30724. Изоляционизм США термин использовавшийся с середины 19 в. 25 KB
  Изоляционизм США термин использовавшийся с середины 19 в. для обозначения направления во внешней политике США в основе которого лежит идея невмешательства в европейские дела и вообще в вооруженные конфликты вне американского континента. складывались под влиянием ряда факторов: географическая обособленность Американского континента создание в США ёмкого внутреннего рынка способствовавшего тому что значительная часть буржуазии мало интересовалась заокеанской экспансией расширение за счет др.