logo

TechCodeview

Introduksjon til binært søketre – datastruktur og algoritmeopplæring

Binært søketre er en datastruktur som brukes i informatikk for å organisere og lagre data på en sortert måte. Binært søketre følger alle egenskapene til binært tre og dets venstre barn inneholder verdier som er mindre enn den overordnede noden og Ikke sant barn inneholder verdier som er større enn den overordnede noden. Denne hierarkiske strukturen tillater effektiv Søker , Innsetting , og Sletting operasjoner på dataene som er lagret i treet.

Binært søketre




java-oppføring

Innholdsfortegnelse

Hva er binært søketre?

Binært søketre (BST) er en spesiell type binært tre der venstre underordnede av en node har en verdi mindre enn nodens verdi og høyre underordnede har en verdi som er større enn nodens verdi. Denne egenskapen kalles BST-egenskapen og den gjør det mulig å effektivt søke, sette inn og slette elementer i treet.



Egenskaper til binært søketre:

  • Det venstre undertreet til en node inneholder kun noder med nøkler som er mindre enn nodens nøkkel.
  • Det høyre undertreet til en node inneholder bare noder med nøkler som er større enn nodens nøkkel.
  • Dette betyr at alt til venstre for roten er mindre enn verdien av roten og alt til høyre for roten er større enn verdien av roten. På grunn av denne ytelsen er et binært søk veldig enkelt.
  • Det venstre og høyre undertreet må også være et binært søketre.
  • Det må ikke være dupliserte noder (BST kan ha dupliserte verdier med forskjellige håndteringsmetoder)

Håndtering av dupliserte verdier i det binære søketreet:

  • Vi må følge en konsistent prosess gjennom, dvs. enten lagre duplikatverdien til venstre eller lagre duplikatverdien til høyre for roten, men være konsekvent med din tilnærming.

Grunnleggende operasjoner på binært søketre:

1. Søke en node i BST:

Å søke i BST betyr å finne en bestemt node i datastrukturen. I binært søketre er det enkelt å søke i en node på grunn av dens en spesifikk rekkefølge. Trinnene for å søke en node i binært søketre er oppført som følger -

  1. Sammenlign først elementet som skal søkes med rotelementet til treet.
    • Hvis root matches med målelementet, returnerer du nodens plassering.
    • Hvis det ikke samsvarer, sjekk om elementet er mindre enn rotelementet, hvis det er mindre enn rotelementet, flytt deretter til venstre undertreet.
    • Hvis det er større enn rotelementet, så flytt til høyre undertreet.
  2. Gjenta prosedyren ovenfor rekursivt til matchen er funnet.
  3. Hvis elementet ikke finnes eller ikke finnes i treet, returnerer du NULL.

La oss nå forstå søket i binært tre ved å bruke et eksempel:

Nedenfor er gitt en BST og vi må søke etter element 6.




Kode:

Nedenfor er implementeringen av søk i BST:

10 av 10
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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // En verktøyfunksjon for å sette inn // en ny node med gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node if (node ​​== NULL ) returner nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) node->venstre = insert(node->venstre, nøkkel);  else if (nøkkel> node->nøkkel) node->høyre = insert(node->høyre, nøkkel);  // Returner den (uendrede) nodepekeren returnoden; } // Verktøyfunksjon for å søke etter en nøkkel i en BST struct node* search(struct node* root, int key) root->key == key) return root;  // Key er større enn roots nøkkel if (root->key< key)  return search(root->høyre, nøkkel);  // Key er mindre enn roots nøkkelretursøk(root->venstre, nøkkel);>
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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // En verktøyfunksjon for å sette inn // en ny node med gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node if (node ​​== NULL ) returner nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) node->venstre = insert(node->venstre, nøkkel);  else if (nøkkel> node->nøkkel) node->høyre = insert(node->høyre, nøkkel);  // Returner den (uendrede) nodepekeren returnoden; } // Verktøyfunksjon for å søke etter en nøkkel i en BST struct node* søk(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 = insert(node.right, key);  // Returner den (uendrede) nodepekeren returnoden;  } // Utility-funksjon for å søke etter en nøkkel i et BST-nodesøk(Node-rot, int-nøkkel) // Grunntilfeller: roten er null eller nøkkelen er til stede ved roten hvis (root == null>
Python 
# 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 = insert(node.right, key) # Returner (uendret) nodepeker returnode # Utility-funksjon for å søke etter en nøkkel i et BST def search(root, key): # Grunntilfeller: root er null eller nøkkel er tilstede ved root hvis root er Ingen eller root.key == nøkkel: returner root # Key er større enn roots nøkkel hvis 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 = insert(node.right, key); } // Returner den (uendrede) nodepekeren returnoden; } // Utility-funksjon for å søke etter en nøkkel i et BST-funksjonssøk(root, key) { // Grunntilfeller: root er null eller nøkkel er til stede ved root if (root === null || root.key === nøkkel ) { returner rot; } // Nøkkelen er større enn rotens nøkkel if (root.key< key) {  return search(root.right, key); } // Key is smaller than root's key return search(root.left, key); }>


