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.

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


 

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

9359. Определить деформирующие характеристики грунта, коэффициент относительной сжимаемости 72.5 KB
  Цель работы:определить деформирующие характеристики грунта, коэффициент относительной сжимаемости m0, модуль линейной деформации Е0. Оборудование: компрессионный прибор одометр, индикаторы часового типа, бумажные фильтры, набор гирь. Методика ...
9360. Прочностные характеристики на срез. Испытания грунта на срез 41 KB
  Цель работы: установить зависимость предельного сопротивления ?пред от величины, сжимающих эффективных давлений Рэф. Определить основные прочностные характеристики: угол внутреннего трения, с - удельное сцепление. Методика испытаний Н...
9361. Мікропроцесорна лабораторія Мікролаб КР580ІК80 1.21 MB
  Мікропроцесорна лабораторія Мікролаб КР580ІК80 Вступ Даний курс призначений для вивчення елементів апаратного і програмного забезпечення систем, побудованих на базі мікропроцесора KP580ІK80. У першому розділі дані загальні принципи побудови пристрої...
9362. Розробка принципової схеми гідро- та пневмоприводів і систем гідро пневмоавтоматики з раціональним вибором робочого середовища 208 KB
  Вступ Курсова робота з дисципліни Гідравліка, гідро- та пневмоприводи є необхідним практичним додатком до теоретичного курсу, а також підготовчим етапом до виконання курсового та дипломного проектування при розробці гідроприводу та пневмориводу мета...
9363. Разработка цифрового измерителя температуры 178.5 KB
  ТЕМА: Разработка цифрового измерителя температуры В качестве цифрового датчика температуры в схеме стенда используется цифровой датчик DS18B20 фирмы DallasSemiconductor (D1), который с помощью однопроводного интерфейса подключен к разряду 7 по...
9364. Минералы и горные породы - строительные материалы природы 101.5 KB
  Минералы и горные породы - строительные материалы природы. Минералы - природные тела, однородные по химическому составу и природным свойствам, образующиеся в глубинах и на поверхности Земли. Известно около 3000 видов минералов. Наиболее распрос...
9366. Технологический процесс ремонта, корпус пневмоцилиндра, дефектоскопия, электролитическое осаждение, механическая обработка, себестоимость, комплект технологической документации 438 KB
  Реферат Объектом разработки является технологический процесс ремонта корпуса пневмоцилиндра. Цель работы - усовершенствовать технологический процесс ремонта заданной детали, произвести необходимые расчеты, составить пояснительную записку, оформить т...
9367. Учет основных средств ООО Транс сервис 632.5 KB
  Введение Развитие различного вида предпринимательства сопровождается возрастанием роли бухгалтерской информации в управлении, контроле и анализе предпринимательской деятельности. Своевременность ее получения, соответствующее качество и достоверность...