Menu

Binární vyhledávací strom C ++: Implementace a operace BST s příklady

  • Hlavní
  • Jiný
  • Binární vyhledávací strom C ++: Implementace a operace BST s příklady

binary search tree c

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Podrobný výukový program o binárním vyhledávacím stromu (BST) v C ++ včetně operací, implementace C ++, výhod a příkladových programů:

Binární vyhledávací strom nebo BST, jak se běžně nazývá, je binární strom, který splňuje následující podmínky:

  1. Uzly, které jsou menší než kořenový uzel, který je umístěn jako levé děti BST.
  2. Uzly, které jsou větší než kořenový uzel, který je umístěn jako správné děti BST.
  3. Levý a pravý podstrom jsou zase binárními vyhledávacími stromy.

Toto uspořádání uspořádání klíčů v určitém pořadí usnadňuje programátorovi efektivnější provádění operací, jako je vyhledávání, vkládání, mazání atd. Pokud uzly nejsou objednány, možná budeme muset porovnat každý uzel, než můžeme získat výsledek operace.

=> Podívejte se na kompletní sérii školení C ++ zde.

Binární vyhledávací strom v C ++

Co se naučíte:

Binární vyhledávací strom C ++

Ukázkový BST je uveden níže.

Ukázka BST

Binární vyhledávací stromy jsou také kvůli tomuto specifickému uspořádání uzlů označovány jako „uspořádané binární stromy“.

Z výše uvedeného BST vidíme, že levý podstrom má uzly, které jsou menší než kořen, tj. 45, zatímco pravý podstrom má uzly, které jsou větší než 45.

Nyní pojďme diskutovat o některých základních operacích BST.

Základní operace

# 1) Vložit

Operace vložení přidá nový uzel do binárního vyhledávacího stromu.

Algoritmus pro operaci vložení binárního vyhledávacího stromu je uveden níže.

model životního cyklu v softwarovém inženýrství
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

Jak ukazuje výše uvedený algoritmus, musíme zajistit, aby byl uzel umístěn na vhodné pozici, abychom neporušili pořadí BST.

Vložit operaci v BST

Jak vidíme ve výše uvedené posloupnosti diagramů, provedeme řadu operací vložení. Po porovnání klíče, který má být vložen s kořenovým uzlem, je vybrán levý nebo pravý podstrom pro klíč, který má být vložen jako listový uzel na příslušné pozici.

# 2) Smazat

Operace odstranění odstraní uzel, který odpovídá danému klíči z BST. I v této operaci musíme po odstranění přemístit zbývající uzly, aby nedošlo k porušení objednávky BST.

Proto v závislosti na tom, který uzel musíme odstranit, máme v BST následující případy odstranění:

# 1) Když je uzel Leaf Node

Když je uzel, který má být odstraněn, uzel listu, pak uzel přímo odstraníme.

Uzel je listový uzel

# 2) Když má uzel pouze jedno dítě

Pokud má uzel, který má být odstraněn, pouze jedno podřízené zařízení, zkopírujeme podřízený objekt do uzlu a podřízený objekt odstraníme.

Uzel má pouze jedno dítě

# 3) Když má uzel dvě děti

Pokud má uzel, který má být odstraněn, dvě podřízené položky, najdeme inorderového následníka pro uzel a potom zkopírujeme inorderového následníka do uzlu. Později odstraníme nástupce inorder.

Node má dvě děti

Ve výše uvedeném stromu k odstranění uzlu 6 se dvěma podřízenými položkami nejprve najdeme inorderového následníka pro tento uzel, který má být odstraněn. Nástupce inorder najdeme nalezením minimální hodnoty ve správném podstromu. Ve výše uvedeném případě je minimální hodnota 7 v pravém podstromu. Zkopírujeme to do uzlu, který má být odstraněn, a potom odstraníme následníka inorder.

# 3) Hledat

Vyhledávací operace BST vyhledá konkrétní položku označenou jako „klíč“ v BST. Výhodou hledání položky v BST je, že nemusíme prohledávat celý strom. Místo toho kvůli objednání v BST jsme pouze porovnali klíč s rootem.

Pokud je klíč stejný jako root, vrátíme root. Pokud klíč není root, porovnáme jej s rootem, abychom zjistili, zda potřebujeme prohledat levý nebo pravý podstrom. Jakmile najdeme podstrom, musíme prohledat klíč a rekurzivně jej vyhledat v kterémkoli z podstromů.

Následuje algoritmus pro vyhledávací operaci 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

Vyhledávací operace v BST

