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.

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


 

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

7322. Робочий час і час відпочинку 205 KB
  Як відомо, ні рабовласницький, ні феодальний устрої не мали законодавчого обмеження робочого часу, оскільки носій робочої сили був разом з іншими знаряддями виробництва об'єктом власності.
7323. Керування пам’яттю в ОС. Сегментна, сторінкова й сегментно-сторінкова організація пам’яті 1.12 MB
  Сегментація памяті дає змогу зображати логічний адресний простір як сукупність незалежних блоків змінної довжини, які називають сегментами. Кожний сегмент звичайно містить дані одного призначення, наприклад в одному може бути стек, в іншому - програмний код і т. д.
7324. География экономического района России. Уральский экономический район 371.5 KB
  География экономического района России. Уральский экономический район Введение Россия представляет собой самый обширный регион всей Евразии и единственную федерацию в рамках СНГ, поэтому региональный анализ ее экономических районов имеет особый смыс...
7325. Система управления электромуфты переключения направления намотки кабеля 180.5 KB
  ВВЕДЕНИЕ Устройство, на ряду со своей основной функцией, способно работать также и в качестве реле аварийной сигнализации. Оно выгодно отличается компактностью, небольшими массой и собственным потреблением электроэнергии. Для автомобилей новых модел...
7326. Кражи и грабежи как преступления против собственности 404 KB
  Кражи и грабежи как преступления против собственности 1. Кража Закон, касающийся кражи и относящихся к ней преступлений таких как грабеж, кража со взломом, различные преступления, включающие обман, шантаж и продажу (передачу) краденного, содержится ...
7327. Информационные технологии управления 468.5 KB
  Информационные технологии управления Информационные технологии и системы, понятие и свойства. Состав и структура экономических информационных систем. Жизненный цикл информационной системы. Классификация автоматизированных инф...
7328. Расчет силового масляного трансформатора 336 KB
  Расчет силового масляного трансформатора. Задание на расчет. Требуется рассчитать конструкцию и параметры силового трансформатора с масляным охлаждением со следующими параметрами: Мощность трансформатора SH = 1000 кВА. Число фаз m = 3. Частота f = 5...
7329. Измеритель активной энергии в однофазной сети на основе микроконтроллера ATMEL 654.5 KB
  Измеритель активной энергии в однофазной сети на основе микроконтроллера ATMEL Разработать измеритель активной энергии в однофазной сети 220 В с токовой нагрузкой 100 А на основе микроконтроллера фирмы ATMEL. Технические требования. В качестве перви...
7330. Исследование сущности и основных аспектов эффективной деятельности риэлторских фирм ООО МЕТР 225 KB
  Основой любой социально-экономической системы является собственность. Переход общества на рыночные основы вызывает ее трансформацию. Собственность от основной государственной преобразуется в многоаспектный комплекс, состоящий из федеральной...