9. Бінарне дерево пошуку.

Бінарне дерево забезпечує дуже зручний метод організації даних, у разі використання якого будь-які конкретні дані можна легко знайти або виявити їхню відсутність. Єдиною вимогою є введення для даних деякого лінійного порядку. Цим порядком може бути, наприклад, алфавітний чи числовий порядок. У бінарному дереві пошуку кожній вершині присвоєне значення, яке називають ключем. Ключ – це елемент деякої лінійно впорядкованої множини: будь-які два елементи цієї множини можна порівняти. В алгоритмі побудови бінарного дерева пошуку використовують його рекурсивну властивість, яку описують так. Кожна вершина розбиває дерево на 2 піддерева. Ліве піддерево містить лише ключі, менші від ключа цієї вершини, а праве – ключі, більші від ключа вершини. Ця властивість повторюється рекурсивно для кожної вершини.

Алгоритм додавання об’єктів в дерево:

Крок 1. Почати з кореня: присвоїти кореню перший об’єкт списку як ключ.

Крок 2. Якщо об’єкт < від ключа у вершині, то перейти до лівого сина.

Крок 3. Якщо об’єкт > від ключа у вершині, то перейти до правого сина.

Крок 4. Повторювати кроки 2 та 3 доки не досягнемо вершини, яка не визначена.

Крок 5. Якщо вершина, яка досягнута, не визначена,то визначити (додати) вершину з новим об’єктом як ключем.

Алгоритм пошуку елемента в дереві:

Крок 1. Почати з кореня.

Крок 2. Якщо об’єкт < від ключа у вершині, то перейти до лівого сина.

Крок 3. Якщо об’єкт > від ключа у вершині, то перейти до правого сина.

Крок 4. Якщо об’єкт = ключу у вершині, то об’єкт знайдено. Виконати потрібні дії і вийти.

Крок 5. Повторювати кроки 2, 3, 4 доки не досягнемо вершини, яка не визначена.

Крок 6. Якщо досягнута вершина не визначена, то даний об’єкт не зберігається у дереві. Виконати потрібні дії і вийти.

10. Дерево прийняття рішень.

Кореневі дерева можна використовувати для розв’язування задач прийняття рішень. Для цього використовують дерева прийняття рішень, або дерева рішень. Кожному листку такого дерева поставлено у відповідність рішення зі скінченної множини відомих рішень, а кожній внутрішній вершині v – перевірку умови P(v). Прийняття рішень за допомогою такого дерева полягає в побудові простого шляху від кореня до листка. У процесі побудови шляху виконують перевірку умов у внутрішніх вершинах дерева. Значення умови P(v) у вершині v визначає ребро, яке буде додано в шлях після вершини v. Кінцева вершина побудованого шляху вказує прийняте рішення. У багатьох практичних задачах потрібно приймати рішення відносно досліджуваних об’єктів віднесенням їх до певних класів, тобто наданням цим об’єктам класифікаційних ознак. Якщо ці класифікації наперед відомі, то задачі називають задачами класифікації.

Система прийняття рішень – це інформаційна система вигляду D=(W, A {d}), де d не належить А – атрибут прийняття рішень. Цей атрибут може набувати декількох значень, однак найчастіше використовують значення {0,1} або {Yes, No}. Систему прийняття рішень можна зобразити у таблиці, у якої останній стовпчик позначено атрибутом прийняття рішень. Таку таблиці називають таблицею прийняття рішень.