Скільки висячих вершин у дереві

0 Comments

Алгоритми і структури даних

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

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

Опис алгоритмів

Опис структури даних
  • набір комірок, кожна з яких містить елемент списку (дані) і покажчики на ліве і праве піддерево;
  • комірка (корінь), яка містить покажчик на перший елемент списку.

1. Побудова ідеально збалансованого дерева

Ідея

Взяти одну вершину як корінь і побудувати тим самим способом спочатку ліве піддерево з n1=n / 2 вершинами (n — кількість вершин у початковому дереві), а потім праве піддерево з n2=n—n1—1

Псевдокод функції TreeBalans(кількість_вершин)

якщо кількість_вершин == 0
то вузол = NULL
інакше
n1=n/2
вузол.дані = чергове число
ліве = TreeBalans (n1)
праве = TreeBalans (n — n1 — 1)
>
повернути вузол

2.Обходи дерева

Ідея

Процес обходу розбивається на три частини: відвідання кореня, обхід лівого піддерева та обхід правого піддерева. Різні обходи відрізняються порядком виконання цих кроків.

Псевдокод

Лівий_обхід (корінь)

відвідати корінь
якщо корінь.ліве != NULL, то Лівий_обхід (корінь.ліве)
якщо корінь.праве != NULL, то Лівий_обхід (корінь.праве)
>

Симетричний_обхід (корінь)

якщо корінь.ліве != NULL, то Симетричний_обхід (корінь.ліве)
відвідати корінь
якщо корінь.праве != NULL, то Симетричний_обхід (корінь.праве)
>

Правий_обхід (корінь)

якщо корінь.ліве != NULL, то Правий_обхід (корінь.ліве)
якщо корінь.праве != NULL, то Правий_обхід (корінь.праве)
відвідати корінь
>

3. Пошук із включенням у дереві пошуку

Ідея

Порівняти шуканий елемент з коренем, якщо він менший значення, то перейти до лівого піддерева, інакше перейти до правого піддерева. Процес припиняється, коли відповідне піддерево є порожнім.

Псевдокод процедури Пошук (ключ, корінь)

якщо корінь = NULL
то створити нову термінальну вершину зі значенням ключ
інакше
якщо ключ < корінь.дані
то Пошук ( ключ , корінь.ліве )
інакше Пошук ( ключ , корінь.праве )

Завдання для виконання

Постановка задачі

  • автоматичну генерацію послідовності чисел як майбутніх вершин дерева
  • побудову дерева із зазначеними властивостями;
  • виведення дерева на екран;
  • виконання вказаних викладачем дій з деревом.

Технічні умови

Хід роботи

  1. Скласти програму BalanceTree.cpp для побудови і виведення на екран ідеально збалансованого дерева.
  2. Виконати програму в покроковому режимі для 7 значень
  3. Здійснити вказаний викладачем обхід побудованого дерева.
  4. Скласти програму SearchTree.cpp для побудови і виведення на екран дерева пошуку.
  5. Виконати в покроковому режимі вказану викладачем процедуру роботи з деревом пошуку.

Запитання для самоконтролю

  1. Яка структура називається двійковим деревом?
  2. Які властивості має ідеально збалансоване дерево?
  3. Поясніть, у чому полягає обхід дерева. У чому відмінність різних обходів дерева.
  4. Яке дерево називається деревом пошуку?
  5. Як здійснюється пошук елемента у дереві пошуку із включенням?
  • Головна
  • 1. Оцінка ефективності алгоритмів
  • 2. Пошукові алгоритми
  • 3. Квадратичні алгоритми сортування
  • 4. Сортування Шелла
  • 5. «Швидке» сортування
  • 6. Стеки й черги як структури даних
  • 7. Лінійні списки як структури даних
  • 8-9. Дерева і алгоритми їх обробки
  • 10-11. Графи і алгоритми їх обробки
  • 12-13 Хеш-таблиці й алгоритми їх обробки

10.4: Бінарні дерева

– це вкорінене дерево, піддерева якого розміщуються у певному порядку і самі по собі упорядковані вкорінені дерева. Порожнє дерево та одна вершина без нащадків (без піддерев) є впорядкованими вкоріненими деревами.

