Використання дерев

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

КОДИ ХАФФМАНА.Це приклад, коли двійкові дерева використовуються в якості структур даних. Нехай маємо сповіщення, в якому символи незалежні і з’являються з відомими ймовірностями. Наприклад, в сповіщені є символи а, б, в, г, д, які з’являються в сповіщені з ймовірностями 0.12, 0.4, 0.15, 0.08 та 0.25, відповідно. Треба закодувати кожний символ так, щоб його код був префіксом коду усього сповіщення. Таке (префіксне) свойство дозволяє легко декодувати рядок з нулів та одиниць так, що послідовно вилучають префікси (коди символів) із цього рядка. Легко запропонувати такий код: а - 000, б - 001, в - 010, г - 011, д – 100. Для цього кода середня длина дорівнює 3.

А чи можна винайти інший код з меншою середньою довжиною? Дійсно, є код з префікс ним свойством, середня довжина чкого для даного приклада дорівнює 2.15. Спосіб винаходу оптимального префіксного коду називається алгоритмом Хаффмана. В цьому алгоритму спочатку знаходять два символа з найменшими ймовірностями їх появи і заміняють фіктивним символом, ймовірность якого визначається як сума ймовірностей знайдених двох символів (в нашому прикладі це символи а та д). Далі, з тих, що лишилися, знаходять символ з найменшою ймовірністю його появи і додають до фіктивного символа і т.д. На рис. 7. 36 показано етапи створення дерева Хаффмана.

Рис. 7.36. Етапи створення дерева Хаффмена

 

Спочатку вилучають символи а (0.12) та г (0.08), далі – в(0.15), потім - д (0.25), потім - б (0.40). Префіксні коди - це путі на дереві: путь від вузла до лівого сина відповідає 0 в коді, а до правого сина -1. Символи, що кодуються, в дереві Хаффмана розташовані тілько на листях, це забезпечує префіксне свойство кодів. В даному випадку символи а, б, в, г, д отримали відповідні коди: 1111, 0, 110, 1110, 10.

ЧАСТОТНІ СЛОВНИКИ.Дерева використовують для визначення того, які слова в тексті використовувалися і скільки разів. В цьому випадку у вузлі зберігаеться в якості ключа само слово і лічильник кількості його появ.

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

- пошук слова в дереві,

- у разі його відсутності слово додається в новий вузол дерева, з лічильником, що дорівнює 1;

- У випадку, коли слово в дереві знайдено, його лічильник збільшується на 1.