<
  • Главная
Статьи

Робота зі структурами даних в мовах Сі та Python: Частина 6. Двійкові дерева

  1. Серія контенту:
  2. Цей контент є частиною серії: Робота зі структурами даних в мовах Сі та Python
  3. Класифікація бінарних дерев
  4. Малюнок 1. Приклад двійкового дерева
  5. Малюнок 2. Різні реалізації одного і того ж бінарного дерева
  6. обчислення шляхів
  7. Малюнок 3. Приклад розширеного дерева
  8. Лістинг 1. Приклад алгоритму Хаффмана
  9. Малюнок 4. Бінарне дерево, побудоване за алгоритмом Хаффмана
  10. Висота бінарного дерева
  11. Лістинг 2. Визначення висоти дерева - рекурсивна реалізація на мові Сі
  12. «Дзеркальне» відображення бінарного дерева
  13. Лістинг 3. Реверс дерева - рекурсивна реалізація на мові Сі
  14. Пошук вузла в бінарному дереві
  15. Лістинг 4. Пошук вузла в дереві - рекурсивна реалізація на мові Сі
  16. Ширина бінарного дерева
  17. Лістинг 5. Визначення ширини дерева - рекурсивна реалізація на мові Сі
  18. Кількість вузлів в бінарному дереві
  19. Лістинг 6. Обчислення кількості вузлів в дереві - рекурсивна реалізація на мові Сі
  20. Порівняння бінарних дерев
  21. Лістинг 7. Порівняння бінарних дерев - рекурсивна реалізація на мові Сі
  22. висновок
  23. Ресурси для скачування

Робота зі структурами даних в мовах Сі та Python

Серія контенту:

Цей контент є частиною # з серії # статей: Робота зі структурами даних в мовах Сі та Python

https://www.ibm.com/developerworks/ru/library/?series_title_by=**auto**

Слідкуйте за виходом нових статей цієї серії.

Цей контент є частиною серії: Робота зі структурами даних в мовах Сі та Python

Слідкуйте за виходом нових статей цієї серії.

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

Як завжди, крім теоретичних аспектів: класифікації бінарних дерев і стандартних прийомів для маніпулювання ними, в статті будуть приклади практичної реалізації алгоритмів для роботи з бінарними деревами на мовах Сі та Python.

Класифікація бінарних дерев

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

У випадку з лінійним пошуком шуканий елемент порівнюється з кожним елементом списку в ході послідовної ітерації. Швидкість такого пошуку залежить від розміру списку: чим більше список, тим нижче швидкість, тобто швидкість обернено пропорційна розміру списку. Збільшити швидкість такого пошуку можна, якщо попередньо відсортувати список. У цьому випадку вже не буде потрібно продовжувати пошук, коли шуканий елемент ще не буде знайдений, а елементи в списку вже стануть більше шуканого.

Для відсортованого списку існує і більш ефективний алгоритм. На початку пошуку необхідно порівняти дані число з елементом, який знаходиться посередині вже відсортованого списку. Якщо серединний елемент виявляється більше шуканого числа, значить шуканий елемент знаходиться в лівій половині. В іншому випадку - справа. Потім виконується порівняння з числом, яке знаходиться посередині потрібної половини. І так далі до тих пір, поки не буде знайдено шукане число. Даний тип пошуку називається двійковим, і він, очевидно, швидше лінійного. Необхідна кількість поділів списку, що складається з n елементів навпіл, називається логарифмом від n по підставі 2. Двійковий пошук є алгоритмом порядку O (log) за основою 2.

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

Малюнок 1. Приклад двійкового дерева
Робота зі структурами даних в мовах Сі та Python   Серія контенту:   Цей контент є частиною # з серії # статей: Робота зі структурами даних в мовах Сі та Python   https://www

У загальному випадку кожен вузол в дереві може мати необмежену кількість дочірніх вузлів. Відмінність бінарного дерева від інших типів дерев в тому, що кожен вузол в ньому може мати не більше двох дочірніх вузлів. Звичайне двоичное дерево - це структура, що складається з вузлів, кожен з яких містить деяке значення, а також покажчики на ліве і праве піддерева. Один або обидва покажчика на ці піддерева можуть мати значення NULL. Двійкові дерева, як і зв'язкові списки, є рекурсивними структурами.

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

Малюнок 2. Різні реалізації одного і того ж бінарного дерева

