Menu

Drzewo wyszukiwania binarnego C ++: Implementacja BST i operacje na przykładach

  • Główny
  • Inny
  • Drzewo wyszukiwania binarnego C ++: Implementacja BST i operacje na przykładach

binary search tree c

Szczegółowy samouczek dotyczący drzewa wyszukiwania binarnego (BST) w C ++, w tym operacje, implementacja C ++, zalety i przykładowe programy:

Drzewo wyszukiwania binarnego lub BST, jak jest popularnie nazywane, to drzewo binarne, które spełnia następujące warunki:

  1. Węzły mniejsze niż węzeł główny, który jest umieszczony jako lewe dziecko BST.
  2. Węzły, które są większe niż węzeł główny, który jest umieszczony jako prawe dziecko BST.
  3. Z kolei lewe i prawe poddrzewo to drzewa wyszukiwania binarnego.

Takie uporządkowanie kluczy w określonej kolejności ułatwia programiście wydajniejsze wykonywanie operacji, takich jak wyszukiwanie, wstawianie, usuwanie itp. Jeśli węzły nie są uporządkowane, może być konieczne porównanie każdego węzła, zanim będziemy mogli uzyskać wynik operacji.

=> Sprawdź całą serię szkoleń C ++ tutaj.

Drzewo wyszukiwania binarnego w C ++

Czego się nauczysz:

Drzewo wyszukiwania binarnego C ++

Przykładowy BST pokazano poniżej.

Przykładowy BST

różnica między przekierowaniem portu a wyzwalaczem portu

Drzewa wyszukiwania binarnego są również nazywane „uporządkowanymi drzewami binarnymi” z powodu tej szczególnej kolejności węzłów.

Z powyższego BST widzimy, że lewe poddrzewo ma węzły mniejsze niż korzeń, tj. 45, podczas gdy prawe poddrzewo ma węzły większe niż 45.

Omówmy teraz kilka podstawowych operacji BST.

Podstawowe operacje

# 1) Wstaw

Operacja wstawiania dodaje nowy węzeł w drzewie wyszukiwania binarnego.

Algorytm operacji wstawiania drzewa wyszukiwania binarnego jest podany poniżej.

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 pokazano w powyższym algorytmie, musimy upewnić się, że węzeł jest umieszczony w odpowiedniej pozycji, aby nie naruszyć kolejności BST.

Operacja wstawiania w BST

Jak widać na powyższej sekwencji diagramów, wykonujemy serię operacji wstawiania. Po porównaniu klucza, który ma być wstawiony, z węzłem głównym, wybierane jest lewe lub prawe poddrzewo dla klucza, który ma być wstawiony jako węzeł liścia w odpowiedniej pozycji.

# 2) Usuń

Operacja usuwania usuwa węzeł, który pasuje do danego klucza z BST. W tej operacji również musimy zmienić położenie pozostałych węzłów po usunięciu, aby kolejność BST nie została naruszona.

Dlatego w zależności od tego, który węzeł musimy usunąć, mamy następujące przypadki usunięcia w BST:

# 1) Gdy węzeł jest węzłem liściastym

Kiedy usuwany węzeł jest węzłem liścia, wówczas bezpośrednio usuwamy węzeł.

Węzeł jest węzłem liścia

# 2) Gdy węzeł ma tylko jedno dziecko

Kiedy usuwany węzeł ma tylko jedno dziecko, wtedy kopiujemy dziecko do węzła i usuwamy dziecko.

Węzeł ma tylko jedno dziecko

# 3) Kiedy węzeł ma dwoje dzieci

Jeśli usuwany węzeł ma dwoje dzieci, znajdujemy następcę w kolejności węzła, a następnie kopiujemy następcę w kolejności do węzła. Później usuwamy następcę w kolejności.

Węzeł ma dwoje dzieci

W powyższym drzewie, aby usunąć węzeł 6 z dwojgiem dzieci, najpierw znajdujemy następcę w kolejności dla tego węzła, który ma zostać usunięty. Następcę wewnętrznego znajdujemy, znajdując wartość minimalną w prawym poddrzewie. W powyższym przypadku minimalna wartość to 7 w prawym poddrzewie. Kopiujemy go do węzła, który ma zostać usunięty, a następnie usuwamy następcę w kolejności.

# 3) Szukaj

Operacja wyszukiwania BST wyszukuje konkretną pozycję zidentyfikowaną jako „klucz” w BST. Zaletą wyszukiwania elementu w BST jest to, że nie musimy przeszukiwać całego drzewa. Zamiast tego ze względu na kolejność w BST, po prostu porównujemy klucz z korzeniem.

Jeśli klucz jest taki sam jak root, zwracamy root. Jeśli klucz nie jest rootem, porównujemy go z korzeniem, aby określić, czy musimy przeszukać lewe czy prawe poddrzewo. Gdy już znajdziemy poddrzewo, musimy przeszukać klucz w nim i rekurencyjnie wyszukać go w jednym z poddrzew.

Poniżej przedstawiono algorytm operacji wyszukiwania w 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

Operacja wyszukiwania w BST

