Menu

Binárny vyhľadávací strom C ++: implementácia a operácie BST s príkladmi

  • Hlavná
  • Iné
  • Binárny vyhľadávací strom C ++: implementácia a operácie BST s príkladmi

binary search tree c

Podrobný návod na binárny vyhľadávací strom (BST) v jazyku C ++ vrátane operácií, implementácie C ++, výhod a príkladov programov:

Binárny vyhľadávací strom alebo BST, ako sa ľudovo nazýva, je binárny strom, ktorý spĺňa nasledujúce podmienky:

  1. Uzly, ktoré sú menšie ako koreňový uzol, ktorý je umiestnený ako ľavé deti BST.
  2. Uzly, ktoré sú väčšie ako koreňový uzol, ktorý je umiestnený ako správne deti BST.
  3. Ľavý a pravý podstrom sú zase binárnymi vyhľadávacími stromami.

Toto usporiadanie usporiadania klávesov v konkrétnom poradí umožňuje programátorovi efektívnejšie vykonávať operácie, ako je vyhľadávanie, vkladanie, mazanie atď. Ak uzly nie sú zoradené, potom možno budeme musieť porovnať každý uzol, aby sme dosiahli výsledok operácie.

=> Kompletnú sériu školení v C ++ nájdete tu.

Binárny vyhľadávací strom v C ++

Čo sa dozviete:

Binárny vyhľadávací strom C ++

Vzor BST je uvedený nižšie.

Ukážka BST

kde nájdem bezpečnostný kľúč pre bezdrôtovú sieť

Binárne vyhľadávacie stromy sa kvôli tomuto špecifickému usporiadaniu uzlov označujú aj ako „usporiadané binárne stromy“.

Z vyššie uvedeného BST vidíme, že ľavý podstrom má uzly, ktoré sú menšie ako koreň, t. J. 45, zatiaľ čo pravý podstrom má uzly, ktoré sú väčšie ako 45.

Teraz poďme diskutovať o niekoľkých základných operáciách BST.

Základné operácie

# 1) Vložte

Operácia vloženia pridá nový uzol do binárneho vyhľadávacieho stromu.

Algoritmus pre operáciu vloženia binárneho vyhľadávacieho stromu je uvedený nižšie.

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

Ako je uvedené vo vyššie uvedenom algoritme, musíme sa ubezpečiť, že uzol je umiestnený na príslušnej pozícii, aby sme neporušili usporiadanie BST.

Vložte operáciu do BST

Ako vidíme vo vyššie uvedenej postupnosti diagramov, urobíme sériu operácií vkladania. Po porovnaní kľúča, ktorý sa má vložiť s koreňovým uzlom, sa zvolí ľavý alebo pravý podstrom pre kľúč, ktorý sa má vložiť ako listový uzol na príslušnej pozícii.

# 2) Odstrániť

Operácia vymazania vymaže uzol, ktorý sa zhoduje s daným kľúčom z BST. Aj v tejto operácii musíme po vymazaní premiestniť zostávajúce uzly, aby nedošlo k porušeniu objednávania BST.

Preto v závislosti od toho, ktorý uzol musíme odstrániť, máme v BST nasledujúce prípady odstránenia:

# 1) Keď je uzol Leaf Node

Keď je uzol, ktorý sa má vymazať, listový uzol, potom uzol priamo odstránime.

Uzol je listový uzol

# 2) Keď má uzol iba jedno dieťa

Keď má uzol, ktorý sa má vymazať, iba jedno dieťa, skopírujeme ho do uzla a dieťa vymažeme.

Node má iba jedno dieťa

# 3) Keď má uzol dve deti

Ak má uzol, ktorý sa má vymazať, dve podradené položky, nájdeme nasledujúceho poradia pre uzol a potom skopírujeme nasledovného poradia do uzla. Neskôr odstránime nasledujúceho poradia.

Node má dve deti

Vo vyššie uvedenom strome na odstránenie uzla 6 s dvoma potomkami najskôr nájdeme následného poradia tohto uzla, ktorý sa má vymazať. Nasledujúceho poradia nájdeme nájdením minimálnej hodnoty v pravom podstrome. V uvedenom prípade je minimálna hodnota 7 v pravom podstrome. Skopírujeme ho do uzla, ktorý sa má vymazať, a potom odstránime nasledujúceho poradia.

# 3) Vyhľadajte

Operácia vyhľadávania BST vyhľadá konkrétnu položku identifikovanú ako „kľúč“ v BST. Výhodou hľadania položky v BST je, že nemusíme prehľadávať celý strom. Namiesto toho kvôli objednaniu v BST iba porovnáme kľúč s rootom.

Ak je kľúč rovnaký ako root, potom vrátime root. Ak kľúč nie je root, porovnáme ho s rootom, aby sme určili, či potrebujeme prehľadať ľavý alebo pravý podstrom. Keď nájdeme podstrom, musíme vyhľadať kľúč a rekurzívne ho vyhľadať v ktoromkoľvek z podstromov.

Nasleduje algoritmus vyhľadávacej operácie v 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

Vyhľadávacia operácia v BST