Існують такі різновиди бінарних дерев:

  • повне бінарне дерево - кожен вузол, за винятком листя, має по 2 дочірніх вузла;
  • ідеальне бінарне дерево - це повне бінарне дерево, в якому все листя знаходяться на одній висоті;
  • збалансоване бінарне дерево - це бінарне дерево, в якому висота 2-х піддерев для кожного вузла відрізняється не більше ніж на 1. Глибина такого дерева обчислюється як двійковий логарифм log (n), де n - загальне число вузлів;
  • вироджене дерево - дерево, в якому кожен вузол має всього один дочірній вузол, фактично це зв'язний список;
  • бінарне пошукове дерево (BST) - бінарне дерево, в якому для кожного вузла виконується умова: всі вузли в лівому поддереве менше, і всі вузли в правому поддереве більше даного вузла.

обчислення шляхів

Шлях (англ. Path) - це відстань від кореня дерева до будь-якого вузла. У розширеному бінарному дереві кожен шлях закінчується листом. Якщо число листя позначити як S, а число інших вузлів позначити як N, то справедлива формула:

S = N +1

тобто для розширеного дерева число листя на одиницю більше числа НЕлістьев (вузлів, що мають дочірні вузли).

Якщо шлях від кореневого вузла до листа позначити як зовнішній шлях, а шлях від кореневого вузла до НЕліста позначити як внутрішній шлях, тоді сума всіх зовнішніх шляхів для дерева, зображеного на малюнку 3 дорівнює:

E = 3 + 3 + 2 + 3 + 4 + 4 + 3 + 3 = 25,

а сума внутрішніх шляхів буде дорівнює:

I = 2 + 1 + 0 + 2 + 3 + 1 + 2 = 11.

і тоді буде справедлива формула:

E = I + 2n

де n - число внутрішніх вузлів (НЕлістьев).

Малюнок 3. Приклад розширеного дерева

Припустимо, є наступний набір листя:

2,3,5,7,11,13,17,19,23,29,31,37,41

Тоді можна сформулювати наступні завдання:

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

Давид Хаффман (David Huffman) запропонував алгоритм для вирішення цієї проблеми, в якому на кожному кроці вибираються і складаються два найменших листа, як показано в лістингу 1, що призводить до дерева, зображеного на малюнку 4.

Лістинг 1. Приклад алгоритму Хаффмана

2 3 5 7 11 13 17 19 23 29 31 37 41 5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 42 53 65 37 41 42 53 65 78 95 65 78 95 143 238

Малюнок 4. Бінарне дерево, побудоване за алгоритмом Хаффмана

коди Хаффмана

Коди Хаффмана - це алгоритм, який використовується для стиснення даних. Нехай є якесь вихідне текстове повідомлення, що складається з 5 символів: a, b, c, d, e, і кожен символ має свою власну частоту:

  • a зустрічається 12 разів;
  • b - 4 рази;
  • c - 15 разів;
  • d - 8 разів;
  • e - 25 разів.

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

символ ймовірність код №1 код №2 a 0.12 000 000 b 0.40 001 11 c 0.15 010 01 d 0.08 011 001 e 0.25 100 10

Якщо зашифрувати повідомлення bcd за допомогою коду №1, то вийде - 001010011. За допомогою коду №2 можна робити те ж саме, але отримала рядок буде коротше - 1101001.

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

У першому варіанті на кожен символ відводилося по 3 символу, а в другому варіанті - вже 2.2, але можна зробити ще коротше і отримати коефіцієнт, що дорівнює 2.15. Це робиться за допомогою алгоритму Хаффмана, в якому беруться 2 символи, які мають найменшу частоту, і об'єднуються, як два дочірніх вузла.

Алгоритм для рядка, що складається з 5 символів, реалізується в такий спосіб. На першому кроці об'єднуються два символу - a і d, як такі, що найменшу частоту. На другому в якості батька додається символ c. На третьому кроці додається символ e, і в кінці - символ b. В результаті виходить наступний код:

  • b - 0;
  • e - 10;
  • c - 110;
  • a - 1111;
  • d - 1110.

Висота бінарного дерева

Для визначення висоти дерева потрібно пройти від кореня спочатку по лівому Піддерево, потім по правому, порівняти ці дві висоти і вибрати максимальне значення. І не забути до одержали значенням додати одиницю (кореневої елемент). У лістингу 2 наведена рекурсивна функція для виконання цього завдання.

Лістинг 2. Визначення висоти дерева - рекурсивна реалізація на мові Сі

int height (struct node * p) {struct node * temp = p; int h1 = 0, h2 = 0; if (p == NULL) return (0); if (p-> left) {h1 = height (p-> left);} if (p-> right) {h2 = height (p-> right);} return (max (h1, h2) +1); }

«Дзеркальне» відображення бінарного дерева

