Binaire boom in gegevensstructuur (VOORBEELD)

Wat is een binaire boom?

Het woord binair betekent twee. In de boomdatastructuur betekent “Binaire Boom” een boom waarin elk knooppunt maximaal twee onderliggende knooppunten kan hebben (linker- en rechterknooppunten). Het is een eenvoudige binaire boom.

Er is echter nog een binaire boom die het vaakst wordt gebruikt en die verschillende gebruiksscenario's heeft. Het wordt de binaire zoekboom (BST) genoemd. Deze boom kan het zoekalgoritme veel sneller maken, nauwkeurig log(n) tijd complexiteit. In de datastructuur betekent n het aantal knooppunten in de binaire boom.

Wat zijn de verschillen tussen binaire boom en binaire zoekboom?

Het verschil tussen de BST en de reguliere binaire boom is dat het linkerknooppunt van de BST een kleinere waarde heeft dan het hoofdknooppunt, en dat het rechterknooppunt een grotere waarde heeft dan het hoofdknooppunt. De linker subboom zal dus altijd een kleinere waarde bevatten dan de wortel, en de rechter subboom zal altijd een grotere waarde bevatten dan de wortel.

De verschillen tussen binaire boom en binaire zoekboom

Voorbeeld van binaire zoekbomen

Laten we het volgende hebbenwing voorbeeld voor het demonstreren van de concepten van de binaire zoekboom.

Voorbeeld van binaire zoekbomen

Hier kun je alle knooppunten de gegeven discipline volgen. Er is een formule voor het maximale aantal knooppunten in de binaire zoekboom. Als we de bovenstaande boom bekijken, kunnen we zien dat elk knooppunt twee kinderen heeft, behalve alle bladknooppunten. En de hoogte(h) van de gegeven binaire boom is 4. De formule is 2h - 1. Het levert dus 15 op.

Voorbeeld van binaire zoekbomen

Voorbeeld van binaire zoekbomen

De hierboven gegeven afbeelding is geen volledige binaire boom of gebalanceerde binaire boom, maar wordt de complete binaire boom of gebalanceerde binaire boom genoemd. Er is een andere gegevensstructuur genaamd AVL (een ander type binaire boom) die de hoogte van de binaire boom optimaliseert en sneller naar de BST zoekt, zoals in figuur 3.

Probeer de volgorde van de hierboven gegeven binaire boom te berekenen. Je zult merken dat het een niet-afnemende gesorteerde array oplevert, en dat de Traversal-algoritmen hetzelfde zullen zijn als de binaire boom.

Soorten binaire boom

Hier zijn enkele belangrijke typen binaire bomen:

  • Volledige binaire boom: Elk knooppunt kan 0 of 2 onderliggende knooppunten in deze binaire boom hebben. Slechts één onderliggend knooppunt is niet toegestaan ​​in dit type binaire boom. Dus, behalve het bladknooppunt, zullen alle knooppunten 2 kinderen hebben.

Soorten binaire boom

  • Volledige binaire boom: Elk knooppunt kan 0 of 2 knooppunten hebben. Het lijkt op de volledige binaire boom, maar alle bladelementen bevinden zich in de linker subboom, terwijl in de volledige binaire boom het knooppunt zich in de rechter of linker subboom kan bevinden.

Soorten binaire boom

  • Perfecte binaire boom: Alle knooppunten moeten 0 of 2 knooppunten hebben en alle bladknooppunten moeten zich op hetzelfde niveau of dezelfde hoogte bevinden. Het bovenstaande voorbeeld van een volledige binaire boomstructuur is geen perfecte binaire boom omdat knooppunt 6 en knooppunt 1,2,3 zich niet op dezelfde hoogte bevinden. Maar het voorbeeld van de complete binaire boom is een perfecte binaire boom.
  • Gedegenereerde binaire boom: Elk knooppunt kan slechts één kind hebben. Alle operaties zoals searchiHet invoegen, invoegen en verwijderen kost O(N) tijd.

Soorten binaire boom

  • Evenwichtige binaire boom: Hier in deze binaire boom is het hoogteverschil tussen de linker en rechter deelboom maximaal 1. Dus tijdens het toevoegen of verwijderen van een knooppunt moeten we de hoogte van de boom opnieuw in evenwicht brengen. Dit type zelfgebalanceerde binaire boom wordt de AVL-boom.

Soorten binaire boom

Er zijn drie basisbewerkingen van BST. Deze worden hieronder in detail besproken.

Implementatie van binaire boom in C en C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
   int value;
   struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
   struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
   tempNode->value = val;
   tempNode->left = NULL;
   tempNode->right = NULL;
   return tempNode;
}
struct Node *successor(struct Node *node)
{
    struct Node *present = node;
// going to the left most node
    while (present != NULL && present->left != NULL)
    {
       present = present->left;
    }
     return present;
 }