Приклад \(\PageIndex<1>\) : Distinct Ordered Rooted Trees Дерева на малюнку \(\PageIndex<1>\) – це однакові вкорінені дерева, з коренем 1, але як упорядковані дерева, вони різні. Малюнок \(\PageIndex<1>\) : Два різних впорядкованих вкорінених

Якщо дерево, що вкорінюється, \(v\) має \(p\) піддерева, ми б називали їх першим, другим. \(p^

\) піддеревами. Існує тонка різниця між певними впорядкованими деревами та бінарними деревами, які ми визначаємо далі.

  1. Дерево, що складається без вершин (порожнє дерево), є двійковим деревом
  2. Вершина разом з двома піддеревами, які є бінарними деревами, є двійковим деревом. Піддерева називаються лівим і правим піддеревами бінарного дерева.

Різниця між бінарними деревами та впорядкованими деревами полягає в тому, що кожна вершина бінарного дерева має рівно два піддерева (одне або обидва з яких можуть бути порожніми), тоді як вершина впорядкованого дерева може мати будь-яку кількість піддерев. Але є ще одна суттєва відмінність між двома типами конструкцій. Два дерева на малюнку \(\PageIndex\) будуть вважатися однаковими, як впорядковані дерева. Однак це різні бінарні дерева. Дерево (a) має порожнє праве піддерево, а Дерево (b) має порожнє ліве піддерево.

Малюнок \(\PageIndex\) : Два різних бінарних дерева

Список \(\PageIndex\) : Terminology and General Facts about Binary Trees

  1. Вершина бінарного дерева з двома порожніми піддеревами називається . Всі інші вершини називаються внутрішніми вершинами.
  2. Кількість листків у двійковому дереві може варіюватися від однієї до приблизно половини кількості вершин у дереві (див. \(\PageIndex\) Вправа цього розділу).
  3. Максимальна кількість вершин на рівні \(k\) двійкового дерева дорівнює \(2^k\) , \(k\geq 0\) (див. \(\PageIndex\) Вправа цього розділу).
  4. — це дерево, для якого кожна вершина має або нуль, або два порожні піддерева. Іншими словами, кожна вершина має або два, або нульові дочірні елементи. \(\PageIndex\) Див. Вправа цього розділу для загального факту про повні бінарні дерева.

Траверси бінарних дерев

Обхід бінарного дерева складається з відвідування кожної вершини дерева в певному встановленому порядку. На відміну від траверсалів графа, послідовні вершини, які відвідуються, не завжди пов’язані з ребром. Найбільш поширені бінарні траверси дерева диференціюються за порядком відвідування кореня і його піддерев. Три траверсалі найкраще описані рекурсивно і є:

Визначення \(\PageIndex\) : Preorder Traversal

  1. Відвідайте корінь дерева.
  2. Попереднє замовлення обхід лівого піддерева.
  3. Попереднє замовлення обходу правого піддерева.

Визначення \(\PageIndex\) : Inorder Traversal

  1. Для того, щоб пройти ліве піддерево.
  2. Відвідайте корінь дерева.
  3. Для того, щоб обходити правильне піддерево.

Визначення \(\PageIndex\) : Postorder Traversal

  1. Пісордер обходить ліве піддерево.
  2. Пісордер обхід правого піддерева.
  3. Відвідайте корінь дерева.

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

Приклад \(\PageIndex\) : Traversal Examples

Для дерева на малюнку порядками \(\PageIndex\) , у яких відвідуються вершини, є:

  • A-B-D-E-C-F-G, для обходу попереднього замовлення.
  • D-B-E-A-F-C-G, для обходу в порядку.
  • D-E-B-F-G-C-A, для обходу післязамовлення.

Двійкове дерево сортування. Враховуючи колекцію цілих чисел (або інших об’єктів, які можна впорядкувати), одним з методів сортування є двійкове дерево сортування. Якщо цілі числа, ми спочатку \(a_1\text\) \(a_2, \ldots \text\) \(a_n\text\) \(n\geq 1\text\) виконуємо наступний алгоритм, який створює двійкове дерево:

