Arborele binar în structura datelor (EXEMPLU)

⚡ Rezumat inteligent

Arborele binar în structura datelor este o structură ierarhică în care fiecare nod are cel mult doi copii, numiți stânga și dreapta. Această resursă explică arborii binari, arborele binar de căutare, tipurile lor, aplicațiile și limbajul C complet. C++ și Python implementări.

  • 🌳 Definiție: Un arbore binar este o structură în care fiecare nod are cel mult două noduri copil, stânga și dreapta.
  • 🔍 Arbore binar de căutare: Într-un BST, copiii din stânga dețin valori mai mici, iar copiii din dreapta dețin valori mai mari, permițând căutarea O(log n).
  • 🧩 tipuri: Arborii binari plini, compleți, perfecți, degenerați și echilibrați impun fiecare reguli de formă diferite.
  • ⚙️ BST Operaacțiuni: Inserarea, căutarea și ștergerea respectă proprietatea de ordonare pentru a menține căutările rapide.
  • 💻 Code Furnizat: Lucrând C, C++ și Python Programele demonstrează inserarea, căutarea, ștergerea și parcurgerea în ordine inordonată.

Ce este un arbore binar?

Cuvântul binar înseamnă doi. În structura de date arborescentă „Arborele binar”, înseamnă un arbore în care fiecare nod poate avea maximum două noduri secundare (noduri stânga și dreapta). Este un arbore binar simplu.

Cu toate acestea, există un alt arbore binar care este folosit cel mai frecvent și are mai multe cazuri de utilizare. Se numește Arborele de căutare binar (BST). Acest arbore poate face algoritmul de căutare mult mai rapid, exact log(n) complexitatea timpului. În structura de date, n înseamnă numărul de noduri din arborele binar.

Care sunt diferențele dintre arborele binar și arborele de căutare binar?

Diferența dintre BST și arborele binar obișnuit este că nodul din stânga BST are o valoare mai mică decât nodul rădăcină, iar nodul din dreapta are o valoare mai mare decât nodul rădăcină. Deci, subarborele din stânga va conține întotdeauna o valoare mai mică decât rădăcina, iar subarborele din dreapta va conține întotdeauna o valoare mai mare decât rădăcina.

Diferențele dintre arborele binar și arborele binar de căutare

Exemplu de arbori binari de căutare

Să avem următorul exemplu pentru a demonstra conceptele Arborele de căutare binar.

Exemplu de arbori binari de căutare

Aici puteți toate nodurile să urmeze disciplina dată. Există o formulă pentru numărul maxim de noduri în Arborele de căutare binar. Dacă observăm arborele de mai sus, putem vedea că fiecare nod are doi copii, cu excepția tuturor nodurilor frunze. Și înălțimea (h) a arborelui binar dat este 4. Formula este 2h - 1. Deci, dă 15.

Exemplu de arbori binari de căutare

Exemplu de arbori binari de căutare

Imaginea de mai sus nu este un arbore binar complet sau un arbore binar echilibrat, ci se numește arbore binar complet sau arbore binar echilibrat. Există o altă structură de date numită AVL (un alt tip de arbore binar) care optimizează înălțimea arborelui binar și efectuează căutarea mai rapid pentru BST, ca în figura 3.

Încercați să calculați traversarea în ordine a arborelui binar prezentat mai sus. Veți descoperi că va oferi o matrice sortată nedescrescătoare, iar algoritmii Traversal vor fi la fel ca și Arborele binar.

Tipuri de arbore binar

Iată câteva tipuri importante de arbore binar:

  • Arborele binar complet: Fiecare nod poate avea 0 sau 2 noduri copil în acest arbore binar. Un singur nod copil nu este permis în acest tip de arbore binar. Deci, cu excepția nodului frunză, toate nodurile vor avea 2 copii.

Tipuri de arbore binar

  • Arbore binar complet: Fiecare nod poate avea 0 sau 2 noduri. Pare a arborelui binar complet, dar toate elementele frunzelor sunt înclinate către subarborele din stânga, în timp ce în arborele binar complet nodul poate fi în subarborele din dreapta sau din stânga.

Tipuri de arbore binar

  • Arborele binar perfect: Toate nodurile trebuie să aibă 0 sau 2 noduri, iar toate nodurile frunzelor trebuie să fie la același nivel sau înălțime. Exemplul de mai sus al unei structuri de arbore binar complet nu este un arbore binar perfect deoarece nodul 6 și nodul 1,2,3 nu sunt la aceeași înălțime. Dar exemplul Arborelui Binar Complet este un arbore binar perfect.
  • Arborele binar degenerat: Fiecare nod poate avea doar un singur copil. Toate operațiunile precum căutarea, inserarea și ștergerea durează O(N).

Tipuri de arbore binar

  • Arborele binar echilibrat: Aici acest arbore binar, diferența de înălțime a subarborelui din stânga și din dreapta este de cel mult 1. Deci, în timp ce adăugăm sau ștergem un nod, trebuie să echilibrăm din nou înălțimea arborelui. Acest tip de arbore binar auto-echilibrat se numește Copac AVL.

Tipuri de arbore binar

Există trei operațiuni de bază ale BST. Acestea sunt discutate în detaliu mai jos.

Implementarea arborelui binar în C și 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);
}

ieșire:

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

Implementarea arborelui binar în 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)

ieșire:

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

Aplicarea arborelui binar

Iată câteva aplicații comune ale arborelui binar:

  • Organizarea datelor nodurilor în ordine sortată
  • Folosit în hartă și set de obiecte nod în bibliotecile limbajului de programare.
  • Căutarea elementelor în structurile de date

» Aflați următorul nostru tutorial despre Algoritmul de combinare

Întrebări frecvente

Adâncimea unui nod este numărul de muchii de la rădăcină până la acel nod. Înălțimea unui nod este numărul de muchii de pe cea mai lungă cale de la acesta până la o frunză. Înălțimea arborelui este egală cu înălțimea rădăcinii.

Un arbore binar limitează fiecare nod la doar doi copii, deci poate deveni dezechilibrat și lent. Un arbore AVL este un arbore binar de căutare auto-echilibrat care menține diferența de înălțime dintre subarbori în limita unuia, garantând operații O(log n).

Un arbore binar poate fi stocat într-o matrice prin plasarea rădăcinii la indexul 0. Pentru un nod la indexul i, copilul său stâng se află la 2i+1, iar copilul său drept la 2i+2. Acest lucru se potrivește cel mai bine arborilor binari compleți.

Instrumentele de inteligență artificială pot transforma o listă de valori sau cod într-o diagramă interactivă de arbore binar, evidențiind nodurile pe măsură ce sunt inserate, căutate sau șterse. Acest lucru îi ajută pe începători să vadă cum se schimbă structura în timpul fiecărei operațiuni.

Da. Asistenții de codare bazați pe inteligență artificială pot genera cod de tip arbore binar și BST — inserare, căutare, ștergere și traversare — în limbaje precum C++, Python și Java. RevVizualizați și testați rezultatul, deoarece IA poate rata cazuri limită, cum ar fi duplicatele.

Rezumați această postare cu: