Реалізація бінарного дерева пошуку
Опубликованно 28.07.2018 02:03
Бінарне дерево пошуку — структуризированная база даних, що містить вузли, два посилання на інші сайти, праворуч і ліворуч. Вузли — це об\'єкт класу, що має дані, а NULL — знак, що позначає кінець дерева.
Його часто позначають як BST, що володіє спеціальним властивістю: вузли більше кореня розташовуються праворуч від нього, а менші — зліва. Загальна теорія та термінологія
У бінарного дерева пошуку кожний вузол, виключаючи корінь, пов\'язаний спрямованих на ребром від одного вузла до іншого, який називають батьківським. Кожен з них може бути підключений до довільного числа вузлів, називаються дочірніми. Вузли без "дітей" називаються листям (зовнішні вузли). Елементи, які не є листям, називаються внутрішніми. Вузли з одним і тим же батьком — це брати і сестри. Самий верхній вузол називається коренем. У BST призначають елемент кожному вузлу і переконуються, що для них виконано спеціальне властивість.
Термінології дерева: Глибина вузла - число ребер, певне від кореня до нього. Висота вузла — число ребер, певне від нього до самого глибокого листка. Висота дерева — визначається висотою кореня. Бінарне дерево пошуку — спеціальна конструкція, вона забезпечує найкраще співвідношення висоти і кількості вузлів. Висота h з N вузлами не більше O (log N).
Можна це легко довести, підрахувавши вузли на кожному рівні, починаючи з кореня, вважаючи, що він містить найбільшу кількість з них: n = 1 + 2 + 4 + ... + 2 h-1 + 2 h = 2 h + 1 - 1 Вирішуючи це по h, отримаємо h = O (log n).
Переваги дерева: Відображають структурні відносини даних. Використовуються для подання ієрархій. Забезпечують ефективну установку і пошук. Дерева — дуже гнучкі дані, що дозволяють переміщати піддерева з мінімальними зусиллями. Метод пошуку
У загальному випадку, щоб визначити, чи є це значення в BST, починають бінарне дерево пошуку з його кореня і визначають, чи відповідає воно вимогам: перебувати в корені; перебувати в лівому поддереве root; у правому поддереве root.
Якщо ні один базовий регістр не виконується, рекурсивний пошук виконується у відповідному поддереве. Насправді є два базових варіанти: Дерево порожнє — return false. Значення знаходиться в кореневому сайті — return true.
Потрібно звернути увагу, що бінарне дерево пошуку c розвиненою схемою починає пошук завжди по шляху від кореня до листка. У гіршому разі, він проходить весь шлях до листу. Тому найгірший час пропорційно довжині самого довгого шляху від кореня до листка, що є висотою дерева. Загалом, це коли треба знати, скільки часу потрібно для пошуку в якості функції кількості значень, що зберігаються в дереві.
Іншими словами, існує зв\'язок між кількістю вузлів у BST і висотою дерева, що залежить від його форми«. В гіршому випадку вузли володіють тільки одним дочірнім елементом, а збалансоване бінарне дерево пошуку по суті є зв\'язаним списком. Наприклад:
50
/
10
15
30
/
20
Це дерево має 5 вузлів і висоту = 5. Для пошуку значень у діапазоні 16-19 та 21-29 буде потрібно наступний шлях від кореня до листка (вузол, що містить значення 20), тобто буде потрібно час, пропорційне кількості сайтів. У кращому випадку всі вони мають 2-х дітей, а листя розташовані на одній глибині.
Це бінарне дерево пошуку має 7 вузлів і висоту = 3. У загальному випадку дерево, подібне до цього (повне дерево), матиме висоту приблизно log 2 (N), де N - кількість вузлів у дереві. Значення log 2 (N) — це кількість разів (2), коли можна розділити N, перш ніж буде досягнуто нуль.
Підводячи підсумок: найгірший час, необхідний для пошуку BST, дорівнює O (висота дерева). В гіршому випадку «лінійне» дерево - це O (N), де N - кількість вузлів у дереві. У кращому випадку «повне» дерево - це O (log N). Двійкова вставка BST
Задаючись питанням, де має бути розташований новий вузол в BST, потрібно розуміти логіку, він повинен бути поміщений туди, де знайде його користувач. Крім того, потрібно запам\'ятати правила: Дублікати не допускаються, спроба вставити дублююче значення викличе виключення. Метод public insert використовує допоміжний рекурсивний метод «помічник» для фактичної вставки. Сайт, що містить нове значення, завжди вставляється як лист в BST. Відкритий метод insert повертає void, але допоміжний метод повертає BSTnode. Він робить це, щоб обробляти випадок, коли вузол, переданий йому, дорівнює нулю.
У загальному випадку допоміжний метод вказує на те, що якщо вихідне бінарне дерево пошуку пусте, результатом є дерево з одним вузлом. В іншому випадку результатом буде покажчик на той самий вузол, який був переданий в якості аргументу. Видалення в бінарному алгоритмі
Як і слід було очікувати, видалення елемента пов\'язане з пошуком знаходить сайт, який містить значення, яке потрібно видалити. У цьому коді є кілька речей: BST використовує допоміжний, перевантажений метод видалення. Якщо шуканий елемент не знаходиться в дереві, то в підсумку допоміжний метод буде викликатися з n == null. Це не вважається помилкою, дерево в цьому випадку не змінюється. Допоміжний метод видалення повертає значення — вказівник на оновлене дерево. Коли видаляється аркуш, при видаленні з бінарного дерева пошуку встановлюється відповідний дочірній покажчик його батька на нуль або корінь у null, якщо видаляється вузол є коренем, і у нього немає дітей. Потрібно звернути увагу на те, що виклик для видалення повинен бути одним з наступних: root = delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete (n.getRight (), key)). Таким чином, у всіх трьох випадках правильно, коли метод delete просто повертає null. Коли пошук вузла, що містить потрібне значення, завершується успішно, то існує три варіанти: вузол для видалення — лист (не має дітей), у видаленого вузла є одна дитина, у нього є двоє дітей. Коли видаляється вузол має один дочірній елемент, можна просто замінити його нащадком, повертаючи вказівник на дочірній елемент. Якщо видаляється вузол має нуль або 1 дочірній елемент, то метод видалення буде «слідувати по шляху» від кореня до цього вузла. Таким чином, найгірший час пропорційно висоті дерева, як і для пошуку, так і вставки.
Якщо видаляється вузол має двох дітей, виконуються наступні кроки: Знайти видаляється вузол, слідуючи по шляху від кореня до нього. Знайти найменше значення v у правому поддереве, продовжуючи рух по шляху до листу. Рекурсивно вилучити значення v, йти по тому ж шляху, що і в пункті 2. Таким чином, в гіршому випадку шлях від кореня до листа виконується двічі. Порядок траверсів
Обхід (Traversal) — це процес, який відвідує всі вузли в дереві. Оскільки бінарне дерево пошуку сі є нелінійною структурою даних, унікального обходу не існує. Наприклад, іноді кілька алгоритмів обходу згруповані за наступними двома видами: перетин глибини; перший прохід.
Існує тільки один вид перетину ширини — обхід рівня. Цей обхід відвідує сайти за рівнями вниз і ліворуч, зверху і праворуч.
Існують три різних типи перетинів по глибині: Проходження Предпорядка — спочатку відвідати батька, а потім лівого і правого дитини. Проходження InOrder — відвідування лівого дитини, потім батьків і правильного дитини. Обхід PostOrder — відвідування лівого дочірнього елемента, потім правильного дитини, а далі батька.
Приклад для чотирьох обходів бінарного дерева пошуку: Предпорядка - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3. InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11. PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8. LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
На малюнку показаний порядок відвідувань сайтів. Число 1 означає перший вузол в конкретному обході, а 7 — останній вузол.
Ці загальні обходи можна представити у вигляді єдиного алгоритму, припустивши, що кожен вузол відвідують три рази. Euler тур - прогулянка навколо бінарного дерева, де кожне ребро розглядається як стіна, яку користувач не можете перетнути. У цій прогулянці кожен вузол буде відвідуватися або зліва, або знизу, або праворуч. Тур Euler, в якій відвідуються вузли зліва, викликає обхід прийменника. Коли відвідуються вузли нижче, отримують обхід по порядку. І коли відвідуються вузли праворуч — отримують поопераційний обхід.
Навігація та налагодження
Щоб полегшити переміщення по дереву, створюють функції, які попередньо перевіряють, чи є вони лівим або правим дочірнім елементом. Щоб змінити положення вузла, повинен бути простий доступ до покажчика в батьківському сайті. Правильно реалізувати дерево дуже складно, тому потрібно знати і застосовувати процеси налагодження. У бінарного дерева пошуку c реалізацією часто зустрічаються покажчики, які фактично не вказують напрямок ходу.
Щоб у всьому цьому розібратися, використовується функція, яка перевіряє, чи може дерево бути правильним, і допомагає знайти багато помилок. Наприклад, перевіряє, чи є батьківський вузол вузлом дитини. З допомогою assert (is_wellformed (root)) багато помилок можуть бути передчасно перехоплені. Використовуючи пару заданих контрольних точок усередині цієї функції можна також точно визначити, який покажчик є помилковим. Функція Konsolenausgabe
Ця функція повністю скидає дерево на консоль і тому дуже корисна. Порядок виконання мети висновку дерева: Для цього спочатку треба визначити, яка інформація буде виводитися через сайт. І також потрібно знати, наскільки широким і високим є дерево, щоб врахувати, скільки потрібно залишити вільного місця. Наступні функції обчислюють цю інформацію для дерева і кожного піддерева. Оскільки можна писати в консоль лише по рядках, також потрібно буде виводити дерево по рядках. Тепер потрібний інший спосіб виведення всього дерева, а не тільки рядковий. За допомогою функції дампа можна прочитати дерево і значно поліпшити алгоритм виведення, оскільки це стосується швидкості.
Тим не менш цю функцію буде складно використовувати на великих деревах. Конструктор копіювання та деструктор
Оскільки дерево не є тривіальною структурою даних, краще реалізувати конструктор копіювання, деструктор та оператор присвоювання. Деструктор легко реалізувати рекурсивно. Для дуже великих дерев він може обробляти «переповнення купи». В цьому випадку його формулюють ітеративне. Ідея полягає в тому, щоб видалити лист, який представляє найменше значення всіх листків, тому він знаходиться на лівій стороні дерева. Відрізання перше листя створює нові, і дерево стискається, поки вона, нарешті, перестане існувати.
Конструктор копіювання також може бути реалізований рекурсивно, але потрібно бути обережним, якщо виключення вилітає. Інакше дерево швидко стає заплутаним і схильним до помилок. Ось чому воліють итеративную версію. Ідея полягає в тому, щоб пройти через старе і нове дерево, як це робиться в деструкторе, клонувати всі вузли, які знаходяться в старому дереві, але не нові.
З допомогою цього методу реалізація бінарного дерева пошуку завжди знаходиться в здоровому стані і може бути видалена деструктором навіть у незавершеному стані. Якщо виникає виняток, потрібно тільки дати команду деструктору видалити напівготове дерево. Оператор присвоювання може бути легко реалізований з використанням Copy & Swap. Створення бінарного дерева пошуку
Оптимальні бінарні дерева пошуку неймовірно ефективні, якщо вони управляються належним чином. Деякі правила для двійкових пошукових дерев: Батьківський вузол має найбільшу 2 дочірніх сайту. Лівий дочірній вузол завжди менше батьківського сайту. Правильний дочірній вузол завжди більше або дорівнює батьківського сайту.
Масив, який буде використовуватися для побудови бінарного дерева пошуку: Базовий цілочисельний масив, що складається з семи значень, які знаходяться в несортированном порядку. Перше значення в масиві дорівнює 10, тому першим кроком при побудові дерева буде створення 10 кореневого вузла, як показано тут. З набором кореневих вузлів всі інші значення будуть дочірніми елементами цього сайту. Посилаючись на правила першим кроком, який буде зроблений для додавання 7 в дерево, буде порівняння його з кореневим вузлом. Якщо значення 7 менше 10, воно стане лівим дочірнім вузлом. Якщо значення 7 більше або дорівнює 10, воно буде переміщатися вправо. Оскільки відомо, що 7 менше 10, його позначають як лівий дочірній вузол. Рекурсивно виконати порівняння для кожного елемента. Слідуючи тій же схемі, виконують те ж порівняння з 14 значенням в масиві. Порівнюючи значення 14 з кореневим вузлом 10, знаючи, що 14 — правильний дитина. Пробираючись через масив, приходять до 20. Починають з порівняння масиву з 10, що більше. Таким чином, рухаються вправо і порівнюють його з 14, 14 і не має дітей праворуч. Тепер є значення 1. Слідуючи тій же схемі, що і інші значення, порівнюють з 1 по 10, перемістившись вліво і порівнюючи з 7 і, нарешті, з 1 лівим дочірнім елементом 7-го вузла. При значенні 5 порівнюють його з 10. Оскільки 5 менше 10, проходять вліво і порівнюють його з 7. Знаючи, що на 5 менше 7, продовжують вниз по дереву і порівнюють 5 із значенням 1. Якщо 1 не має дочірніх вузлів, а 5 — більше 1, то 5 — правильний дитина з 1 вузла. Нарешті, вставляють значення 8 в дерево. При 8 менше, ніж 10, переміщують його вліво і порівнюємо його з 7, 8 більше 7, тому переміщують його вправо і завершують дерево, що робить 8 правильним дитиною 7.
Отримуємо і оцінюємо просту елегантність оптимальних бінарних дерев пошуку. Як і багато інші теми в програмуванні, сила двійкових дерев пошуку залежить від їх здатності вирішувати розбиття даних на невеликі пов\'язані компоненти. З цього моменту можна працювати з повним набором даних організованим чином. Потенційні проблеми двійкового пошуку
Дерева двійкового пошуку хороші, але є кілька застережень, про які потрібно пам\'ятати. Вони зазвичай ефективні тільки в тому випадку, якщо збалансовані. Збалансоване дерево — це дерево,в якому різниця між висотами піддерев будь-якого вузла у дереві не більше одиниці. Розглянемо приклад, який може допомогти роз\'яснити правила. Уявімо, що масив починається, як сортовані.
Якщо спробувати запустити алгоритм двійкового дерева пошуку в цьому дереві, він буде виконувати точно так само, як якщо б просто повторювати масив, поки не буде знайдене шукане значення. Сила двійкового пошуку полягає в можливості швидко відфільтрувати непотрібні значення. Коли дерево не збалансовано, він не дасть таких переваг, як збалансоване дерево.
Дуже важливо вивчити дані, з якими працює користувач, коли створюється бінарне дерево пошуку. Можна інтегрувати підпрограми, такі як рандомізація масиву, перш ніж реалізувати бінарне дерево пошуку для цілих чисел, щоб збалансувати його. Приклади розрахунку двійкового пошуку
Потрібно визначити, яке дерево вийде, якщо буде вставлено 25 в наступне дерево двійкового пошуку:
10
/
/
5 15
/ /
/ /
2 12 20
Коли вставляють x в дерево T, яке ще не містить x, ключ x завжди поміщається в новий лист. У зв\'язку з чим нове дерево буде мати вигляд:
10
/
/
5 15
/ /
/ /
2 12 20
25
Яке дерево буде отримано, якщо вставити 7 наступне дерево двійкового пошуку?
10
/
/
5 15
/ /
/ /
2 12 20
Відповідь:
10
/
/
/
5 15
/ /
/ /
2 7 12 20
Бінарне дерево пошуку може використовуватися для зберігання будь-яких об\'єктів. Перевага використання бінарного дерева пошуку замість пов\'язаного списку полягає в тому, що якщо дерево розумно збалансовано і більше схоже на «повне» дерево, ніж «лінійне», вставка, пошук, і всі операції видалення можуть бути реалізовані для запуску в O (log N) часу. Автор: Іван 26 Липня, 2018
Категория: Новости
