binary search tree c
Подробен урок за бинарно дърво за търсене (BST) в C ++, включващ операции, внедряване на C ++, предимства и примерни програми:
Двоично дърво за търсене или BST, както е популярно наричано, е двоично дърво, което отговаря на следните условия:
- Възлите, които са по-малки от кореновия възел, който е поставен като оставени дъщери на BST.
- Възлите, които са по-големи от основния възел, който е поставен като правилните дъщери на BST.
- Лявото и дясното поддървета са от своя страна бинарни дървета за търсене.
Тази подредба на подреждането на ключовете в определена последователност улеснява програмиста да извършва по-ефективно операции като търсене, вмъкване, изтриване и т.н. Ако възлите не са подредени, може да се наложи да сравним всеки възел, преди да можем да получим резултата от операцията.
=> Проверете тук пълната серия за обучение на C ++.
Какво ще научите:
- Двоично дърво за търсене C ++
- Основни операции
- Внедряване на бинарно дърво за търсене C ++
- Предимства на BST
- Приложения на BST
- Заключение
- Препоръчително четене
Двоично дърво за търсене C ++
Примерен 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 подреждането.
Както виждаме в горната последователност от диаграми, ние правим поредица от операции за вмъкване. След сравняване на ключа, който трябва да се вмъкне с кореновия възел, лявото или дясното поддърво се избира за ключа, който трябва да се вмъкне като листен възел на подходящата позиция.
# 2) Изтриване
Операцията Delete изтрива възел, който съответства на дадения ключ от BST. И при тази операция трябва да преместваме останалите възли след изтриване, така че BST подреждането да не бъде нарушено.
Следователно в зависимост от това кой възел трябва да изтрием, имаме следните случаи за изтриване в BST:
# 1) Когато възелът е Leaf Node
Когато възелът, който трябва да се изтрие, е листен възел, тогава ние директно изтриваме възела.
# 2) Когато възелът има само едно дете
Когато възелът, който трябва да бъде изтрит, има само едно дете, тогава ние копираме детето във възела и изтриваме детето.
# 3) Когато възелът има две деца
Ако възелът, който трябва да бъде изтрит, има две деца, тогава ние намираме наследника на inorder за възела и след това копираме наследника на inorder в възела. По-късно изтриваме наследника на inorder.
В горното дърво, за да изтрием възела 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
Ако искаме да търсим ключ със стойност 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
# 3) 60
# 4) 65
# 5) 70
Когато изпълняваме обръщане по ред на горния 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 ++ тук.
Препоръчително четене
- Структура на данните на двоичното дърво в C ++
- Структура на данните за дърво и купчина AVL в C ++
- Структура на данните от B Tree и B + Tree в C ++
- Основни операции по въвеждане / извеждане в C ++
- Основни I / O операции в Java (входни / изходни потоци)
- Дървета в C ++: Основна терминология, техники за преминаване и типове дървета на C ++
- Операции за извеждане на файл в C ++
- Указатели и операции на показалеца в C ++