2. Sett inn en node i en BST :

En ny nøkkel settes alltid inn ved bladet. Begynn å søke etter en nøkkel fra roten til en bladnode. Når en bladnode er funnet, legges den nye noden til som et barn av bladnoden.


Kode:

Nedenfor er implementeringen av innsetting av en enkelt node i binært søketre:

konverter streng int java
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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // Funksjon for å sette inn en ny node med // gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node hvis (node ​​== NULL) returnerer nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) { node->venstre = insert(node->venstre, nøkkel);  } else if (nøkkel> node->nøkkel) { node->høyre = insert(node->høyre, nøkkel);  } // Returner nodepekeren returnode; }>
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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // Funksjon for å sette inn en ny node med // gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node hvis (node ​​== NULL) returnerer nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) { node->venstre = insert(node->venstre, nøkkel);  } else if (nøkkel> node->nøkkel) { node->høyre = insert(node->høyre, nøkkel);  } // Returner nodepekeren returnode; }>
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 = insert(node.right, key);  } // Returner noden returnoden;  } }>
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 = insert(node.right, key) # Returner nodepekeren returnode>
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 = insert(node.right, key);  } // Returner nodepekeren returnode; }>

Tidskompleksitet: O(N), hvor N er antall noder til BST
Hjelpeplass: O(1)

3. Slett en node av BST :

Den brukes til å slette en node med spesifikk nøkkel fra BST og returnere den nye BST.

Ulike scenarier for å slette noden:

Node som skal slettes er bladnoden :

Det er enkelt, du kan bare slette det.

d1

Noden som skal slettes har ett barn :

Du kan bare erstatte noden med barnenoden.

fil

Noden som skal slettes har to barn :

Her må vi slette noden er slik at det resulterende treet følger egenskapene til en BST. Trikset er å finne nodens etterfølger i rekkefølge. Kopier innholdet av inorder-etterfølgeren til noden, og slett inorder-etterfølgeren.

d3

Ta vare på følgende ting mens du sletter en node til en BST:

  1. Trenger å finne ut hva som skal erstatte noden som skal slettes.
  2. Ønsker minimal forstyrrelse av eksisterende trestruktur
  3. Kan ta erstatningsnoden fra de slettede nodene venstre eller høyre undertre.
  4. Hvis vi tar hvis fra venstre undertre, må vi ta den største verdien i venstre undertre.
  5. Hvis vi tar hvis fra høyre undertre, må vi ta den minste verdien i høyre undertre.

Kode:

Nedenfor er implementeringen av slettingen i BST:

