Меню

Бінарне дерево пошуку C ++: Впровадження BST та операції з прикладами

  • Головна
  • Інший
  • Бінарне дерево пошуку C ++: Впровадження BST та операції з прикладами

binary search tree c

Спробуйте Наш Інструмент Для Усунення Проблем

Детальний підручник з бінарного дерева пошуку (BST) у C ++, що включає операції, реалізацію C ++, переваги та приклади програм:

Бінарне дерево пошуку або BST, як його в народі називають, це бінарне дерево, яке відповідає наступним умовам:

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

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

=> Ознайомтесь із Повною навчальною серією C ++ тут

Бінарне дерево пошуку в C ++

Що ви дізнаєтесь:

Бінарне дерево пошуку C ++

Зразок BST наведено нижче.

Зразок BST

Бінарні дерева пошуку також називаються 'впорядкованими двійковими деревами' через це специфічне упорядкування вузлів.

З наведеного вище BST ми бачимо, що ліве піддерево має вузли, менші за корінь, тобто 45, тоді як праве піддерево має вузли, більші за 45.

Тепер обговоримо деякі основні операції BST.

Основні операції

# 1) Вставка

Операція вставки додає новий вузол у двійковому дереві пошуку.

Алгоритм операції вставки бінарного дерева пошуку наведено нижче.

протоколи, що використовуються в кожному шарі моделі osi
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end

Як показано в наведеному вище алгоритмі, ми повинні переконатися, що вузол розміщений у відповідному положенні, щоб ми не порушували порядок BST.

Вставити операцію в BST

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

# 2) Видалити

Операція видалення видаляє вузол, який відповідає даному ключу, з BST. У цій операції ми також повинні змінити положення решти вузлів після видалення, щоб не порушувати порядок BST.

Отже, залежно від того, який вузол нам потрібно видалити, у нас є такі випадки для видалення в BST:

# 1) Коли вузол є Листовим Вузлом

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

Вузол - це листовий вузол

# 2) Коли вузол має лише одну дитину

Коли вузол, який потрібно видалити, має лише одну дочірню організацію, ми копіюємо дитину у вузол і видаляємо її.

Вузол має лише одну дитину

# 3) Коли вузол має двох дітей

Якщо вузол, який потрібно видалити, має двох дітей, тоді ми знаходимо наступника inorder для вузла, а потім копіюємо наступника inorder на вузол. Пізніше ми видаляємо наступника inorder.

Вузол має двох дітей

У наведеному вище дереві для видалення вузла 6 з двома дочірніми об’єктами спочатку ми знаходимо наступника inorder для цього вузла, який потрібно видалити. Ми знаходимо наступника inorder, знаходячи мінімальне значення у правильному піддереві. У наведеному вище випадку мінімальне значення - 7 у правому піддереві. Ми копіюємо його на вузол, який потрібно видалити, а потім видаляємо наступника inorder.

# 3) Пошук

Операція пошуку BST здійснює пошук певного елемента, визначеного як “ключ” у BST. Перевага пошуку елемента в BST полягає в тому, що нам не потрібно шукати все дерево. Натомість із-за впорядкування в BST ми просто порівнюємо ключ із коренем.

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

Далі наведено алгоритм операції пошуку в BST.

Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end

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

Якщо ми хочемо здійснити пошук ключа зі значенням 6 у наведеному вище дереві, то спочатку ми порівнюємо ключ із кореневим вузлом, тобто if (6 == 7) => Ні if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Далі ми спускаємось до лівого піддерева. Якщо (6 == 5) => Ні.

Якщо (6 Ні; це означає 6> 5, і ми повинні рухатися вправо.

Якщо (6 == 6) => Так; ключ знайдено.

# 4) Обхід

Ми вже обговорювали обходи бінарного дерева. У випадку з BST, ми можемо пройти дерево, щоб отримати послідовність inOrder, preorder або postOrder. Насправді, коли ми проходимо BST у послідовності Inorder01, ми отримуємо відсортовану послідовність.

Ми показали це на ілюстрації нижче.

обхід

Обхід для вищезазначеного дерева такий:

Внутрішній обхід (lnr): 3 5 6 7 8 9 10
Обхід попереднього замовлення (nlr): 7 5 3 6 9 8 10
Обхід PostOrder (lrn): 3 6 5 8 10 9 7

Ілюстрація

Давайте побудуємо бінарне дерево пошуку з даних, наведених нижче.

char до цілого числа c ++

45 30 60 65 70

Візьмемо перший елемент як кореневий вузол.

No1) 45

кореневий вузол

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

Ці кроки показані нижче.

№2) 30

Дерево двійкового пошуку Крок 1 30

№ 3) 60

Дерево двійкового пошуку Крок 2 60

No4) 65

11 Бінарне дерево пошуку step3

No5) 70

Крок 4 дерева двійкового пошуку

Коли ми виконуємо обхід в порядку наведеного вище BST, який ми щойно побудували, послідовність виглядає наступним чином.

Послідовність обходу в порядку

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

Реалізація бінарного дерева пошуку C ++

Давайте продемонструємо BST та його операції за допомогою реалізації C ++.

#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'<

Вихід:

Створено бінарне дерево пошуку (обхід в порядку):

30 40 60 65 70

Видалити вузол 40

Обхід обходу для модифікованого дерева двійкового пошуку:

30 60 65 70

У наведеній вище програмі ми виводимо BST для послідовності обходу в порядку.

Переваги BST

# 1) Пошук дуже ефективний

Ми маємо всі вузли BST у певному порядку, отже пошук певного елемента є дуже ефективним та швидшим. Це тому, що нам не потрібно шукати все дерево і порівнювати всі вузли.

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

# 2) Ефективна робота в порівнянні з масивами та пов'язаними списками

Коли ми шукаємо елемент у випадку BST, ми позбавляємося половини лівого або правого піддерева на кожному кроці, тим самим покращуючи ефективність операції пошуку. Це на відміну від масивів або пов’язаних списків, в яких нам потрібно порівнювати всі елементи послідовно для пошуку певного елемента.

# 3) Вставлення та видалення швидше

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

Застосування BST

Деякі з основних застосувань BST:

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

Висновок

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

У порядку обходу BST ми отримуємо відсортовану послідовність елементів у порядку зростання. Коли BST використовуються для пошуку, це дуже ефективно і робиться в найкоротші терміни. BST також використовуються для різних додатків, таких як кодування Хаффмана, багаторівнева індексація в базах даних тощо.

=> Ознайомтесь з Популярною серією навчальних програм C ++ тут.

Рекомендована література

^