Лекція 13: Тема: Поняття двобічного (бінарного) дерева. Збалансоване і незбалансоване дерево. Алгоритм обходу двобічного дерева. Алгоритм пошуку за допомогою бінарного дерева

План:

1. Поняття дерева

2. Бінарні дерева

3. Структура бінарного дерева

4. Способи обходу бінарного дерева

5. Вставка і видалення

У повсякденному житті часто зустрічаються приклади дерев.

Люди часто використовують генеалогічне дерево для зображення структури свого роду; багато термінів, пов'язаних з деревами, узято саме звідси.

Другий приклад - це структура великої організації; використання деревоподібної структури для представлення її "ієрархічної структури" нині широко використовується в багатьох комп'ютерних завданнях.

Деревовидні структури широко використовуються :

• Интернет: Группа новостей, логическая структура DOM[1], индексация Yahoo!,

• Управління інформацією: десяткова класифікація Д’юи

• Управління: ієрархічно організовані структури

• Інформатика: бінарне дерево пошуку Червоно-чорні дерева

• Біологія: филогенетичне дерево

• Бізнес: фінансова піраміда

• Управління проектами: структура декомпозиції робот

• Лінгвістика (синтаксис): дерево структури фрази

Деревовидна структура є одним із способів уявлення ієрархічній структури у графічному вигляді.

Вершину дерева називають його коренем, вузли, у яких відсутні обидва спадкоємці, називаються листям.

• Вузол є "батьком" іншого вузла, якщо він розташований на один крок вище в ієрархії дерева, тобто знаходиться ближчим до кореневого вузла.

• "Діти" ("брат" або "сестра") мають загальний батьківський вузол.

• Вузол, пов'язаний з вузлами, що пролягають нижче, називається "предком" або "попередником".

• Корінь дерева- це вузол, який не має предка. Вузли дерева, які не мають нащадків називаються листям. Решта вузлів (не листя і не корінь) називається вузлами-розгалуженнями. Наступний малюнок 1 ілюструє класичне зображення кореневого дерева засобами теорії графів, де вершини і ребра графа представляють вузли і гілки дерева.

Мал.1.

На цьому малюнку заголовні букви латинського алфавіту позначають вузли, а строкові- гілки кореневого дерева. Конфігурація гілок цього кореневого дерева така, що вузол А є коренем, вузли В З і D- розгалуженнями, а вузли E, F, G, H, і K - листям.

Слід зазначити, що окрім класичного зображення, в області інформаційних технологій застосовуються альтернативні способи представлення кореневих дерев. На наступному малюнку 2 приведені 3 еквівалентних способу представлення початкового кореневого дерева: за допомогою вкладених дужок (а), уступчатого списку (б) і десяткової системи Дьюї (в) відповідно:

Мал. 2. Альтернативні способи представлення кореневого дерева

Поняття бінарного дерева

Важливим різновидом кореневих дерев є клас бінарних дерев, де кожен вузол може мати не більш 2-х нащадків. У рекурсивному варіанті визначення бінарне дерево складається з кореня і 2-х бінарних піддерев: лівого і правого, причому будь-яке з них може бути порожнім. Наступний малюнок 3 ілюструє зображення бінарного дерева з 8-ми вузлів A, B, C, D, E, F, G, H засобами теорії графів.

Мал. 3. Зображення бінарного дерева в теорії графів.

Не дивлячись на ієрархічну структуру бінарні дерева не є підмножиною безлічі дерев. Наприклад на наступному малюнку показані 2 різних бінарних дерева, які еквівалентні як кореневі дерева.

Мал. 4. Відмінність кореневих і бінарних дерев

Наприклад

М ал. 5.

Двійкове дерево - це дерево, у якого кожен вузол має не більше двох спадкоємців. Приклад бінарного дерева приведений на мал.

Найпростіші з дерев вважаються бінарні дерева.

Бінарне (двійкове) дерево (binary tree) - це впорядковане дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: у лівому поддереве містяться тільки ключі, що мають значення, менші, ніж значення даного вузла, а в правому поддереве містяться тільки ключі, що мають значення, більші, ніж значення даного вузла.

Бінарне дерево є рекурсивною структурою, оскільки кожне його поддерево само є бінарним деревом і, отже, кожен його вузол у свою чергу є коренем дерева.

Схемне зображення бінарного дерева:

мал. 6

Бінарне дерево може бути порожньою множиною.

Бінарне дерево може звиродніти в список:

мал. 7

Бінарне дерево - це кінцева безліч елементів, яка або порожньо, або містить один елемент, званий коренем дерева, а решта елементів множини ділиться на дві непересічні підмножини, кожне з яких само є бінарним деревом.

Ці підмножини називаються лівим і правим піддеревами початкового дерева.

Кожен елемент бінарного дерева називається вузлом дерева.

Мал. 8

На мал. 8 показаний загальноприйнятий спосіб зображення бінарного дерева. Це дерево складається з дев'яти вузлів, А-корень дерева. Його ліве поддерево має корінь В, а правое- корінь С. Це зображується двома гілками, витікаючими з А: лівим - до В і правим - до С. Відсутність гілки позначає порожнє поддерево.

Наприклад, ліве поддерево бінарного дерева з коренем З і праве поддерево бінарного дерева з коренем Е обидва порожні. Бінарні дерева з корінням D, G, Н і I мають порожні ліві і праві піддерева.

Мал. 9

На мал. 9 приведені деякі структури, що не є бінарними деревами.

Отже, повторюваний, якщо А - корінь бінарного дерева і В - корінь його лівого або правого поддерева, то говорять, що А - отець В, а В - лівий або правий син А.

Вузол, що не має синів (такі як вузли D, G, Н і I), називається листом.

Рівень вузла в бінарному дереві може бути визначений таким чином. Корінь дерева має рівень 0, і рівень будь-якого іншого вузла дерева має рівень на 1 більше рівня свого отця.

Наприклад, в бінарному дереві на мал. 8 вузол Е- вузол рівня 2, а вузол Н-уровня 3.

Строге бінарне дерево з n листами завжди містить 2n-1 вузол.

Вузол n1 -предок вузла n2 (а n2-потомок n1), якщо n1 - або отець n2, або отець деякого предка n2. Наприклад, в дереві з малюнку А-предок G і Н-потомок З, але Е не є ні предком, ні нащадком С.

Вузол n2-левый нащадок вузла n1, якщо n2 є або лівим сином n1, або нащадком лівого сина n1. Схожим чином може бути визначений правий нащадок.

Два вузли є братами, якщо вони сини одного і того ж отця.

Якщо кожен вузол бінарного дерева, що не є листом, має непорожні праві і ліві піддерева, то дерево називається строго бінарним деревом.

Рівень вузла в бінарному дереві визначається таким чином: рівень кореня завжди рівний нулю, а далі номери рівнів при русі по дереву від кореня збільшуються на 1 по відношенню до свого безпосереднього предка. Глибина бінарного дерева - це максимальний рівень листа дерева, інакше кажучи, довжина щонайдовшого шляху від кореня до листа дерева. Вузли дерева можуть бути пронумеровані по наступній схемі (див. мал. 10)

 

Мал. 10 Схема нумерації вузлів двійкового дерева

К орінь дерева на мал. 11 містить 20, а листя - 4, 16, 37 і 43. Висота дерева - це довжина наидлиннейшего з шляхів від кореня до листя. У нашому прикладі висота дерева рівна 2.