css opasitet overgang
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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // Funksjon for å sette inn en ny node med // gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node hvis (node ​​== NULL) returnerer nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) { node->venstre = insert(node->venstre, nøkkel);  } else if (nøkkel> node->nøkkel) { node->høyre = insert(node->høyre, nøkkel);  } // Returner nodepekeren returnode; } // Funksjon som returnerer noden med minimum // nøkkelverdi funnet i det treet struct node* minValueNode(struct node* node) { struct node* current = node;  // Loop ned for å finne bladet lengst til venstre mens (gjeldende && strøm->venstre != NULL) strøm = strøm->venstre;  returstrøm; } // Funksjon som sletter nøkkelen og // returnerer den nye root struct node* deleteNode(struct node* root, int key) { // base Case if (root == NULL) return root;  // Hvis nøkkelen som skal slettes er // mindre enn rotens nøkkel, // ligger den i venstre undertre if (nøkkel< root->key) { root->venstre = deleteNode(root->venstre, nøkkel);  } // Hvis nøkkelen som skal slettes er // større enn rotens nøkkel, // ligger den i høyre undertre else if (nøkkel> rot->nøkkel) { root->right = deleteNode(root-> høyre, nøkkel);  } // Hvis nøkkelen er den samme som rotnøkkelen, // så er dette noden // som skal slettes ellers { // Node med bare ett barn // eller ingen underordnet hvis (root->venstre == NULL) { struct node* temp = root->right;  gratis(root);  retur temp;  } else if (rot->høyre == NULL) { struct node* temp = rot->venstre;  gratis(root);  retur temp;  } // Node med to barn: // Få rekkefølgen etterfølgeren(minste // i høyre undertre) struct node* temp = minValueNode(root->right);  // Kopier etterfølgerens // innhold til denne noden root->key = temp->key;  // Delete the inorder successor root->right = deleteNode(root->right, temp->key);  } returner 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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // Funksjon for å sette inn en ny node med // gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node hvis (node ​​== NULL) returnerer nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) { node->venstre = insert(node->venstre, nøkkel);  } else if (nøkkel> node->nøkkel) { node->høyre = insert(node->høyre, nøkkel);  } // Returner nodepekeren returnode; } // Funksjon som returnerer noden med minimum // nøkkelverdi funnet i det treet struct node* minValueNode(struct node* node) { struct node* current = node;  // Loop ned for å finne bladet lengst til venstre mens (gjeldende && strøm->venstre != NULL) strøm = strøm->venstre;  returstrøm; } // Funksjon som sletter nøkkelen og // returnerer den nye root struct node* deleteNode(struct node* root, int key) { // base Case if (root == NULL) return root;  // Hvis nøkkelen som skal slettes er // mindre enn rotens nøkkel, // ligger den i venstre undertre if (nøkkel< root->key) { root->venstre = deleteNode(root->venstre, nøkkel);  } // Hvis nøkkelen som skal slettes er // større enn rotens nøkkel, // ligger den i høyre undertre else if (nøkkel> rot->nøkkel) { root->right = deleteNode(root-> høyre, nøkkel);  } // Hvis nøkkelen er den samme som rotnøkkelen, // så er dette noden // som skal slettes ellers { // Node med bare ett barn // eller ingen underordnet hvis (root->venstre == NULL) { struct node* temp = root->right;  gratis(root);  retur temp;  } else if (rot->høyre == NULL) { struct node* temp = rot->venstre;  gratis(root);  retur temp;  } // Node med to barn: // Få rekkefølgen etterfølgeren(minste // i høyre undertre) struct node* temp = minValueNode(root->right);  // Kopier etterfølgerens // innhold til denne noden root->key = temp->key;  // Delete the inorder successor root->right = deleteNode(root->right, temp->key);  } returner 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 = insert(node.right, key);  } // Returner noden returnoden;  } // Funksjon som returnerer noden med minimum // nøkkelverdi funnet i det treet statisk node minValueNode(node ​​node) { node current = node;  // Loop ned for å finne bladet lengst til venstre mens (current != null && current.left != null) current = current.left;  returstrøm;  } // Funksjon som sletter nøkkelen og // returnerer den nye statiske rotnoden deleteNode(node ​​rot, int nøkkel) { // base Case if (root == null) returner rot;  // Hvis nøkkelen som skal slettes er // mindre enn rotens nøkkel, // ligger den i venstre undertre if (nøkkel< 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, nøkkel);  } // Hvis nøkkelen er den samme som roots nøkkel, // så er dette noden // som skal slettes ellers { // Node med bare ett barn // eller ingen underordnet hvis (root.left == null) { node temp = root.right;  retur temp;  } else if (root.right == null) { node temp = root.left;  retur temp;  } // Node med to barn: // Få inorderfølgeren(minste // i høyre undertre) node temp = minValueNode(root.right);  // Kopier etterfølgerens //-innhold til denne noden root.key = temp.key;  // Delete the inorder successor root.right = deleteNode(root.right, temp.key);  } returner rot;  }>
Python 
# 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) # Returner nodepekeren returner root # Funksjon for å gjøre inorder-gjennomgang av BST def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # Funksjon som returnerer noden med minimum # nøkkelverdi funnet i det treet def minValueNode(node): strøm = node # Loop ned for å finne bladet lengst til venstre mens gjeldende og current.left er ikke Ingen: gjeldende = gjeldende.venstre returner gjeldende # Funksjon som sletter nøkkelen og # returnerer den nye roten def deleteNode(root, nøkkel): # base Sak hvis root er Ingen: returner rot # Hvis nøkkelen skal være slettet er # mindre enn rotens nøkkel, # så ligger den i venstre undertre hvis nøkkelen< 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, key) # Hvis nøkkelen er den samme som root-nøkkelen, # så er dette noden # som skal slettes ellers: # Node med bare ett barn # eller ingen barn hvis root.left er Ingen: temp = root.right root = Ingen retur temp elif root.right er Ingen: temp = root.left root = Ingen retur temp # Node med to barn: # Få etterfølgeren i rekkefølgen(minste # i høyre undertre) temp = minValueNode(root.right) # Kopier etterfølgerens # innhold i rekkefølgen til denne noden root.key = temp.key # Slett rekkefølgen root.right = deleteNode(root.right, temp.key) returner rot>