struct Node *insert(struct Node *node, int value)
{
   if (node == NULL)
   {
      return getEmptynode(value);
   }
   if (value < node->value)
   {
      node->left = insert(node->left, value);
   }
   else
   {
      node->right = insert(node->right, value);
   }
      return node;
}
int searchInBST(struct Node *node, int value)
{
   struct Node *current = node;
   while (current->value != value)
    {
    if (current->value > value)
      {
      current = current->left;
      }
    else
     {
     current = current->right;
     }
   if (current == NULL)
     {
    return 0;
     }
   }
return 1;
}
void inorder(struct Node *root)
{
 if (root != NULL)
  {
   inorder(root->left);
   cout << root->value << " ";
   inorder(root->right);
  }
}
struct Node *deleteNode(struct Node *node, int value)
{
 if (node == NULL)
  {
   return node;
  }
 if (value < node->value)
  {
   node->left = deleteNode(node->left, value);
  }
else if (value > node->value)
 {
   node->right = deleteNode(node->right, value);
 }
else
{
if (node->left == NULL)
 {
 struct Node *temp = node->right;
 free(node);
 return temp;
 }
 else if (node->right == NULL)
 {
 struct Node *temp = node->left;
 free(node);
 return temp;
  }
 struct Node *temp = successor(node->right);
 node->value = temp->value;
 node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
 {
  struct Node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 4);
  root = insert(root, 12);
  root = insert(root, 2);
  root = insert(root, 6);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 1);
  root = insert(root, 3);
  root = insert(root, 5);
  root = insert(root, 7);
  root = insert(root, 9);
  root = insert(root, 11);
  root = insert(root, 13);
  root = insert(root, 15);

 cout << "InOrder Traversal after inserting all nodes: " << endl;
 inorder(root);
 root = insert(root, -10);
 cout << "\nInOrder Traversal after inserting -10 : " << endl;
 inorder(root);
 cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
 cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
 root = deleteNode(root,8);
 cout<<"After deleting node 8, inorder traversal: "<<endl;
 inorder(root);
 root = deleteNode(root,-10);
 cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
 inorder(root);
}

Output:

InOrder Traversal after inserting all nodes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

InOrder Traversal after inserting -10 :
10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Searching -5 in the BST: 0
Searching -10 in the BST: 1

After deleting node 8, inorder traversal:
-10 1 2 3 4 5 6 7 9 10 11 12 13 14 15

After deleting node -10, inorder traversal:
1 2 3 4 5 6 7 9 10 11 12 13 14 15

Implementatie van binaire boom in Python

class Node:
def __init__(self,value):
      self.left = None
      self.right = None
      self.value = value
def insert(root,value):
      if root == None:
          return Node(value)
      if value< root.value:
          root.left = insert(root.left,value)
      else:
          root.right = insert(root.right,value)
          return root
  def searchInBST(root,value):
      current = root
  while current.value != value:
  if current.value > value:
      current = current.left
  else:
      current = current.right
  if current == None:
      return "Not found"
      return "Found"
def inorder(root):
    if root != None:
      inorder(root.left)
      print(root.value,end=" ")
      inorder(root.right)
def successor(root):
    present = root
    while present != None and present.left != None:
    present = present.left
      return present
def deleteNode(root,value):
    if root == None:
      return root
    if value < root.value:
        root.left = deleteNode(root.left, value)
    elif value>root.value:
        root.right = deleteNode(root.right, value)
    else:
    if root.left == None:
        temp = root.right
        root = None
        return temp
    elif root.right == None:
        temp = root.left
        root = None
        return temp
        temp = successor(root.right)
        root.value = temp.value
        root.right = deleteNode(root.right, temp.value)
        return root
        root = Node(8)
        root = insert(root, 4)
        root = insert(root, 12)
        root = insert(root, 2)
        root = insert(root, 6)
        root = insert(root, 10)
        root = insert(root, 14)
        root = insert(root, 1)
        root = insert(root, 3)
        root = insert(root, 5)
        root = insert(root, 7)
        root = insert(root, 9)
        root = insert(root, 11)
        root = insert(root, 13)
        root = insert(root, 15)
  print("InOrder Traversal after inserting all nodes: ")
  inorder(root)
  root = insert(root, -10)
  print("\nInOrder Traversal after inserting -10 : ")
  inorder(root)
  print("\nSearching -5 in the BST: ",searchInBST(root, -5))
  print("Searching -5 in the BST: ",searchInBST(root, -10))
  root = deleteNode(root,8)
  print("After deleting node 8, inorder traversal:")
  inorder(root)
  root = deleteNode(root,-10)
  print("\nAfter deleting node -10, inorder traversal:")
  inorder(root)

Output:

InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Searching -5 in the BST: Not found 

Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 

After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15

Toepassing van binaire boom

Hier zijn enkele veelvoorkomende toepassingen van Binary Tree:

  • Knooppuntgegevens in gesorteerde volgorde ordenen
  • Wordt gebruikt in de kaart- en set-node-objecten in programmeertaalbibliotheken.
  • Searching voor elementen in de datastructuren

» Lees onze volgende tutorial over Combinatie-algoritme