Алгоритм \(\PageIndex\) : Binary Sort Tree Creation

  1. \(a_1\) Вставте в корінь дерева.
  2. Для k: = 2 до n// \(a_k\) вставити в дерево
    1. р = \(a_1\)
    2. вставлено = брехня
    3. while not (вставлено):
      \(\quad \) якщо \(a_k < r\text\)
      \(\quad \quad \quad \) якщо \(r\) є лівий дочірній:
      \(\quad \quad \quad \quad\) r = лівий дочірній з \(r\)
      \(\quad \quad \quad\) else:
      \(\quad \quad \quad \quad\) зробити \(a_k\) ліву дитину з \(r\)
      \(\quad \quad \quad \quad\) вставлено = true
      \(\quad \quad\) else:
      \(\quad \quad \quad \) якщо \(r\) має право дочірнього:
      \(\quad \quad \quad \quad\) r = права дочірня з \(r\)
      \(\quad \quad \quad\) else:
      \(\quad \quad \quad \quad\) зробити \(a_k\) правильну дочірню \(r\)
      \(\quad \quad \quad \quad\) вставлену = true

    Якщо цілі числа, які потрібно сортувати, складають 25, 17, 9, 20, 33, 13 і 30, то дерево, яке створюється, є тим, що на малюнку \(\PageIndex\) . Обхід цього дерева в порядку 9, 13, 17, 20, 25, 30, 33, цілі числа у порядку зростання. Загалом, обхід дерева в порядку, який побудований в алгоритмі вище, дасть відсортований список. Попереднє замовлення і післязамовлення обходи дерева тут не мають ніякого значення.

    Малюнок \(\PageIndex\) : Двійкове дерево сортування

    Дерева виразів

    Зручним способом візуалізації алгебраїчного виразу є його дерево виразів. Розглянемо вираз

    \ begin X = a*b – с/д + е.\ end

    Оскільки прийнято ставити пріоритет на множення/ділення, \(X\) оцінюється як \(((a*b) -(c/d)) + e\text<.>\) послідовне множення/ділення або додавання/віднімання оцінюються зліва направо. Ми можемо проаналізувати \(X\) далі, зазначивши, що це сума двох простіших виразів \((a*b) – (c/d)\) і \(e\text<.>\) Перший з цих виразів може бути розбитий далі на різницю виразів \(a*b\) і \(c/d\text<.>\) Коли ми розкладаємо будь-який вираз в дерево \((\textrm)\textrm (\textrm)\text\) виразів цього виразу є двійковим деревом, корінь якого містить операцію, а ліве та праве піддерева яких є деревами лівого та правого виразів відповідно. Крім того, проста змінна або число має дерево виразів, яке є єдиною вершиною, що містить змінну або число. Еволюція дерева виразів для вираження \(X\) відображається на рисунку \(\PageIndex\) .

    Малюнок \(\PageIndex\) : Побудова дерева виразів

    Приклад \(\PageIndex\) : Some Expression Trees

    1. Якщо ми маємо намір застосувати операції додавання та віднімання \(X\) спочатку, ми будемо укладати в дужки вираз до дерева \(a*(b – c)/(d + e)\text\) його виразів з’являється на малюнку \(\PageIndex\) (a).
    2. Дерева виразів для \(a^2-b^2\) та для \((a + b)*(a – b)\) відображаються на малюнку \(\PageIndex\) (b) та рисунку \(\PageIndex\) (c).

    Три обходи дерева операцій є важливими. Двійкову операцію, застосовану до пари чисел, можна записати трьома способами. Одним з них є знайома форма інфікс, наприклад, \(a + b\) для суми \(a\) і \(b\text<.>\) інша форма – префікс, в якому пишеться \(+a b\text<.>\) та ж сума. Кінцева форма – постфікс, в якій пишеться сума \(a b+\text<.>\) Алгебраїчні вирази, що включають чотири стандартні арифметичні операції \((+,-,*, \text /)\) у префіксній та постфіксній формі визначаються наступним чином:

    Список \(\PageIndex\) : Prefix and Postfix Forms of an Algebraic Expression

    Префікс

    1. Змінна або число – це вираз префікса
    2. Будь-яка операція, за якою слідує пара префіксних виразів, є виразом префікса.

    Постфікс

    1. Змінна або число – це постфіксний вираз
    2. Будь-яка пара постфіксних виразів, за якими слідує операція, є постфіксним виразом.

    Зв’язок між траверсалами дерева виразів і цими формами простий:

    1. Обхід перед порядком дерева виразів призведе до отримання префіксної форми виразу.
    2. Обхід післязамовлення дерева виразів призведе до постфіксної форми виразу.
    3. Обхід у порядку дерева операцій, загалом, не дасть належної інфіксної форми виразу. Якщо для виразу потрібні дужки у формі інфіксів, обхід у порядку його дерева виразів призводить до видалення дужок.

    Приклад \(\PageIndex\) : Traversing an Expression Tree

    Обхід попереднього порядку дерева на малюнку \(\PageIndex\) – це \(+-*ab/cd e\text\) префіксна версія виразу \(X\text<.>\) Обхід післязамовлення \(ab*cd/-e+\text<.>\) Зауважте, що оскільки початкова форма не \(X\) потрібна дужок, обхід непорядку \(a*b-c/d+e\text\) є правильною версією інфіксів.

    Підрахунок бінарних дерев

    Закриваємо цей розділ формулою для кількості різних двійкових дерев з \(n\) вершинами. Формула виведена за допомогою генеруючих функцій. Хоча повні деталі виходять за рамки цього тексту, ми надамо огляд деривації, щоб проілюструвати, як генеруючі функції використовуються в просунутій комбінаториці.

    \(B(n)\) Дозволяти число різних двійкових дерев розміру \(n\) ( \(n\) вершин), \(n \geq 0\text<.>\) За нашим визначенням двійкового дерева, \(B(0) = 1\text<.>\) Тепер розглянемо будь-яке додатне ціле \(n + 1\text\) \(n \geq 0\text<.>\) двійкове дерево розміром \(n + 1\) має два піддерева, розміри яких складаються \(n\text<.>\) до можливості можна розбити на \(n + 1\) випадки:

    Випадок 0: ліве піддерево має розмір 0; праве піддерево має розмір \(n\text<.>\)

    Випадок 1: Ліве піддерево має розмір 1; праве піддерево має розмір \(n – 1\text<.>\)

    \(\quad \quad \) \(\vdots\)

    Піддерево Case \(k\text\) Left має розмір \(k\text\) праворуч піддерево має розмір \(n – k\text<.>\)

    \(\quad \quad \) \(\vdots\)

    Піддерево \(n\text\) регістру Left має розмір \(n\text\) правого піддерева має розмір 0.

    У загальному випадку \(k\text\) ми можемо порахувати кількість можливостей, множивши кількість способів заповнення лівого піддерева \(B(k)\text\) на кількість способів заповнення правого піддерева. \(B(n-k)\text<.>\) Оскільки сума цих добутків дорівнює, \(B(n + 1)\text\) ми отримуємо рекуррентне відношення для \(n\geq 0\text\)

    \ begin \ почати B (n+1) &= B (0) B (n) + B (1) B (n-1) +\ cdots + B (n) B (0)\ &=\ sum_ ^n B (k) B (k) B (n-k)\ кінець \ кінець

    Тепер візьмемо генеруючу функцію обох сторін цього рекуррентного відношення:

    \[\label\sum\limits_^\infty B(n+1)z^n=\sum\limits_^\infty\left(\sum\limits_^n B(k)B(n-k)\right)z^n\]

    Нагадаємо, що \(G(B\uparrow;z) =\frac=\frac\) якщо ми скорочуємо \(G(B; z)\) до \(G\text\) ми отримаємо

    \ begin \ розрив = G^2\ Стрілка вправо z G^2- G + 1 = 0\ кінець

    За допомогою квадратного рівняння знаходимо два розв’язки:

    Розрив у нашому виведенні відбувається тут, оскільки ми не припускаємо знання обчислення. Якщо ми розширимо \(G_1\) як розширений силовий ряд, ми знайдемо

    Коефіцієнти після першого є негативними і є сингулярність на 0 через \(\frac\) термін. Однак якщо ми зробимо те ж саме з \(G_2\) ми отримаємо

    Подальший аналіз призводить до виразу замкнутої форми \(B(n)\text\) , для якого

    \ begin B (n) =\ frac \ лівий (\ begin 2n\\ n\\ end \ праворуч)\ кінець

    Цю послідовність чисел часто називають . Для отримання додаткової інформації про каталонських чисел див. запис A000108 в он-лайн енциклопедії цілочисельних послідовностей.

    Примітка SageMath – Серія живлення

    Може бути цікаво відзначити, як розширені силові ряди розширень \(G_1\) і \(G_2\) визначаються за допомогою Sage. У Sage людина має можливість бути дуже конкретним щодо того, як алгебраїчні вирази слід інтерпретувати, вказавши основне кільце. Це може зробити роботу з різними алгебраїчними виразами трохи більш заплутаною для початківця. Ось як отримати розширення Лорана для \(G_1\) вище.

    R.=PowerSeriesRing(ZZ,'z') G1=(1+sqrt(1-4*z))/(2*z) G1

    Перший вираз Sage вище оголошує структуру, яка називається , що містить ряди степенів. Ми не використовуємо всю цю структуру, просто конкретний елемент, G1 . Так що важлива річ про цей перший вхід є те, що він встановлює z як змінна, пов’язана з владою ряд над цілими числами. Коли другий вираз визначає значення G1 через z , воно автоматично перетворюється в ряди степенів.

    Розширення \(G_2\) використовує ідентичний код, а його коефіцієнти є значеннями \(B(n)\text<.>\)

    У розділі 16 ми представимо кільця і зможемо додатково скористатися можливостями Sage у цій галузі.

    Вправи

    Намалюйте дерева виразів для наступних виразів:

    1. \(\displaystyle a(b + c)\)
    2. \(\displaystyle a b + c\)
    3. \(\displaystyle a b + a c\)
    4. \(\displaystyle b b – 4 a c\)
    5. \(\displaystyle \left(\left(a_3 x + a_2\right)x +a_1\right)x + a_0\)

    Намалюйте дерева виразів для

    Випишіть попереднє замовлення, inorder та postorder обходи дерев у вправі \(\PageIndex\) вище.

    Відповідь

    \ begin \ begin &\ text &\ текст \\ текст \\ (а) &\ cdot a + b\ cdot b+c & a\ cdot\\ (b) & +\ cdot a b\ cdot +\\ (c) & +\ cdot a b\ cdot a c & a\ cdot b+a\ cdot c\ cdot a\ cdot a\ cdot +\ \ end \ end

    Перевірте формулу, \(B(n)\text\) \(0 \leq n \leq 3\) намалювавши всі двійкові дерева з трьома або меншими вершинами.

    1. Намалюйте бінарне дерево з сімома вершинами і тільки одним листом.
    2. Намалюйте бінарне дерево з сімома вершинами і якомога більшою кількістю листя.

    Додайте сюди тексти. Не видаляйте цей текст спочатку.

    Доведіть, що максимальна кількість вершин на рівні \(k\) двійкового дерева є \(2^k\) і що дерево з що багато вершин на рівні \(k\) повинні мати \(2^-1\) вершини.

    Доведіть, що якщо \(T\) є повним двійковим деревом, то кількість листків на \(T\) один більше, ніж кількість внутрішніх вершин (non-leaves).

    Відповідь

    Основа: Двійкове дерево, що складається з однієї вершини, яка є листом, задовольняє рівнянню \(\text=\text< internal vertices >+1\)

    Уявіть собі, як побудувати повне двійкове дерево, починаючи з однієї вершини. Продовжуючи додавати листя попарно, щоб дерево залишалося повним, ми можемо побудувати будь-яке повне двійкове дерево. Наше стартове дерево задовольняє умові, що кількість листків на одну більше, ніж кількість внутрішніх вершин. Додавши пару листків до повного двійкового дерева, старий лист стає внутрішньою вершиною, збільшуючи кількість внутрішніх вершин на одиницю. Хоча ми втрачаємо лист, два доданих листя створюють чистий приріст одного листа. Тому зберігається бажана рівність.