Binärt sökträd är en datastruktur som används inom datavetenskap för att organisera och lagra data på ett sorterat sätt. Binärt sökträd följer alla egenskaper hos binärt träd och dess vänster child innehåller värden mindre än den överordnade noden och höger barn innehåller värden som är större än den överordnade noden. Denna hierarkiska struktur möjliggör effektiv Sökande , Införande , och Radering operationer på data som lagras i trädet.
Binärt sökträd
Innehållsförteckning
- Vad är binärt sökträd?
- Egenskaper för binärt sökträd
- Hanterar dubbletter av värden i det binära sökträdet
- Operationer utförda på en BST
- 1. Söka efter en nod i BST
- 2. Infoga en nod i en BST
- 3. Ta bort en nod av BST
- 4. Traversal (Inorder traversal av BST)
- Tillämpningar av BST
- Fördelar
- Nackdelar
- FAQ (vanliga frågor) om binärt sökträd:
Vad är binärt sökträd?
Binärt sökträd (BST) är en speciell typ av binärt träd där det vänstra barnet i en nod har ett värde som är mindre än nodens värde och det högra barnet har ett värde som är större än nodens värde. Denna egenskap kallas BST-egenskapen och den gör det möjligt att effektivt söka, infoga och ta bort element i trädet.
Egenskaper för binärt sökträd:
- Det vänstra underträdet i en nod innehåller endast noder med nycklar som är mindre än nodens nyckel.
- Det högra underträdet i en nod innehåller endast noder med nycklar som är större än nodens nyckel.
- Detta betyder att allt till vänster om roten är mindre än rotens värde och allt till höger om roten är större än rotens värde. På grund av denna prestanda är en binär sökning mycket enkel.
- Det vänstra och högra underträdet måste också vara ett binärt sökträd.
- Det får inte finnas några dubbletter av noder (BST kan ha dubbletter av värden med olika hanteringsmetoder)
Hantera dubbletter av värden i det binära sökträdet:
- Vi måste följa en konsekvent process genomgående, det vill säga antingen lagra dubblettvärdet till vänster eller lagra dubblettvärdet till höger om roten, men vara konsekvent med ditt tillvägagångssätt.
Grundläggande funktioner på binärt sökträd:
1. Söka efter en nod i BST:
Att söka i BST innebär att lokalisera en specifik nod i datastrukturen. I binärt sökträd är det lätt att söka i en nod på grund av dess en specifik ordning. Stegen för att söka en nod i binärt sökträd listas enligt följande –
- Jämför först elementet som ska sökas med trädets rotelement.
- Om root matchas med målelementet returnerar du nodens plats.
- Om det inte matchas, kontrollera om objektet är mindre än rotelementet, om det är mindre än rotelementet, flytta sedan till det vänstra underträdet.
- Om det är större än rotelementet, flytta till höger underträd.
- Upprepa ovanstående procedur rekursivt tills matchningen hittas.
- Om elementet inte hittas eller inte finns i trädet, returnera NULL.
Låt oss nu förstå sökningen i binärt träd med ett exempel:
Nedan ges en BST och vi måste söka efter element 6.
Koda:
frågeväljare
Nedan är implementeringen av sökning i BST:
C++ // C++ function to search a given key in a given BST #include using namespace std; struct node { int key; struct node *left, *right; }; // A utility function to create a new BST node struct node* newNode(int item) { struct node* temp = new struct node; temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // En verktygsfunktion för att infoga // en ny nod med given nyckel i BST struct node* insert(struct node* node, int key) { // Om trädet är tomt, returnera en ny nod if (nod == NULL ) returnera nyNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) nod->vänster = infoga(nod->vänster, nyckel); annars if (nyckel> nod->nyckel) nod->höger = infoga(nod->höger, nyckel); // Returnera (oförändrad) nodpekarens returnod; } // Verktygsfunktion för att söka efter en nyckel i en BST struct node* search(struct node* root, int key) root->key == key) return root; // Key är större än roots nyckel if (root->key< key) return search(root->höger, nyckel); // Nyckeln är mindre än roots nyckelretursökning (root->vänster, nyckel);> C // C function to search a given key in a given BST #include #include struct node { int key; struct node *left, *right; }; // A utility function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // En verktygsfunktion för att infoga // en ny nod med given nyckel i BST struct node* insert(struct node* node, int key) { // Om trädet är tomt, returnera en ny nod if (nod == NULL ) returnera nyNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) nod->vänster = infoga(nod->vänster, nyckel); annars if (nyckel> nod->nyckel) nod->höger = infoga(nod->höger, nyckel); // Returnera (oförändrad) nodpekarens returnod; } // Verktygsfunktion för att söka efter en nyckel i en BST struct node* sökning(struct node* root, int key)> Java // Java program to search a given key in a given BST class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } class BinarySearchTree { Node root; // Constructor BinarySearchTree() { root = null; } // A utility function to insert // a new node with given key in BST Node insert(Node node, int key) { // If the tree is empty, return a new node if (node == null) { node = new Node(key); return node; } // Otherwise, recur down the tree if (key < node.key) node.left = insert(node.left, key); else if (key>node.key) node.right = infoga(nod.höger, nyckel); // Returnera (oförändrad) nodpekarens returnod; } // Verktygsfunktion för att söka efter en nyckel i en BST-nodsökning (nodrot, int-nyckel) // Basfall: root är null eller nyckel finns vid rot om (root == null> Pytonorm # Python3 function to search a given key in a given BST class Node: # Constructor to create a new node def __init__(self, key): self.key = key self.left = None self.right = None # A utility function to insert # a new node with the given key in BST def insert(node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key>node.key: node.right = infoga(nod.höger, nyckel) # Returnera (oförändrad) nodpekarens returnod # Verktygsfunktion för att söka efter en nyckel i en BST def-sökning(root, nyckel): # Basfall: roten är null eller nyckel finns vid root om root är None eller root.key == nyckel: returnera root # Key är större än roots nyckel om root.key< key: return search(root.right, key) # Key is smaller than root's key return search(root.left, key)>
JavaScript // Javascript function to search a given key in a given BST class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } // A utility function to insert // a new node with given key in BST function insert(node, key) { // If the tree is empty, return a new node if (node === null) { return new Node(key); } // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key>node.key) { node.right = infoga(nod.höger, nyckel); } // Returnera den (oförändrade) nodpekarens returnod; } // Verktygsfunktion för att söka efter en nyckel i en BST-funktionssökning(root, nyckel) { // Basfall: root är null eller nyckel finns vid root om (root === null || root.key === nyckel ) { returnera rot; } // Nyckeln är större än rotens nyckel if (root.key< key) { return search(root.right, key); } // Key is smaller than root's key return search(root.left, key); }>
2. Infoga en nod i en BST :
En ny nyckel sätts alltid in vid bladet. Börja söka efter en nyckel från roten till en lövnod. När en lövnod har hittats läggs den nya noden till som en underordnad lövnod.
Koda:
Nedan är implementeringen av infogningen av en enda nod i binärt sökträd:
C++ // Given Node Structure struct node { int key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // Funktion för att infoga en ny nod med // given nyckel i BST struct node* insert(struct node* node, int nyckel) { // Om trädet är tomt, returnera en ny nod if (nod == NULL) returnera newNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) { nod->vänster = infoga(nod->vänster, nyckel); } else if (nyckel> nod->nyckel) { nod->höger = insert(nod->höger, nyckel); } // Returnera nodpekaren returnod; }> C // Given Node Structure struct node { int key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // Funktion för att infoga en ny nod med // given nyckel i BST struct node* insert(struct node* node, int nyckel) { // Om trädet är tomt, returnera en ny nod if (nod == NULL) returnera newNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) { nod->vänster = infoga(nod->vänster, nyckel); } else if (nyckel> nod->nyckel) { nod->höger = insert(nod->höger, nyckel); } // Returnera nodpekaren returnod; }> Java class GFG { // Given Node Structure static class node { int key; node left, right; }; // Function to create a new BST node static node newNode(int item) { node temp = new node(); temp.key = item; temp.left = temp.right = null; return temp; } // Function to insert a new node with // given key in BST static node insert(node node, int key) { // If the tree is empty, return a new node if (node == null) return newNode(key); // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key>node.key) { node.right = infoga(nod.höger, nyckel); } // Returnera nodens returnod; } }> Python3 # Given Node Structure class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to insert a new node with # given key in BST def insert(node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key>node.key: node.right = infoga(nod.höger, nyckel) # Returnera nodpekaren returnod>
Javascript // Given Node Structure class Node { constructor(key){ this.key = key; this.left = null; this.right = null; } } // Function to insert a new node with // given key in BST function insert(node, key) { // If the tree is empty, return a new node if (node == null) return new Node(key); // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key>node.key) { node.right = infoga(nod.höger, nyckel); } // Returnera nodpekaren returnod; }> Tidskomplexitet: O(N), där N är antalet noder för BST
Hjälputrymme: O(1)
3. Ta bort en nod av BST :
Den används för att ta bort en nod med specifik nyckel från BST och returnera den nya BST.
Olika scenarier för att ta bort noden:
Nod som ska raderas är lövnoden :
Det är enkelt, du kan bara ta bort det.
Noden som ska raderas har ett barn :
Du kan bara ersätta noden med den underordnade noden.
Noden som ska raderas har två barn :
Här måste vi ta bort noden är ett sådant sätt att det resulterande trädet följer egenskaperna för en BST. Tricket är att hitta nodens efterföljare i ordningsföljd. Kopiera innehållet i inorderns efterföljare till noden och ta bort inorder efterföljaren.
Ta hand om följande saker när du tar bort en nod i en BST:
- Behöver ta reda på vad som kommer att ersätta noden som ska raderas.
- Vill ha minimala störningar på den befintliga trädstrukturen
- Kan ta ersättningsnoden från de borttagna noderna till vänster eller höger underträd.
- Om vi tar if från det vänstra underträdet, måste vi ta det största värdet i det vänstra underträdet.
- Om vi tar if från höger underträd, måste vi ta det minsta värdet i höger underträd.
Koda:
Nedan är implementeringen av raderingen i BST:
C++ // C++ program to delete // a node of BST // Given Node node struct node { int key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // Funktion för att infoga en ny nod med // given nyckel i BST struct node* insert(struct node* node, int nyckel) { // Om trädet är tomt, returnera en ny nod if (nod == NULL) returnera newNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) { nod->vänster = infoga(nod->vänster, nyckel); } else if (nyckel> nod->nyckel) { nod->höger = insert(nod->höger, nyckel); } // Returnera nodpekaren returnod; } // Funktion som returnerar noden med minsta // nyckelvärde som finns i det trädet struct node* minValueNode(struct node* node) { struct node* current = node; // Slinga ner för att hitta bladet längst till vänster medan (aktuell && ström->vänster != NULL) ström = ström->vänster; returström; } // Funktion som tar bort nyckeln och // returnerar den nya root struct noden* deleteNode(struct node* root, int key) { // base Case if (root == NULL) return root; // Om nyckeln som ska raderas är // mindre än rotens nyckel, // så ligger den i vänster underträd if (nyckel< root->key) { root->left = deleteNode(root->vänster, nyckel); } // Om nyckeln som ska raderas är // större än rotens nyckel, // så ligger den i höger underträd annars om (nyckel> root->nyckel) { root->right = deleteNode(root-> höger, nyckel); } // Om nyckeln är samma som rotnyckeln, // så är detta noden // som ska raderas annars { // Nod med endast ett barn // eller inget barn om (root->vänster == NULL) { struct node* temp = root->right; fri (rot); returtemp; } else if (root->right == NULL) { struct node* temp = root->left; fri (rot); returtemp; } // Nod med två barn: // Hämta inorderns efterföljare(minst // i det högra underträdet) struct node* temp = minValueNode(root->right); // Kopiera efterföljarens // innehåll till denna nod root->key = temp->key; // Ta bort ordningens efterföljare root->right = deleteNode(root->höger, temp->nyckel); } returnera rot; }> C // C program to delete // a node of BST // Given Node node struct node { int key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // Funktion för att infoga en ny nod med // given nyckel i BST struct node* insert(struct node* node, int nyckel) { // Om trädet är tomt, returnera en ny nod if (nod == NULL) returnera newNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) { nod->vänster = infoga(nod->vänster, nyckel); } else if (nyckel> nod->nyckel) { nod->höger = insert(nod->höger, nyckel); } // Returnera nodpekaren returnod; } // Funktion som returnerar noden med minsta // nyckelvärde som finns i det trädet struct node* minValueNode(struct node* node) { struct node* current = node; // Slinga ner för att hitta bladet längst till vänster medan (aktuell && ström->vänster != NULL) ström = ström->vänster; returström; } // Funktion som tar bort nyckeln och // returnerar den nya root struct noden* deleteNode(struct node* root, int key) { // base Case if (root == NULL) return root; // Om nyckeln som ska raderas är // mindre än rotens nyckel, // så ligger den i vänster underträd if (nyckel< root->key) { root->left = deleteNode(root->vänster, nyckel); } // Om nyckeln som ska raderas är // större än rotens nyckel, // så ligger den i höger underträd annars om (nyckel> root->nyckel) { root->right = deleteNode(root-> höger, nyckel); } // Om nyckeln är samma som rotnyckeln, // så är detta noden // som ska raderas annars { // Nod med endast ett barn // eller inget barn om (root->vänster == NULL) { struct node* temp = root->right; fri (rot); returtemp; } else if (root->right == NULL) { struct node* temp = root->left; fri (rot); returtemp; } // Nod med två barn: // Hämta inorderns efterföljare(minst // i det högra underträdet) struct node* temp = minValueNode(root->right); // Kopiera efterföljarens // innehåll till denna nod root->key = temp->key; // Ta bort ordningens efterföljare root->right = deleteNode(root->höger, temp->nyckel); } returnera rot; }> Java // Java program for Delete a Node of BST class GFG { // Given Node node static class node { int key; node left, right; }; // Function to create a new BST node static node newNode(int item) { node temp = new node(); temp.key = item; temp.left = temp.right = null; return temp; } // Function to insert a new node with // given key in BST static node insert(node node, int key) { // If the tree is empty, return a new node if (node == null) return newNode(key); // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key>node.key) { node.right = infoga(nod.höger, nyckel); } // Returnera nodens returnod; } // Funktion som returnerar noden med minsta // nyckelvärde som finns i det trädet statisk nod minValueNode(nod node) { node current = node; // Slinga ner för att hitta bladet längst till vänster medan (current != null && current.left != null) current = current.left; returström; } // Funktion som tar bort nyckeln och // returnerar den nya statiska rotnoden deleteNode(nodrot, int nyckel) { // base Case if (root == null) returnerar rot; // Om nyckeln som ska raderas är // mindre än rotens nyckel, // så ligger den i vänster underträd if (nyckel< root.key) { root.left = deleteNode(root.left, key); } // If the key to be deleted is // greater than the root's key, // then it lies in right subtree else if (key>root.key) { root.right = deleteNode(root.right, nyckel); } // Om nyckeln är samma som root's key, // så är detta noden // som ska raderas annars { // Nod med endast ett barn // eller inget barn if (root.left == null) { nod temp = root.right; returtemp; } else if (root.right == null) { node temp = root.left; returtemp; } // Nod med två barn: // Hämta inorderns efterföljare(minst // i det högra underträdet) node temp = minValueNode(root.right); // Kopiera efterföljarens // innehåll till denna nod root.key = temp.key; // Delete the inorder successor root.right = deleteNode(root.right, temp.key); } returnera rot; }> Pytonorm # Python program to delete a node of BST # Given Node node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to insert a new node with # given key in BST def insert(root, key): # If the tree is empty, return a new node if root is None: return Node(key) # Otherwise, recur down the tree if key < root.key: root.left = insert(root.left, key) elif key>root.key: root.right = insert(root.right, key) # Returnera nodpekaren returnera rot # Funktion för att göra inorderövergång av BST def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # Funktion som returnerar noden med minsta # nyckelvärde som finns i det trädet def minValueNode(nod): ström = nod # Slinga ner för att hitta bladet längst till vänster medan aktuella och current.left är inte None: current = current.left return current # Funktion som tar bort nyckeln och # returnerar den nya root def deleteNode(root, key): # base Case om root är None: return root # Om nyckeln som ska vara raderad är # mindre än rotens nyckel, # sedan ligger den i vänster underträd om nyckeln< root.key: root.left = deleteNode(root.left, key) # If the key to be deleted is # greater than the root's key, # then it lies in right subtree elif key>root.key: root.right = deleteNode(root.right, nyckel) # Om nyckeln är samma som root-nyckeln, # så är detta noden # som ska tas bort annars: # Nod med bara ett barn # eller inget barn om root.left är Ingen: temp = root.right root = Ingen retur temp elif root.right är Ingen: temp = root.left root = Ingen retur temp # Nod med två underordnade: # Få efterföljaren i ordningsföljden (minsta # i höger underträd) temp = minValueNode(root.right) # Kopiera efterföljarens # innehåll till denna nod root.key = temp.key # Ta bort efterföljaren root.right = deleteNode(root.right, temp.key) returnera root>
4. Traversal (Inorder traversal of BST) :
Vid binära sökträd (BST) ger Inorder-traversal noder i icke-minskande ordning. Vi besöker det vänstra barnet först, sedan roten och sedan det högra barnet.
Nedan är implementeringen av hur man gör ordningsgenomgång av ett binärt sökträd:
C++ // C++ program to implement // inorder traversal of BST #include using namespace std; // Given Node node struct node { int key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // Funktion för att infoga en ny nod med // given nyckel i BST struct node* insert(struct node* node, int nyckel) { // Om trädet är tomt, returnera en ny nod if (nod == NULL) returnera newNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) { nod->vänster = infoga(nod->vänster, nyckel); } else if (nyckel> nod->nyckel) { nod->höger = insert(nod->höger, nyckel); } // Returnera nodpekaren returnod; } // Funktion för att göra inorder-traversal av BST void inorder(struct node* root) { if (root != NULL) { inorder(root->left); cout<< ' ' << root->nyckel; inorder(root->höger); } } // Driver Code int main() { /* Låt oss skapa följande BST 50 / 30 70 / / 20 40 60 80 */ struct node* root = NULL; // Skapa BST-roten = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Funktion Anrop inorder(root); returnera 0; } // Denna kod är bidragit från shivanisinghss2110> C // C program to implement // inorder traversal of BST #include #include // Given Node node struct node { int key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->nyckel = objekt; temp->vänster = temp->höger = NULL; returtemp; } // Funktion för att infoga en ny nod med // given nyckel i BST struct node* insert(struct node* node, int nyckel) { // Om trädet är tomt, returnera en ny nod if (nod == NULL) returnera newNode(nyckel); // Annars återkommer du ner i trädet om (nyckel< node->nyckel) { nod->vänster = infoga(nod->vänster, nyckel); } else if (nyckel> nod->nyckel) { nod->höger = insert(nod->höger, nyckel); } // Returnera nodpekaren returnod; } // Funktion för att göra inorder-traversal av BST void inorder(struct node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->nyckel); inorder(root->höger); } } // Driver Code int main() { /* Låt oss skapa följande BST 50 / 30 70 / / 20 40 60 80 */ struct node* root = NULL; // Skapa BST-roten = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Funktion Anrop inorder(root); returnera 0; }> Java import java.io.*; // Java program for Inorder Traversal class GFG { // Given Node node static class node { int key; node left, right; }; // Function to create a new BST node static node newNode(int item) { node temp = new node(); temp.key = item; temp.left = temp.right = null; return temp; } // Function to insert a new node with // given key in BST static node insert(node node, int key) { // If the tree is empty, return a new node if (node == null) return newNode(key); // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key>node.key) { node.right = infoga(nod.höger, nyckel); } // Returnera nodens returnod; } // Funktion för att göra inorder-traversal av BST static void inorder(nodrot) { if (root != null) { inorder(root.left); System.out.print(' ' + root.key); inorder(root.right); } } // Driver Code public static void main(String[] args) { /* Låt oss skapa följande BST 50 / 30 70 / / 20 40 60 80 */ nodrot = null; // infogar värde 50 root = insert(root, 50); // infogar värde 30 insert(root, 30); // infogar värde 20 insert(root, 20); // infogar värde 40 insert(root, 40); // infogar värde 70 insert(root, 70); // infogar värde 60 insert(root, 60); // infogar värde 80 insert(root, 80); // skriv ut BST inorder(root); } } // Denna kod är bidragit av abhijitjadhav1998> Python3 # Python program to implement # inorder traversal of BST # Given Node node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to create a new BST node def newNode(item): temp = Node(item) temp.key = item temp.left = temp.right = None return temp # Function to insert a new node with # given key in BST def insert(node, key): # If the tree is empty, return a new node if node is None: return newNode(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key>node.key: node.right = infoga(nod.höger, nyckel) # Returnera nodpekarens returnod # Funktion för att göra inorderövergång av BST def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # Driver Code if __name__ == '__main__': # Låt oss skapa följande BST # 50 # / # 30 70 # / / # 20 40 60 80 root = Ingen # Skapar BST-roten = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 20) , 80) # Funktion Call inorder(root) #Denna kod är bidragit av japmeet01>
Produktion
20 30 40 50 60 70 80>
Tidskomplexitet: O(N), där N är antalet noder för BST
Hjälputrymme: O(1)
konvertera en sträng till heltal i java
Tillämpningar av BST:
- Grafalgoritmer: BST:er kan användas för att implementera grafalgoritmer, till exempel i algoritmer för minimum spaning tree.
- Prioriterade köer: BST kan användas för att implementera prioritetsköer, där elementet med högst prioritet är i roten av trädet, och element med lägre prioritet lagras i underträden.
- Självbalanserande binärt sökträd: BST kan användas som en självbalanserande datastruktur som AVL-träd och Röd-svart träd.
- Datalagring och hämtning: BST kan användas för att lagra och hämta data snabbt, till exempel i databaser, där sökning efter en specifik post kan göras i logaritmisk tid.
Fördelar:
- Snabb sökning: Att söka efter ett specifikt värde i en BST har en genomsnittlig tidskomplexitet på O(log n), där n är antalet noder i trädet. Detta är mycket snabbare än att söka efter ett element i en array eller länkad lista, som har en tidskomplexitet på O(n) i värsta fall.
- Genomgång i ordning: BST kan passeras i ordning, vilket besöker det vänstra underträdet, roten och det högra underträdet. Detta kan användas för att sortera en datauppsättning.
- Utrymmeseffektiv: BST:er är utrymmeseffektiva eftersom de inte lagrar någon redundant information, till skillnad från arrayer och länkade listor.
Nackdelar:
- Skeva träd: Om ett träd blir skevt blir tidskomplexiteten för sökning, infogning och radering O(n) istället för O(log n), vilket kan göra trädet ineffektivt.
- Ytterligare tid som krävs: Självbalanserande träd kräver ytterligare tid för att upprätthålla balansen under insättnings- och raderingsoperationer.
- Effektivitet: BST:er är inte effektiva för datauppsättningar med många dubbletter eftersom de kommer att slösa utrymme.
FAQ(Vanliga frågor)på binärt sökträd:
1. Vad är ett binärt sökträd?
Ett binärt sökträd (BST) är ett binärt träd där varje nod i det vänstra underträdet är mindre än roten, och varje nod i det högra underträdet har ett värde som är större än roten . Egenskaperna för ett binärt sökträd är rekursiva: om vi betraktar någon nod som en rot kommer dessa egenskaper att förbli sanna.
2. Vad är det binära sökträdet?
Det finns tre stora operationer i Binary Search Tree: 1. Infogning, 2. Radering, 3. Sökning. På grund av dess egenskaper är det effektivt att söka i alla element i Binary Search Tree.
3. Vad är binärt sökträd och AVL-träd?
Binärt sökträd : Ett binärt sökträd (BST) är ett binärt träd där varje nod i det vänstra underträdet är mindre än roten, och varje nod i det högra underträdet har ett värde som är större än roten.
AVL-träd : Binära sökträd (BST) som självbalanserar och roterar automatiskt kallas AVL-träd.
4. Vad är användningen av Binary Search Tree?
Binära sökträd kan användas för att implementera abstrakta datatyper som t.ex dynamiska uppsättningar, uppslagstabeller och prioritetsköer, och används i sorteringsalgoritmer såsom trädsortering.
5. Vad är skillnaden mellan binärt sökträd och binärt träd?
Ett binärt sökträd är ett träd som följer någon ordning för att ordna elementen, medan det binära trädet inte följer någon ordning.
Relaterade artiklar:
- Tillämpning av BST
- Tillämpningar, fördelar och nackdelar med Binary Search Tree
- Infogning i binärt sökträd (BST)
- Söka i binärt sökträd (BST)
- Borttagning i binärt sökträd (BST)