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.

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


 

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

28003. Сравнительный анализ функционирования естественных экосистем и агроэкосистем. Устойчивость эко(агроэко)системы: толерантность, уязвимость, гетерогенность агроценозов 5.26 KB
  Экосистемы – исторически сложившееся в биосфере и на той или иной территории открытые но целостные и устойчивые системы живых организмов. Агроэкосистемы – вторичные измененные человеком биогеоценозы основу которых составляют искусственно созданные биотические сообщества объединяемые видами живых организмов. Особенность агросистем в отличии от экосистем их неусточивость то есть к способности саморегуляции.
28004. Формирование биогенной нагрузки в природных аграрных системах. Естественные потери биогенных веществ в земледелии, животноводстве и селитебных территорий 4.24 KB
  Естественные потери биогенных веществ в земледелии животноводстве и селитебных территорий. Интенсивно развивающееся сельское хозяйство – это наиболее активный источник поступления биогенных элементов. Влияние с х как источника поступления биогенных веществ в природные ресурсы возрастает в связи с увеличением распаханности территорий трансформацию угодий мощной техникой развитием процессов химизации на основе минеральных и органических удобрений. Потери биогенных веществ в растениеводстве условно можно разделить на...
28005. Функционирование агроэкосистем в условиях техногенеза 4.85 KB
  Функционирование агроэкосистем в условиях техногенеза. Агроэкосистема АЭС – совокупность биогенных и абиогенных компонентов участков суши преобразованных человеком используемых для производства сельхозпродукции. Основа АгроЭкоСистем – почва с х угодия. Типы АгроЭкоСистем: Пропашное земледелие Многолетнее земледелие Многоурожайное земледелие МезоАЭС крупномасштабная МикроАЭС грядка Суша занимает площадь 149 млрд.
28006. Экологизация сельскохозяйственного производства 4.56 KB
  Природоразрушающий ресурсоемкий тип развития АПК требует пересмотра сложившейся теории и на практике техногенной концепции развития АПК. Главным принципом развития АПК должна стать экологизация с х производства всех мероприятий по развитию с х учет природных особенностей функционирования земельных ресурсов. для изменения приоритетов в распределении ресурсов капитальных вложений в АПК усилить природоохранную роль затрат. Для преодоления негативных тенденций в развитии АПК скорейшего решения...
28007. Экологическая биотехнология. Возможности увеличения производства экологически безопасной продукции на основе биопроизводства 2.52 KB
  Возможности увеличения производства экологически безопасной продукции на основе биопроизводства. Среди новых направлений биотехнологии способствующих получению экологически безопасной продукции следует отметить применение микробиологических удобрений промышленную переработку бытовых отходов индустриальную технологию компостирования отходов животноводства и др. микробиологические удобрения повышают продуктивность растений и кол во растительной продукции. Азотфиксирующие микроорганизмы служат прекрасной основой для...
28008. Экологически безопасные технологии и оптимизация обработки почвы 3.73 KB
  Поэтому нужна разработка таких сельскохозяйственных машин и орудий которые при общей эффективности должны оказывать минимальный вред окружающей среде а именно: Сократить выбросы от с х машин и орудий Уменьшить нагрузку на почву путем изменения конструктивной особенности техники Внедрение двигателей с высоким КПД но низким потреблением топлива.
28009. Экологические аспекты применения сточных вод при орошении. Ценность сточных вод в повышении плодородия почв. Контроль загрязнения почв 12.86 KB
  Ценность сточных вод в повышении плодородия почв. Сточные воды используются для орошения на специальных участках земледельческих полях орошения ЗПО. Под последними понимаются водохозяйственные объекты оборудованные для непрерывного приема определенного количества сточных вод в течение всего года с целью их очистки или доочистки и использования для орошения.
28010. Экологические особенности и значимость биогумуса. Препараты получаемые на основе биогумуса. Экологические аспекты подготовки и применения биогумуса 2.93 KB
  Препараты получаемые на основе биогумуса. Экологические аспекты подготовки и применения биогумуса. Установлена возможность биогумуса связывать радионуклиды находящиеся в почве органических удобрений резко уменьшать поступление тяжелых металлов в растения.
28011. Экологические проблемы мелиорации. Виды и целевое назначение современных мелиораций. Положительные и отрицательные изменения в ОС под влиянием гидротехнических мелиораций 4.85 KB
  К этим мероприятиям относятся: Орошение и обводнение Осушение земель Противоэрозионные мероприятия закрепление оврагов сыпучих песков почво и полезащитное лесонасаждение. Рассоление почв Выравнивание микрорельефа и т. Мелиорация земель призвана способствовать получению высоких и стабильных урожаев повышению плодородия почв рациональному использованию земельных ресурсов. Орошение – способ повышения продуктивности почв важнейшее направление интенсификации с х производства.