4. Traversal (Inorder traversal av BST) :

I tilfelle av binære søketrær (BST), gir Inorder-traversal noder i ikke-avtagende rekkefølge. Vi besøker først venstre barn, så roten og så høyre barn.

Nedenfor er implementeringen av hvordan du utfører en rekkefølgegjennomgang av et binært søketre:

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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // Funksjon for å sette inn en ny node med // gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node hvis (node ​​== NULL) returnerer nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) { node->venstre = insert(node->venstre, nøkkel);  } else if (nøkkel> node->nøkkel) { node->høyre = insert(node->høyre, nøkkel);  } // Returner nodepekeren returnode; } // Funksjon for å gjøre inorder-gjennomgang av BST void inorder(struct node* root) { if (root != NULL) { inorder(root->venstre);  cout<< ' ' << root->nøkkel;  inorder(root->høyre);  } } // Driverkode int main() { /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ struct node* root = NULL;  // Opprette BST-roten = insert(root, 50);  insert(root, 30);  insert(root, 20);  insert(root, 40);  insert(root, 70);  insert(root, 60);  insert(root, 80);  // Funksjon Call inorder(root);  returner 0; } // Denne koden er bidratt av 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->nøkkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // Funksjon for å sette inn en ny node med // gitt nøkkel i BST struct node* insert(struct node* node, int key) { // Hvis treet er tomt, returner en ny node hvis (node ​​== NULL) returnerer nyNode(nøkkel);  // Ellers går du tilbake i treet hvis (tast< node->key) { node->venstre = insert(node->venstre, nøkkel);  } else if (nøkkel> node->nøkkel) { node->høyre = insert(node->høyre, nøkkel);  } // Returner nodepekeren returnode; } // Funksjon for å gjøre inorder-gjennomgang av BST void inorder(struct node* root) { if (root != NULL) { inorder(root->venstre);  printf('%d ', root->nøkkel);  inorder(root->høyre);  } } // Driverkode int main() { /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ struct node* root = NULL;  // Opprette BST-roten = insert(root, 50);  insert(root, 30);  insert(root, 20);  insert(root, 40);  insert(root, 70);  insert(root, 60);  insert(root, 80);  // Funksjon Call inorder(root);  returner 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 = insert(node.right, key);  } // Returner noden returnoden;  } // Funksjon for å gjøre inorder-gjennomgang av BST static void inorder(node ​​root) { if (root != null) { inorder(root.left);  System.out.print(' ' + root.key);  inorder(root.right);  } } // Driver Code public static void main(String[] args) { /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ noderot = null;  // setter inn verdi 50 root = insert(root, 50);  // setter inn verdi 30 insert(root, 30);  // setter inn verdi 20 insert(root, 20);  // setter inn verdi 40 insert(root, 40);  // setter inn verdi 70 insert(root, 70);  // setter inn verdi 60 insert(root, 60);  // setter inn verdi 80 insert(root, 80);  // skriv ut BST i rekkefølgen(root);  } } // Denne koden er bidratt 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 = insert(node.right, key) # Returner nodepekeren returnode # Funksjon for å gjøre inorder-gjennomgang av BST def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # Driverkode hvis __navn__ == '__main__': # La oss lage følgende BST # 50 # /  # 30 70 # /  /  # 20 40 60 80 root = Ingen # Opprette BST-roten = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 20) , 80) # Funksjon Call inorder(root) #Denne koden er bidratt av japmeet01>
Produksjon 
 20 30 40 50 60 70 80>

