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:
- Węzły mniejsze niż węzeł główny, który jest umieszczony jako lewe dziecko BST.
- Węzły, które są większe niż węzeł główny, który jest umieszczony jako prawe dziecko BST.
- 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.
Czego się nauczysz:
- Drzewo wyszukiwania binarnego C ++
- Podstawowe operacje
- Implementacja drzewa wyszukiwania binarnego C ++
- Zalety BST
- Zastosowania BST
- Wniosek
- rekomendowane lektury
Drzewo wyszukiwania binarnego C ++
Przykładowy BST pokazano poniżej.
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; endJak pokazano w powyższym algorytmie, musimy upewnić się, że węzeł jest umieszczony w odpowiedniej pozycji, aby nie naruszyć kolejności 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ł.
# 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.
# 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 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 
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.
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 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
# 3) 60
# 4) 65
# 5) 70
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
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
- Struktura danych drzewa binarnego w C ++
- Struktura danych drzewa AVL i sterty w C ++
- Struktura danych B Tree i B + Tree w C ++
- Podstawowe operacje wejścia / wyjścia w C ++
- Podstawowe operacje we / wy w języku Java (strumienie wejścia / wyjścia)
- Drzewa w C ++: podstawowa terminologia, techniki przechodzenia i typy drzew w C ++
- Operacje na plikach i danych wyjściowych w C ++
- Wskaźniki i operacje na wskaźnikach w C ++