B TREE в структурі даних: Приклад операції пошуку, вставки, видалення

Зміст:

Anonim

Що таке дерево B?

B Tree - це самобалансуюча структура даних, що базується на певному наборі правил для пошуку, вставлення та видалення даних швидшим та ефективнішим способом. Для того, щоб досягти цього, дотримуйтесь наведених нижче правил для створення дерева B.

B-Tree - це особливий вид дерева в структурі даних. У 1972 р. Цей метод вперше був представлений МакКрайтом, і Байєр назвав його Height Balanced m-way Search Tree. Це допомагає зберегти відсортовані дані та дозволити різні операції, такі як вставка, пошук і видалення за менший час.

У цьому підручнику B-Tree ви дізнаєтесь:

  • Що таке дерево B?
  • Навіщо використовувати B-Tree
  • Історія дерева B
  • Пошукова операція
  • Операція вставки
  • Видалити операцію

Правила для B-Tree

Тут є важливі правила створення B_Tree

  • Всі листки будуть створені на одному рівні.
  • B-Tree визначається кількістю ступенів, що також називається "порядком" (визначається зовнішнім актором, наприклад програмістом), іменованим як 
    m
    далі. Значення 
    m
    залежить від розміру блоку на диску, на якому в основному знаходяться дані.
  • Ліве піддерево вузла матиме менші значення, ніж праве право піддерева. Це означає, що вузли також сортуються за зростанням зліва направо.
  • Максимальна кількість дочірніх вузлів, який може містити кореневий вузол, а також його дочірні вузли, обчислюється за цією формулою: 
    m - 1
    Наприклад: 
    m = 4max keys: 4 - 1 = 3

  • Кожен вузол, крім кореневого, повинен містити мінімум ключів 
    [m/2]-1
    Наприклад: 
    m = 4min keys: 4/2-1 = 1
  • Максимальна кількість дочірніх вузлів, які може мати вузол, дорівнює його ступеню, тобто 
    m
  • Мінімальна кількість дочірніх елементів, яку може мати вузол, становить половину порядку, що дорівнює м / 2 (береться значення стелі).
  • Усі ключі у вузлі відсортовані за зростанням.

Навіщо використовувати B-Tree

Ось причини використання B-Tree

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

Історія дерева B

  • Дані зберігаються на диску блоками, ці дані, потрапляючи в основну пам’ять (або оперативну пам’ять), називаються структурою даних.
  • У випадку величезних даних для пошуку одного запису на диску потрібно прочитати весь диск; це збільшує час та споживання основної пам'яті завдяки високій частоті доступу до диска та обсягу даних.
  • Щоб подолати це, створюються таблиці індексів, які зберігають посилання на записи на основі блоків, в яких вони перебувають. Це різко зменшує час та споживання пам'яті.
  • Оскільки ми маємо величезні дані, ми можемо створювати багаторівневі таблиці покажчиків.
  • Багаторівневий індекс може бути розроблений за допомогою дерева B для збереження даних, відсортованих у спосіб самобалансування.

Пошукова операція

Операція пошуку - це найпростіша операція на дереві B.

Застосовано такий алгоритм:

  • Нехай ключ (значення) шукатиметься за "k".
  • Почніть пошук з кореня і рекурсивно пройдіть вниз.
  • Якщо k менше кореневого значення, шукайте ліве піддерево, якщо k більше кореневого значення, шукайте праве піддерево.
  • Якщо вузол має знайдений k, просто поверніть вузол.
  • Якщо k у вузлі не знайдено, перейдіть до дочірнього за допомогою більшого ключа.
  • Якщо k у дереві не знайдено, ми повертаємо NULL.

Операція вставки

Оскільки B Tree є самобалансуючим деревом, ви не можете примусово вставити ключ у будь-який вузол.

Застосовується такий алгоритм:

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

ПОРАДА

Про алгоритм вставки не відповідає дійсності:

Оскільки вузол заповнений, отже він буде розділений, а потім буде вставлено нове значення

У наведеному вище прикладі:

  • Шукайте відповідну позицію у вузлі для ключа
  • Вставте ключ у цільовий вузол та перевірте наявність правил
  • Після вставки чи має вузол більше ніж рівну мінімальній кількості ключів, яка дорівнює 1? У цьому випадку так, це так. Перевірте наступне правило.
  • Після вставки чи має вузол більше максимальної кількості ключів, що становить 3? У цьому випадку ні, це не так. Це означає, що дерево B не порушує жодних правил, і вставка завершена.

У наведеному вище прикладі:

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

У наведеному вище прикладі:

  • Вузол має менше ніж максимум ключів
  • 1 вставляється поруч із 3, але правило за зростанням порушується
  • Для того, щоб це виправити, ключі сортуються

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

У наведеному вище прикладі:

  • Вузол має ключі, рівні макс.
  • Ключ вставляється в цільовий вузол, але він порушує правило макс. Ключів.
  • Цільовий вузол розділений, а середній ключ за лівим зміщенням тепер є батьківським для нових дочірніх вузлів.
  • Нові вузли розташовані у порядку зростання.