Tidskompleksitet: O(N), hvor N er antall noder til BST
Hjelpeplass: O(1)

Anvendelser av BST:

  • Grafalgoritmer: BST-er kan brukes til å implementere grafalgoritmer, for eksempel i minimum span-tre-algoritmer.
  • Prioriterte køer: BST-er kan brukes til å implementere prioritetskøer, der elementet med høyest prioritet er ved roten av treet, og elementer med lavere prioritet lagres i undertrærne.
  • Selvbalanserende binært søketre: BST-er kan brukes som en selvbalanserende datastruktur som AVL-tre og rød-svart tre.
  • Datalagring og henting: BST-er kan brukes til å lagre og hente data raskt, for eksempel i databaser, hvor søk etter en spesifikk post kan gjøres i logaritmisk tid.

Fordeler:

  • Rask søk: Å søke etter en spesifikk verdi i en BST har en gjennomsnittlig tidskompleksitet på O(log n), der n er antall noder i treet. Dette er mye raskere enn å søke etter et element i en matrise eller koblet liste, som i verste fall har en tidskompleksitet på O(n).
  • Gjennomgang i rekkefølge: BST-er kan krysses i rekkefølge, som besøker det venstre undertreet, roten og det høyre undertreet. Dette kan brukes til å sortere et datasett.
  • Plasseffektiv: BST-er er plasseffektive siden de ikke lagrer overflødig informasjon, i motsetning til arrays og koblede lister.

Ulemper:

  • Skjeve trær: Hvis et tre blir skjevt, vil tidskompleksiteten til søke-, innsettings- og slettingsoperasjoner være O(n) i stedet for O(log n), noe som kan gjøre treet ineffektivt.
  • Ekstra tid nødvendig: Selvbalanserende trær krever ekstra tid for å opprettholde balansen under innsettings- og slettingsoperasjoner.
  • Effektivitet: BST-er er ikke effektive for datasett med mange duplikater, da de vil kaste bort plass.

Vanlige spørsmål(Ofte stilte spørsmål)på binært søketre:

1. Hva er et binært søketre?

Et binært søketre (BST) er et binært tre der hver node i venstre undertre er mindre enn roten, og hver node i høyre undertre har en verdi større enn roten . Egenskapene til et binært søketre er rekursive: hvis vi betrakter en node som en rot, vil disse egenskapene forbli sanne.

2. Hva er den binære søketreoperasjonen?

Det er tre hovedoperasjoner i Binary Search Tree: 1. Innsetting, 2. Sletting, 3. Søking. På grunn av egenskapene er det effektivt å søke i alle elementer i Binary Search Tree.

3. Hva er binært søketre og AVL-tre?

Binært søketre : Et binært søketre (BST) er et binært tre der hver node i det venstre undertreet er mindre enn roten, og hver node i det høyre undertreet har en verdi større enn roten.

AVL-tre : Binære søketrær (BST) som selvbalanserer og roterer automatisk er kjent som AVL-trær.

4. Hva er bruken av Binary Search Tree?

Binære søketrær kan brukes til å implementere abstrakte datatyper som f.eks dynamiske sett, oppslagstabeller og prioriterte køer, og brukes i sorteringsalgoritmer for eksempel tresortering.

5. Hva er forskjellen mellom binært søketre og binært tre?

Et binært søketre er et tre som følger en eller annen rekkefølge for å ordne elementene, mens det binære treet ikke følger noen rekkefølge.

hva xd betyr

Relaterte artikler:

  • Anvendelse av BST
  • Applikasjoner, fordeler og ulemper med binært søketre
  • Innsetting i binært søketre (BST)
  • Søk i binært søketre (BST)
  • Sletting i binært søketre (BST)