Ak chceme vyhľadať kľúč s hodnotou 6 vo vyššie uvedenom strome, potom najskôr porovnáme kľúč s koreňovým uzlom, tzn. If (6 == 7) => Nie if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Ďalej zostupujeme do ľavého pod stroma. Ak (6 == 5) => Nie.

Ak (6 Nie; to znamená 6> 5 a musíme sa pohnúť doprava.

If (6 == 6) => Áno; kľúč sa našiel.

# 4) Traversals

Už sme diskutovali o prechodoch pre binárny strom. Aj v prípade BST môžeme stromom prechádzať, aby sme dostali poradie, objednávku alebo predobjednávku. V skutočnosti, keď prechádzame BST v sekvencii Inorder01, dostaneme zoradenú sekvenciu.

Ukázali sme to na ilustrácii nižšie.

traverzy

Traverzy pre vyššie uvedený strom sú nasledujúce:

Traversal inorder (lnr): 3 5 6 7 8 9 10
Predobjednávka (nlr): 7 5 3 6 9 8 10
Prechod po objednávke (lrn): 3 6 5 8 10 9 7

Ilustrácia

Vytvorme binárny vyhľadávací strom z údajov uvedených nižšie.

45 30 60 65 70

Zoberme si prvý prvok ako koreňový uzol.

# 1) 45

aplikácia pre Android špehovať iný telefón

koreňový uzol

V ďalších krokoch umiestnime údaje podľa definície binárneho vyhľadávacieho stromu, tj. Ak sú údaje menšie ako nadradený uzol, umiestnia sa do ľavého podriadeného prvku a ak sú údaje väčšie ako nadradený uzol, potom bude to správne dieťa.

Tieto kroky sú uvedené nižšie.

# 2) 30

Strom binárneho vyhľadávania Krok 1 30

# 3) 60

Strom binárneho vyhľadávania Krok 2 60

# 4) 65

11 Binárny vyhľadávací strom, krok3

# 5) 70

Krok 4: Binárny vyhľadávací strom

Keď vykonáme inorder traversal na vyššie uvedenom BST, ktorý sme práve skonštruovali, postupnosť je nasledovná.

Poradie traversálnej sekvencie

Vidíme, že traverzová sekvencia má prvky usporiadané vzostupne.

Implementácia binárneho vyhľadávacieho stromu C ++

Ukážme si BST a jeho operácie pomocou implementácie 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):'<

Výkon:

Vytvorený binárny vyhľadávací strom (priechod v poradí):

30 40 60 65 70

Odstrániť uzol 40

Prechod v poradí pre upravený binárny vyhľadávací strom:

30 60 65 70

Vo vyššie uvedenom programe vydávame BST v poradí prechodu v poradí.

Výhody BST

# 1) Vyhľadávanie je veľmi efektívne

Všetky uzly BST máme v konkrétnom poradí, takže hľadanie konkrétnej položky je veľmi efektívne a rýchlejšie. Je to tak preto, lebo nemusíme prehľadávať celý strom a porovnávať všetky uzly.

Musíme iba porovnať koreňový uzol s položkou, ktorú hľadáme, a potom sa rozhodneme, či musíme hľadať v ľavom alebo pravom podstrome.

# 2) Efektívna práca v porovnaní s poliami a prepojenými zoznamami

Keď hľadáme položku v prípade BST, v každom kroku sa zbavíme polovice ľavého alebo pravého podstromu, čím sa zlepší výkonnosť vyhľadávacej operácie. To je na rozdiel od polí alebo prepojených zoznamov, v ktorých musíme postupne vyhľadávať všetky položky, aby sme vyhľadali konkrétnu položku.

# 3) Vloženie a odstránenie sú rýchlejšie

Operácie vkladania a mazania sú tiež rýchlejšie v porovnaní s inými dátovými štruktúrami, ako sú prepojené zoznamy a polia.

Aplikácie BST

Niektoré z hlavných aplikácií BST sú tieto:

  • BST sa používa na implementáciu viacúrovňového indexovania v databázových aplikáciách.
  • BST sa tiež používa na implementáciu konštrukcií ako slovník.
  • Pomocou BST je možné implementovať rôzne efektívne vyhľadávacie algoritmy.
  • BST sa tiež používa v aplikáciách, ktoré ako vstupy vyžadujú triedený zoznam, ako napríklad internetové obchody.
  • BST sa tiež používajú na hodnotenie výrazu pomocou stromov výrazu.

Záver

Binárne vyhľadávacie stromy (BST) sú variáciou binárneho stromu a sú široko používané v softvérovej oblasti. Tiež sa nazývajú usporiadané binárne stromy, pretože každý uzol v BST je umiestnený podľa konkrétneho poradia.

Inorder traversal of BST nám dáva zoradenú postupnosť položiek vo vzostupnom poradí. Keď sa na vyhľadávanie používajú BST, je to veľmi efektívne a je to hotové behom chvíľky. BST sa tiež používajú na rôzne aplikácie, ako je Huffmanovo kódovanie, viacúrovňové indexovanie v databázach atď.

=> Prečítajte si populárnu sériu školení C ++ tu.

Odporúčané čítanie

^