Коли два дерева є дзеркальним відображенням один одного, то йдеться, що вони симетричні. Для отримання «дзеркальної» копії дерева використовується алгоритм, наведений у лістингу 3. Спочатку виконується перевірка на наявність у кореня дерева дочірніх вузлів, і якщо ці вузли є, то вони міняються місцями. Потім ці ж дії рекурсивно повторюються для лівого і правого дочірніх вузлів. Якщо існує тільки один дочірній вузол, тоді можна переходити на один рівень нижче по дереву і продовжувати.

Лістинг 3. Реверс дерева - рекурсивна реалізація на мові Сі

void reverse (struct tree * p) {struct tree * temp; if (p) {if (p-> left && p-> right) {temp = p-> left; p-> left = p-> right; p-> right = temp; reverse (p-> left); reverse (p-> right); } Else if (p-> left &&! P-> right) reverse (p-> left); else if (! p-> left && p-> right) reverse (p-> right); }}

Пошук вузла в бінарному дереві

Для пошуку вузла в бінарному дереві за що містяться в ньому значень можна використовувати функцію lookup, наведену в лістингу 4:

Лістинг 4. Пошук вузла в дереві - рекурсивна реалізація на мові Сі

int lookup (struct node * node, int target) {if (node ​​== NULL) {return (0); } Else {if (target == node-> data) return (1); else {if (target <node-> data) return (lookup (node-> left, target)); else return (lookup (node-> right, target)); }}}

Ширина бінарного дерева

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

Лістинг 5. Визначення ширини дерева - рекурсивна реалізація на мові Сі

int getMaxWidth (struct node * root) {int maxWdth = 0; int i; int width = 0; int h = height (root); for (i = 1; i <h; i ++) {width = getWidth (root, i); if (width> maxWdth) maxWdth = width; } Return maxWdth; } Int getWidth (struct node * root, int level) {if (! Root) return 0; if (level == 1) return 1; else if (level> 1) return getWidth (root-> left, level-1) + getWidth (root-> right, level-1); getWidth (root-> right, level-1); }

Кількість вузлів в бінарному дереві

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

Лістинг 6. Обчислення кількості вузлів в дереві - рекурсивна реалізація на мові Сі

int size (struct node * node) {if (node ​​== NULL) {return (0); } Else {return (size (node-> left) + 1 + size (node-> right)); }}

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

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

Лістинг 7. Порівняння бінарних дерев - рекурсивна реалізація на мові Сі

int sameTree (struct node * a, struct node * b) {if (a == NULL && b == NULL) return (true); else if (a! = NULL && b! = NULL) {return (a-> data == b-> data && sameTree (a-> left, b-> left) && sameTree (a-> right, b-> right)); } Else return (false); }

висновок

До статті приєднаний файл sources.zip , В якому знаходяться два файли вихідного коду: tree_operations.c і tree_operations.py. У першому файлі міститься повноцінна програма на мові Сі, що використовує функції, розроблені в цій статті, для виконання операцій над бінарним деревом. У другому файлі наведено сценарій на мові Python, в якому реалізовані подібні алгоритми для роботи з бінарними деревами. Реалізація на Python ближче за стилем до об'єктно-орієнтованого програмування, так як в ній використовуються класи для оголошення самого дерева і входять в нього вузлів.

У даній статті була виконана класифікація бінарних дерев і розглянуті алгоритми для виконання найважливіших операцій: визначення висоти і ширини дерева, відображення дерева і пошук в ньому певного елемента. Також було розглянуто алгоритм Хаффмана, який може використовуватися для побудови розширених дерев і, як наслідок, для кодування інформації.

Ресурси для скачування

Схожі теми

  • Робота зі структурами даних в мовах Сі та Python. Частина 1 .
  • Робота зі структурами даних в мовах Сі та Python. Частина 2 .
  • Робота зі структурами даних в мовах Сі та Python. частина 3 .
  • Робота зі структурами даних в мовах Сі та Python. частина 4 .
  • Робота зі структурами даних в мовах Сі та Python. частина 5 .
  • Робота зі структурами даних в мовах Сі та Python. частина 6 .

Підпишіть мене на повідомлення до коментарів

Com/developerworks/ru/library/?


Новости
  • Виртуальный хостинг

    Виртуальный хостинг. Возможности сервера распределяются в равной мере между всеми... 
    Читать полностью

  • Редизайн сайта

    Редизайн сайта – это полное либо частичное обновление дизайна существующего сайта.... 
    Читать полностью

  • Консалтинг, услуги контент-менеджера

    Сопровождение любых интернет ресурсов;- Знание HTML и CSS- Поиск и обновление контента;-... 
    Читать полностью

  • Трафик из соцсетей

    Сравнительно дешевый способ по сравнению с поисковым и контекстным видами раскрутки... 
    Читать полностью

  • Поисковая оптимизация

    Поисковая оптимизация (англ. search engine optimization, SEO) — поднятие позиций сайта в результатах... 
    Читать полностью