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.

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


 

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

80052. Подорож материками 39.5 KB
  Мета: сформувати уявлення про материки, продовжувати формувати уявлення про глобус, карту півкуль, розвивати вміння працювати з фізичною та контурною картами, вміння працювати з додатковою літературою, розвивати пізнавальні інтереси, виховувати спостережливість, любов до природи.
80053. Охорона природи на Землі 88 KB
  Вчити дітей знаходити красиве в природі. Збагатити знання дітей про природу і заходи щодо її збереження. Вміти зіставляти вчинки людей, аргументувати свою думку, встановлювати зв’язок між елементами довкілля. Формувати у дітей ділову готовність реалізувати ці знання в нестандартній ситуації...
80054. Природна зона мішаних лісів 144.5 KB
  Мета: продовжити формувати уявлення про Україну; розкрити значення вислову мішані ліси; розкрити значення лісів для життя людей; розвивати спостережливість мислення уміння аналізувати і робити висновки; вміння висловлювати свої думки; виховувати бережливе дбайливе ставлення до природи...
80055. Не дай скотитися у прірву… 8.97 MB
  Мета: розкрити негативні сторони самостійного життя поза батьківським домом, сприяти формуванню у випускників відповідального ставлення до свого життя, до життя своїх батьків, допомогти учням знайти відповіді на питання: як нам жити, що робити, як вижити в цьому світі?
80056. Проблема под микроскопом 63.5 KB
  Цели и задачи мероприятия: дать представление учащимся о понятии «проблема»; научить детей выделять и оформлять проблему; познакомить учащихся с различными способами решения личностных проблем; развивать навыки употребления полученных знаний на смоделированных проблемных ситуациях...
80057. Забуті народні свята осіннього циклу 72.5 KB
  Мета. Дослідити забуті народні свята осіннього циклу: Дмитра(8 листопада), Святої П’ятниці(10 листопада), Кузьми й Дем’яна(14 листопада); організувати пошукову роботу стосовно відродження втрачених обрядів, звичаїв, традицій українських ярмарків.
80058. ENGLISH HOLIDAYS 719 KB
  Актуальність проекту: прагматична направленість на результат; цей результат можна побачити осмислити застосувати в реальній практичній діяльності; дозволяє органічно інтегрувати знання учнів з різних сфер навколо рішення однієї проблеми.
80059. Планета на ім’я «Сміття»?.. 69.5 KB
  Мета: привернути увагу учнів побутових відходів; виявити джерела екологічних проблем, як наслідок неадекватних дій людей; продовжити формувати дбайливе відношення до природи; розвивати здібності «мислити глобально, діяти локально».
80060. Бережи здоров’я змолоду 59 KB
  У проекті враховано природні здатності молодшого школяра, вразливість його психіки, допитливість у пізнанні самого себе, схильність до імітації зразків поведінки дорослих, що зумовлює соціальний та особистісний розвиток учня. Важливе місце займає практична діяльність учнів разом з батьками.