Подібним чином, виходячи з вищезазначених правил та випадків, решта значень можна легко вставити в дерево B.

Видалити операцію

Операція видалення має більше правил, ніж операції вставки та пошуку.

Застосовується такий алгоритм:

  • Запустіть операцію пошуку та знайдіть цільовий ключ у вузлах
  • Застосовано три умови на основі розташування цільового ключа, як пояснюється в наступних розділах

Якщо цільовий ключ знаходиться в листовому вузлі

  • Ціль знаходиться в листовому вузлі, більше ніж мінімум ключів.
    • Видалення цього не порушить властивість дерева B
  • Ціль знаходиться в листовому вузлі, він має мінімальні ключові вузли
    • Видалення цього призведе до порушення властивості дерева B
    • Цільовий вузол може позичити ключ у безпосереднього лівого вузла або безпосереднього правого вузла (брата або сестри)
    • Брат або сестра скажуть так, якщо у нього більше ніж мінімальна кількість ключів
    • Ключ буде запозичений у батьківського вузла, максимальне значення буде передано батьківському, максимальне значення батьківського вузла буде передано цільовому вузлу і видалить цільове значення
  • Ціль знаходиться в листовому вузлі, але жоден брат чи сестра не має більше ніж мінімальну кількість ключів
    • Шукати ключ
    • Злиття з побратимами та мінімумом батьківських вузлів
    • Загальна кількість ключів тепер буде більше ніж хв
    • Цільовий ключ буде замінений мінімумом батьківського вузла

Якщо цільовий ключ знаходиться у внутрішньому вузлі

  • Виберіть або попередника за порядком, або наступника за порядком
  • У випадку попередника в порядку, буде вибрано максимальний ключ з його лівого піддерева
  • У випадку наступника за порядком, буде вибрано мінімальний ключ з його правого піддерева
  • Якщо попередник у порядку цільового ключа має більше, ніж мінімальних ключів, лише тоді він може замінити цільовий ключ на макс. Попередника в порядку
  • Якщо попередник порядку замовлення цільового ключа не має більше ключів min, знайдіть мінімальний ключ наступника порядку.
  • Якщо попередник та наступник цільового ключа мають менше, ніж мінімальних ключів, тоді об’єднайте попередника та наступника.

Якщо цільовий ключ знаходиться в кореневому вузлі

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

Тепер давайте розберемося з операцією видалення на прикладі.

На наведеній вище схемі показано різні випадки операції видалення в B-Tree. Це B-дерево має порядок 5, що означає, що мінімальна кількість дочірніх вузлів, які може мати будь-який вузол, дорівнює 3, а максимальна кількість дочірніх вузлів, які може мати будь-який вузол, - 5. Тоді як мінімальна та максимальна кількість ключів будь-якого вузла може мати відповідно 2 і 4.

У наведеному вище прикладі:

  • Цільовий вузол має цільовий ключ для видалення
  • Цільовий вузол має ключі більше ніж мінімальні ключі
  • Просто видаліть ключ

У наведеному вище прикладі:

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

На наступній схемі пояснюється, як видалити цей ключ:

  • Цільовий вузол позичить ключ у безпосереднього брата або сестри, у цьому випадку у попередника по порядку (лівий брат), оскільки він не має наступного в порядку (правий брат)
  • Максимальне значення попередника inorder буде передано батьківському, а батьківський передасть максимальне значення цільовому вузлу (див. Схему нижче)

Наступний приклад ілюструє, як видалити ключ, якому потрібне значення, з наступника за порядком.

  • Цільовий вузол позичить ключ у безпосереднього брата, у цьому випадку наступника за порядком (правий брат), оскільки його попередник у порядку (лівий брат) має ключі, рівні мінімальним ключам.
  • Мінімальне значення наступника за порядком буде передано батьківському, а батьківський передасть максимальне значення цільовому вузлу.

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

Дивіться процедуру видалення такого ключа:

  • Об’єднайте цільовий вузол з будь-яким з його безпосередніх братів і сестер разом із батьківським ключем
    • Вибрано ключ від батьківського вузла, який поєднується між двома вузлами злиття
  • Видаліть цільовий ключ із об’єднаного вузла

Видалити операційний псевдокод

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Вихід :

Найбільший елемент видалено з дерева B.

Короткий зміст:

  • B Tree - це самобалансуюча структура даних для кращого пошуку, вставки та видалення даних з диска.
  • B Дерево регулюється вказаним ступенем
  • B Клавіші та вузли дерева розташовані у порядку зростання.
  • Операція пошуку дерева B є найпростішою, яка завжди починається з кореня і починає перевіряти, чи є цільовий ключ більшим чи меншим за значення вузла.
  • Операція вставки дерева B є досить детальною, яка спочатку знаходить відповідне місце вставки для цільового ключа, вставляє його, оцінює валідність дерева B щодо різних випадків, а потім відповідно реструктурує вузли дерева B.
  • Операція видалення дерева B спочатку здійснює пошук цільового ключа, який потрібно видалити, видаляє його, оцінює валідність на основі кількох випадків, таких як мінімальний і максимальний ключі цільового вузла, братів і сестер та батьків.