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.

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


 

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

21144. Защита покрытиями 31.5 KB
  Негальванические покрытия. К металлическим покрытиям относятся: вакуумное испарение практически любым металлом и почти на любые подложки толщина слоя зависит от скорости и времени испарения вещества; катодное распыление перенос металла с катода на анод при тлеющем разряде в газах; горячее распыление расплавленный металл распыляется сжатым газом толщина пленки от 30 мкм до нескольких миллиметров которым можно нанести любое металлическое покрытие на поверхность любого материала. К неметаллическим покрытиям относятся лакокрасочные...
21145. Звуки BIOS 141 KB
  ru Дата: 20:13:17 14 11 01 BIOS Beep Sound core list AWARD BIOS Beep Sound Massage 1 short System booting is normally. 2 short CMOS setting error 1 long1 short DRAM ERROR 1 long2 short Display card or monitor connected error 1 long3 short Keyboard Error 1 long9 short ROM Error Long continuous DRAM hasn't inset correctly. Short continuous POWER supply has problem. AMI BIOS 1 short DRAM Flash Error 2 short DRAM ECC Check Error 3 short DRAM Detect Fail 5 short CPU Error 6 short Keyboard...
21146. Виды политических систем в современном мире 49 KB
  Для демократических политических систем характерно наличие государственных органов в центре и на местах, легальное существование на ряду с правящими партиями и оппозиционных...
21147. Методы обеспечения и повышения надежности 26.5 KB
  Общие методы реализуются на стадиях проектирования и производства и осуществляются следующими путями: максимальным упрощением принципиальной схемы с одновременным уменьшением числа элементов с невысокой надежностью; ослаблением влияния внешних воздействий герметизацией амортизацией охлаждением и т. Специальные методы реализуются путем облегчения режима работы элементов схем и конструкции предварительной тренировкой элементов резервированием и др. Облегчение режима работы схемных элементов снижает интенсивность отказов. Для учета нагрузки...
21148. МЕТОДЫ ОБРАБОТКИ ИЗДЕЛИЙ ЭВМ 124 KB
  Для всех методов обработки кроме ультразвуковых производительность не зависит от твердости и вязкости обрабатываемого материала. Электроэрозионные методы обработки Электроэрозионные методы обработки это совокупность электрических химических воздействий на обрабатываемую деталь для придания ей заданной формы и размеров. Основными методами электроэрозионной обработки являются электроискровая и анодномеханическая.
21149. МЕХАНИЧЕСКИЕ ВОЗДЕЙСТВИЯ НА КОНСТРУКЦИИ СВТ 38.5 KB
  Наибольшее разрушающее воздействие на конструкцию СВТ оказывают вибрации. Он в свою очередь приводит к увеличению амплитуды колебаний СВТ. Введение амортизаторов между СВТ и объектом в качестве среды уменьшающей амплитуду передаваемых колебаний и ударов снижает действующие на СВТ механические силы но не уничтожают их полностью.
21150. Основные характеристики МПП общего применения на фольгированном диэлектрике 855.5 KB
  Основные характеристики МПП общего применения на фольгированном диэлектрике Показатель Характеристика Область применения Спецтехника вычислительная техника средства связи Класс точности 1;2; 3 Группа жесткости I IV Рекомендуемые максимальные размеры мм 360 х 420 γ = 033 Материал основания Стеклотекстолит фольгированный например СТФ1 СТФ2 стеклоткань СТП1 Минимальный диаметр отверстия мм Переходное 04 Сквозное 06 Минимальная ширина проводника мм 025 Тип производства Мелкосерийное серийное крупносерийное Методы...
21151. Культура українських земель XIX ст. Національно-культурне відродження 870.53 KB
  У XIX ст. розвиток української культури обумовлювався підпорядкуванням українських земель двом імперіям – Російській та Австро-Угорській. Обидві імперії були багатонаціональними, з титульною (панівною) нацією. І Росія, і Австро-Угорщина проводили колонізаторську політику, підтримували антиукраїнські сили
21152. Поиск и устранение неисправностей в CD-ROM 57.5 KB
  Много неприятностей доставляют и так называемые условные отказы плавающие неисправности когда чтение диска либо внезапно прекращается а потом возобновляется либо производится с ошибками. Конечно многие отказы связаны с дешевыми пиратскими дисками использование которых может нарушить бесперебойную работу устройства. Причем помимо того что информация на таком диске может не читаться использование несбалансированных дисков в высокоскоростных приводах зачастую ведет к разрушению как самого диска он буквально разлетается на мелкие...