binary search tree c
Подробен урок за бинарно дърво за търсене (BST) в C ++, включващ операции, внедряване на C ++, предимства и примерни програми:
Двоично дърво за търсене или BST, както е популярно наричано, е двоично дърво, което отговаря на следните условия:
- Възлите, които са по-малки от кореновия възел, който е поставен като оставени дъщери на BST.
- Възлите, които са по-големи от основния възел, който е поставен като правилните дъщери на BST.
- Лявото и дясното поддървета са от своя страна бинарни дървета за търсене.
Тази подредба на подреждането на ключовете в определена последователност улеснява програмиста да извършва по-ефективно операции като търсене, вмъкване, изтриване и т.н. Ако възлите не са подредени, може да се наложи да сравним всеки възел, преди да можем да получим резултата от операцията.
=> Проверете тук пълната серия за обучение на C ++.
Какво ще научите:
- Двоично дърво за търсене C ++
- Основни операции
- Внедряване на бинарно дърво за търсене C ++
- Предимства на BST
- Приложения на BST
- Заключение
- Препоръчително четене
Двоично дърво за търсене C ++
Примерен BST е показан по-долу.
Бинарните дървета за търсене също се наричат „Подредени двоични дървета“ поради това специфично подреждане на възлите.
От горното BST можем да видим, че лявото поддърво има възли, които са по-малки от корена, т.е. 45, докато дясното поддърво има възли, които са по-големи от 45.
Сега нека обсъдим някои основни операции на BST.
Основни операции
# 1) Вмъкване
Операцията за вмъкване добавя нов възел в двоично дърво за търсене.
Алгоритъмът за операцията за вмъкване на двоично дърво за търсене е даден по-долу.
sql сървър заявки примери с отговори
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
можете ли да направите масив от обекти в java
В следващите стъпки ще поставим данните според дефиницията на бинарното дърво за търсене, т.е. ако данните са по-малки от родителския възел, тогава те ще бъдат поставени в лявото дете и ако данните са по-големи от родителския възел, тогава ще бъде правилното дете.
Тези стъпки са показани по-долу.
# 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) Търсенето е много ефективно
Разполагаме с всички възли на 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 ++