Меню

Двоично дърво за търсене C ++: Внедряване на BST и операции с примери

  • Основен
  • Други
  • Двоично дърво за търсене C ++: Внедряване на BST и операции с примери

binary search tree c

Подробен урок за бинарно дърво за търсене (BST) в C ++, включващ операции, внедряване на C ++, предимства и примерни програми:

Двоично дърво за търсене или BST, както е популярно наричано, е двоично дърво, което отговаря на следните условия:

  1. Възлите, които са по-малки от кореновия възел, който е поставен като оставени дъщери на BST.
  2. Възлите, които са по-големи от основния възел, който е поставен като правилните дъщери на BST.
  3. Лявото и дясното поддървета са от своя страна бинарни дървета за търсене.

Тази подредба на подреждането на ключовете в определена последователност улеснява програмиста да извършва по-ефективно операции като търсене, вмъкване, изтриване и т.н. Ако възлите не са подредени, може да се наложи да сравним всеки възел, преди да можем да получим резултата от операцията.

=> Проверете тук пълната серия за обучение на C ++.

Дърво на двоично търсене в C ++

Какво ще научите:

Двоично дърво за търсене C ++

Примерен BST е показан по-долу.

Пример BST

sql сървър заявки примери с отговори

Бинарните дървета за търсене също се наричат ​​„Подредени двоични дървета“ поради това специфично подреждане на възлите.

От горното BST можем да видим, че лявото поддърво има възли, които са по-малки от корена, т.е. 45, докато дясното поддърво има възли, които са по-големи от 45.

Сега нека обсъдим някои основни операции на BST.

Основни операции

# 1) Вмъкване

Операцията за вмъкване добавя нов възел в двоично дърво за търсене.

Алгоритъмът за операцията за вмъкване на двоично дърво за търсене е даден по-долу.

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) Изтриване

Операцията Delete изтрива възел, който съответства на дадения ключ от BST. И при тази операция трябва да преместваме останалите възли след изтриване, така че BST подреждането да не бъде нарушено.

Следователно в зависимост от това кой възел трябва да изтрием, имаме следните случаи за изтриване в BST:

# 1) Когато възелът е Leaf Node

Когато възелът, който трябва да се изтрие, е листен възел, тогава ние директно изтриваме възела.

Node е листен възел

# 2) Когато възелът има само едно дете

Когато възелът, който трябва да бъде изтрит, има само едно дете, тогава ние копираме детето във възела и изтриваме детето.

Възелът има само едно дете

# 3) Когато възелът има две деца

Ако възелът, който трябва да бъде изтрит, има две деца, тогава ние намираме наследника на inorder за възела и след това копираме наследника на inorder в възела. По-късно изтриваме наследника на inorder.

Node има две деца

В горното дърво, за да изтрием възела 6 с две деца, първо намираме наследника на inorder за този възел, който трябва да бъде изтрит. Намираме наследника на inorder, като намираме минималната стойност в правилното поддърво. В горния случай минималната стойност е 7 в дясното поддърво. Копираме го в възела, който трябва да бъде изтрит, и след това изтриваме наследника на inorder.

# 3) Търсене

Операцията за търсене на BST търси определен елемент, идентифициран като „ключ“ в BST. Предимството на търсенето на елемент в BST е, че не е необходимо да търсим цялото дърво. Вместо това, поради подреждането в BST, ние просто сравняваме ключа с корена.

Ако ключът е същият като root, ние връщаме root. Ако ключът не е 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) => No 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
Обръщане след поръчка (lrn): 3 6 5 8 10 9 7

Илюстрация

Нека да изградим двоично дърво за търсене от данните, дадени по-долу.

45 30 60 65 70

Нека вземем първия елемент като основен възел.

# 1) 45

корен възел

В следващите стъпки ще поставим данните според дефиницията на бинарното дърво за търсене, т.е. ако данните са по-малки от родителския възел, тогава те ще бъдат поставени в лявото дете и ако данните са по-големи от родителския възел, тогава ще бъде правилното дете.

Тези стъпки са показани по-долу.

# 2) 30

Дърво на двоично търсене Стъпка 1 30

# 3) 60

Дърво на двоично търсене Стъпка 2 60

# 4) 65

11 Двоично дърво за търсене, стъпка 3

# 5) 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):'<

Изход:

Създадено е двоично дърво за търсене (Invert traversal):

30 40 60 65 70

Изтрийте възел 40

Вътрешно обръщане за модифицираното двоично дърво за търсене:

30 60 65 70

В горната програма извеждаме BST за последователност на обръщане по ред.

Предимства на BST

# 1) Търсенето е много ефективно

можете ли да направите масив от обекти в java

Разполагаме с всички възли на BST в определен ред, поради което търсенето на определен елемент е много ефективно и по-бързо. Това е така, защото не е необходимо да търсим цялото дърво и да сравняваме всички възли.

Просто трябва да сравним основния възел с елемента, който търсим, и след това решаваме дали трябва да търсим в лявото или дясното поддърво.

# 2) Ефективна работа в сравнение с масиви и свързани списъци

Когато търсим елемент в случай на BST, ние се отърваваме от половината от лявото или дясното поддърво на всяка стъпка, като по този начин подобряваме ефективността на операцията за търсене. Това е за разлика от масивите или свързаните списъци, в които трябва да сравняваме всички елементи последователно, за да търсим определен елемент.

# 3) Вмъкване и изтриване са по-бързи

Операциите за вмъкване и изтриване също са по-бързи в сравнение с други структури от данни, като свързани списъци и масиви.

Приложения на BST

Някои от основните приложения на BST са както следва:

  • BST се използва за прилагане на многостепенно индексиране в приложения за бази данни.
  • BST се използва и за реализиране на конструкции като речник.
  • BST може да се използва за реализиране на различни ефективни алгоритми за търсене.
  • BST се използва и в приложения, които изискват сортиран списък като вход като онлайн магазините.
  • BST също се използват за оценка на израза, като се използват дървета на изрази.

Заключение

Бинарните дървета за търсене (BST) са разновидност на двоичното дърво и се използват широко в софтуерната област. Те също се наричат ​​подредени двоични дървета, тъй като всеки възел в BST се поставя според определен ред.

Прехвърлянето на BST ни дава сортирана последователност от елементи във възходящ ред. Когато BST се използват за търсене, това е много ефективно и се извършва за нула време. BST също се използват за различни приложения като кодиране на Huffman, многостепенно индексиране в бази данни и т.н.

=> Прочетете Популярната серия за обучение на C ++ тук.

Препоръчително четене

^