Jeśli chcemy wyszukać klucz o wartości 6 w powyższym drzewie, to najpierw porównujemy klucz z węzłem głównym, czyli jeśli (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.

Następnie schodzimy do lewego poddrzewa. Jeśli (6 == 5) => Nie.

Jeśli (6 Nie; oznacza to 6> 5 i musimy iść w prawo.

Jeśli (6 == 6) => Tak; klucz został znaleziony.

# 4) Przemieszczenia

Omówiliśmy już przejścia dla drzewa binarnego. Również w przypadku BST możemy przejść przez drzewo, aby uzyskać sekwencję inOrder, preorder lub postOrder. W rzeczywistości, kiedy przechodzimy przez BST w sekwencji Inorder01, otrzymujemy posortowaną sekwencję.

Pokazaliśmy to na poniższej ilustracji.

przechodzenie

Przejścia dla powyższego drzewa są następujące:

Przechodzenie wewnętrzne (lnr): 3 5 6 7 8 9 10
Przechodzenie w przedsprzedaży (nlr): 7 5 3 6 9 8 10
Przechodzenie przez PostOrder (lrn): 3 6 5 8 10 9 7

Ilustracja

Skonstruujmy drzewo wyszukiwania binarnego z danych podanych poniżej.

45 30 60 65 70

Weźmy pierwszy element jako węzeł główny.

# 1) 45

Węzeł główny

W kolejnych krokach umieścimy dane zgodnie z definicją drzewa wyszukiwania binarnego tj. Jeśli dane są mniejsze niż węzeł nadrzędny, to zostaną umieszczone w lewym będzie właściwym dzieckiem.

Te kroki przedstawiono poniżej.

# 2) 30

Drzewo wyszukiwania binarnego Krok 1 30

# 3) 60

Drzewo wyszukiwania binarnego Krok 2 60

# 4) 65

11 Krok drzewa wyszukiwania binarnego 3

# 5) 70

Krok 4 drzewa wyszukiwania binarnego

Kiedy wykonujemy przechodzenie w kolejności na powyższym BST, który właśnie skonstruowaliśmy, sekwencja jest następująca.

bezpłatna aplikacja z kartą czasu na iPhone'a i Androida

Wewnętrzna sekwencja przechodzenia

Widzimy, że sekwencja przejścia ma elementy ułożone w porządku rosnącym.

Implementacja drzewa wyszukiwania binarnego C ++

Pozwól nam zademonstrować BST i jego działanie w implementacji 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):'<

Wynik:

Utworzono drzewo wyszukiwania binarnego (przechodzenie w kolejności):

30 40 60 65 70

Usuń węzeł 40

Przechodzenie w kolejności dla zmodyfikowanego drzewa wyszukiwania binarnego:

30 60 65 70

W powyższym programie wyprowadzamy BST dla kolejności przechodzenia w kolejności.

Zalety BST

1) Wyszukiwanie jest bardzo wydajne

Mamy wszystkie węzły BST w określonej kolejności, stąd wyszukiwanie konkretnego elementu jest bardzo wydajne i szybsze. Dzieje się tak, ponieważ nie musimy przeszukiwać całego drzewa i porównywać wszystkich węzłów.

Musimy tylko porównać węzeł główny z szukanym elementem, a następnie zdecydujemy, czy musimy szukać w lewym czy prawym poddrzewie.

# 2) Wydajna praca w porównaniu z tablicami i połączonymi listami

Kiedy szukamy elementu w przypadku BST, na każdym kroku pozbywamy się połowy lewego lub prawego poddrzewa, poprawiając tym samym wydajność operacji wyszukiwania. Inaczej jest w przypadku tablic lub list połączonych, w których musimy kolejno porównywać wszystkie elementy, aby wyszukać konkretny element.

# 3) Wstawianie i usuwanie jest szybsze

Operacje wstawiania i usuwania są również szybsze w porównaniu z innymi strukturami danych, takimi jak połączone listy i tablice.

Zastosowania BST

Oto niektóre z głównych zastosowań BST:

  • BST służy do implementacji wielopoziomowego indeksowania w aplikacjach bazodanowych.
  • BST jest również używany do implementacji konstrukcji, takich jak słownik.
  • BST może być używany do implementacji różnych wydajnych algorytmów wyszukiwania.
  • BST jest również używany w aplikacjach, które wymagają posortowanej listy jako danych wejściowych, takich jak sklepy internetowe.
  • BST są również używane do oceny wyrażenia przy użyciu drzew wyrażeń.

Wniosek

Drzewa wyszukiwania binarnego (BST) są odmianą drzewa binarnego i są szeroko stosowane w dziedzinie oprogramowania. Nazywa się je również uporządkowanymi drzewami binarnymi, ponieważ każdy węzeł w BST jest umieszczony w określonej kolejności.

Przechodzenie w kolejności przez BST daje nam posortowaną sekwencję elementów w porządku rosnącym. Kiedy BST są używane do wyszukiwania, jest to bardzo wydajne i odbywa się w krótkim czasie. BST są również używane do różnych zastosowań, takich jak kodowanie Huffmana, wielopoziomowe indeksowanie w bazach danych itp.

=> Przeczytaj popularne serie szkoleń C ++ tutaj.

rekomendowane lektury

^