Pokud chceme ve výše uvedeném stromu hledat klíč s hodnotou 6, nejprve porovnáme klíč s kořenovým uzlem, tj. If (6 == 7) => Ne if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Dále sestupujeme k levému dílčímu stromu. Pokud (6 == 5) => Ne

Pokud (6 Ne; to znamená 6> 5 a musíme se pohnout doprava.

If (6 == 6) => Ano; klíč je nalezen.

# 4) Traversals

Už jsme diskutovali o procházení binárního stromu. I v případě BST můžeme strom procházet, abychom získali sekvenci InOrder, Preorder nebo PostOrder. Ve skutečnosti, když procházíme BST v sekvenci Inorder01, dostaneme seřazenou sekvenci.

Ukázali jsme to na níže uvedeném obrázku.

procházení

Traverzy pro výše uvedený strom jsou následující:

Traversal inorder (lnr): 3 5 6 7 8 9 10
Předobjednat traversal (nlr): 7 5 3 6 9 8 10
Přechod po objednávce (lrn): 3 6 5 8 10 9 7

Ilustrace

Vytvořme binární vyhledávací strom z níže uvedených údajů.

45 30 60 65 70

Vezměme první prvek jako kořenový uzel.

# 1) 45

kořenový uzel

V následujících krocích umístíme data podle definice stromu Binárního vyhledávání, tj. Pokud jsou data menší než nadřazený uzel, budou umístěna na levé podřízené a pokud jsou data větší než nadřazený uzel, pak bude tím správným dítětem.

Tyto kroky jsou uvedeny níže.

# 2) 30

Strom binárního vyhledávání Krok 1 30

# 3) 60

Strom binárního vyhledávání Krok 2 60

# 4) 65

11 Binární vyhledávací strom krok 3

# 5) 70

Krok 4: Binární vyhledávací strom

Když provádíme inorder traversal na výše uvedeném BST, který jsme právě zkonstruovali, je sekvence následující.

Pořadí traversální sekvence

Vidíme, že traverzová sekvence má prvky uspořádané vzestupně.

Implementace binárního stromu vyhledávání C ++

Pojďme si předvést BST a jeho operace pomocí implementace 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ýstup:

Vytvořen binární vyhledávací strom (procházení Inorder):

30 40 60 65 70

Odstranit uzel 40

Přechod v pořadí pro upravený binární vyhledávací strom:

30 60 65 70

Ve výše uvedeném programu vydáváme BST pro in-order traversal sled.

kde je bezpečnostní klíč na routeru

Výhody BST

# 1) Hledání je velmi efektivní

Máme všechny uzly BST v určitém pořadí, a proto je vyhledávání konkrétní položky velmi efektivní a rychlejší. Je to proto, že nemusíme prohledávat celý strom a porovnávat všechny uzly.

Musíme pouze porovnat kořenový uzel s položkou, kterou hledáme, a poté se rozhodneme, zda musíme hledat v levém nebo pravém podstromu.

# 2) Efektivní práce ve srovnání s poli a propojenými seznamy

Když prohledáváme položku v případě BST, zbavíme se v každém kroku poloviny levého nebo pravého podstromu, čímž se zlepší výkon vyhledávací operace. To je na rozdíl od polí nebo propojených seznamů, ve kterých potřebujeme sekvenčně porovnat všechny položky, abychom prohledali konkrétní položku.

# 3) Vkládání a mazání je rychlejší

Operace vkládání a mazání jsou také rychlejší ve srovnání s jinými datovými strukturami, jako jsou propojené seznamy a pole.

Aplikace BST

Některé z hlavních aplikací BST jsou následující:

  • BST se používá k implementaci víceúrovňového indexování v databázových aplikacích.
  • BST se také používá k implementaci konstrukcí, jako je slovník.
  • BST lze použít k implementaci různých efektivních vyhledávacích algoritmů.
  • BST se také používá v aplikacích, které jako vstupy vyžadují seřazený seznam, jako jsou online obchody.
  • BST se také používají k vyhodnocení výrazu pomocí stromů výrazů.

Závěr

Binární vyhledávací stromy (BST) jsou variací binárního stromu a jsou široce používány v oblasti softwaru. Nazývají se také objednané binární stromy, protože každý uzel v BST je umístěn podle konkrétního pořadí.

Inorder traversal of BST nám dává seřazené pořadí položek ve vzestupném pořadí. Když se pro vyhledávání používají BST, je to velmi efektivní a je to hotové během chvilky. BST se také používají pro různé aplikace, jako je Huffmanovo kódování, víceúrovňové indexování v databázích atd.

=> Přečtěte si zde populární sérii školení C ++.

Doporučené čtení

^