Dvejetainis medis yra nelinijinė duomenų struktūra kur kiekvienas mazgas turi daugiausia du vaikus. Šiame straipsnyje apžvelgsime visus dvejetainio medžio pagrindus, operacijas su dvejetainiu medžiu, jo įgyvendinimą, privalumus, trūkumus, kurie padės išspręsti visas dvejetainio medžio problemas.

Turinys

• Kas yra dvejetainis medis?
• Dvejetainio medžio vaizdavimas
• Dvejetainių medžių rūšys
• Operacijos ant dvejetainio medžio
  • Įterpimas į dvejetainį medį
  • Perėjimas per dvejetainį medį
  • Ištrynimas dvejetainiame medyje
  • Ieškoma dvejetainiame medyje
• Pagalbinės operacijos dvejetainiame medyje
• Dvejetainio medžio įgyvendinimas
• Dvejetainio medžio operacijų sudėtingumo analizė
• Dvejetainio medžio privalumai
• Dvejetainio medžio trūkumai
• Dvejetainio medžio programos
• Dažnai užduodami klausimai apie dvejetainį medį

Kas yra dvejetainis medis?

Dvejetainis medis yra a medžio duomenų struktūra (netiesinė) kuriame kiekvienas mazgas gali turėti daugiausiai du vaikai kurios vadinamos paliktas vaikas ir teisingas vaikas .

Viršutinis dvejetainio medžio mazgas vadinamas šaknis , o žemiausi mazgai vadinami lapai . Dvejetainį medį galima įsivaizduoti kaip hierarchinę struktūrą, kurios šaknis yra viršuje, o lapai apačioje.

Dvejetainio medžio vaizdavimas

Kiekvienas dvejetainio medžio mazgas turi tris dalis:

• Duomenys
• Rodyklė į kairįjį vaiką
• Nukreipkite į tinkamą vaiką

Žemiau pateikiamas dvejetainio medžio mazgo vaizdas įvairiomis kalbomis:

// Use any below method to implement Nodes of tree // Method 1: Using 'struct' to make // user-define data type struct node {  int data;  struct node* left;  struct node* right; }; // Method 2: Using 'class' to make // user-define data type class Node { public:  int data;  Node* left;  Node* right; }; 

// Structure of each node of the tree struct node {  int data;  struct node* left;  struct node* right; }; 

// Class containing left and right child // of current node and key value class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } 

# A Python class that represents # an individual node in a Binary Tree class Node: def __init__(self, key): self.left = None self.right = None self.val = key 

// Class containing left and right child // of current node and key value class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } 

 >>   
 Dvejetainių medžių rūšys  
 
 Dvejetainis medis gali būti suskirstytas į kelis tipus, atsižvelgiant į kelis veiksnius:  
  
 
    Pagal vaikų skaičių     
 
  Visas dvejetainis medis   
 
  Degeneruotas dvejetainis medis   
 
  Iškreipti dvejetainiai medžiai   
 
 
 
    Lygių užbaigimo pagrindu     
 
   Pilnas dvejetainis medis    
 
  Tobulas dvejetainis medis   
 
   Subalansuotas dvejetainis medis    
 
 
 
    Remiantis mazgo reikšmėmis:     
 
  Dvejetainis paieškos medis   
 
   AVL medis    
 
   Raudonas juodas medis    
 
   B Medis    
 
   B+ medis    
 
  Segmentų medis   
 
 
 
 
    Operacijos ant dvejetainio medžio     
 
 1. Įterpimas į dvejetainį medį  
 
 Mes galime įterpti mazgą bet kurioje dvejetainio medžio vietoje, įterpdami mazgą kaip kairįjį arba dešinįjį bet kurio mazgo antrinį elementą arba padarydami mazgą kaip medžio šaknį.  
  
    Algoritmas įterpti mazgą į dvejetainį medį:     
  
 
 Patikrinkite, ar dvejetainiame medyje nėra mazgo, kuriame nėra kairiojo vaiko. Jei toks mazgas egzistuoja, įterpkite naują mazgą kaip kairįjį antrinį.  
 
 Patikrinkite, ar dvejetainiame medyje nėra mazgo, kuriam trūksta tinkamo vaiko. Jei toks mazgas egzistuoja, įterpkite naują mazgą kaip dešinįjį antrinį.  
 
 Jei nerandame nė vieno mazgo, kuriame trūksta kairiojo arba dešiniojo porūšio, tada suraskite mazgą, kuriame trūksta abiejų antrinių dalių, ir įterpkite mazgą kaip kairįjį arba dešinįjį atžalą.  
 
 
 2. Perėjimas per dvejetainį medį  
 
 Perėjimas per dvejetainį medį apima visų dvejetainio medžio mazgų aplankymą. Medžio apėjimo algoritmus galima iš esmės suskirstyti į dvi kategorijas:  
  
 
 Giluminės paieškos (DFS) algoritmai  
 
 Pirmosios paieškos (BFS) algoritmai  
 
 
 Giluminės paieškos (DFS) algoritmai:  
 
 
      Išankstinis užsakymas (dabartinis - kairėn - dešinėn):          Apsilankykite dabartiniame mazge prieš apsilankydami bet kuriuose mazguose kairiajame arba dešiniajame pomedžio viduje. Čia perėjimas yra šaknis – kairysis vaikas – dešinysis vaikas. Tai reiškia, kad pirmiausia pereinama šakninis mazgas, tada jo kairysis vaikas ir galiausiai dešinysis vaikas.  
 
      Inorder Traversal (kairė-srovė-dešinė):               Apsilankę dabartiniame mazge aplankykite visus kairiojo pomedžio mazgus, bet prieš apsilankydami bet kuriame dešiniojo pomedžio mazge. Čia perėjimas yra kairysis vaikas – šaknis – dešinysis vaikas. Tai reiškia, kad pirmiausia perkeliamas kairysis vaikas, tada jo šaknies mazgas ir galiausiai dešinysis vaikas.  
 
      Postorder Traversal (kairė-dešinė-srovė):       Apsilankę visuose kairiojo ir dešiniojo pomedžio mazguose, apsilankykite dabartiniame mazge.           Čia perėjimas yra kairysis vaikas – dešinysis vaikas – šaknis. Tai reiškia, kad pirmiausia perėjo kairysis vaikas, tada dešinysis vaikas ir galiausiai jo šaknies mazgas.  
 
 
 Pirmosios paieškos (BFS) algoritmai:  
 
 
      Lygio užsakymo perėjimas:               Apsilankykite mazguose po lygius ir iš kairės į dešinę tame pačiame lygyje. Čia važiavimas vyksta lygiu. Tai reiškia, kad pirmas perėjo labiausiai kairysis vaikas, o tada kiti to paties lygio vaikai iš kairės į dešinę.  
 
 
 3. Ištrynimas dvejetainiame medyje  
 
 Galime ištrinti bet kurį dvejetainio medžio mazgą ir po ištrynimo pertvarkyti mazgus, kad vėl būtų sudarytas tinkamas dvejetainis medis.  
  
    Algoritmas, kaip ištrinti mazgą dvejetainiame medyje:     
  
 
 Pradėdami nuo šaknies, suraskite giliausią ir dešinįjį dvejetainio medžio mazgą ir mazgą, kurį norime ištrinti.  
 
 Pakeiskite giliausio dešiniojo mazgo duomenis mazgu, kurį reikia ištrinti.  
 
 Tada ištrinkite giliausią dešinįjį mazgą.  
 
 
 4. Paieška dvejetainiame medyje  
 
 Elemento mazge galime ieškoti naudodami bet kurią perėjimo techniką.  
  
    Algoritmas ieškoti mazgo dvejetainiame medyje:     
  
 
 Pradėkite nuo šakninio mazgo.  
 
 Patikrinkite, ar dabartinio mazgo vertė yra lygi tikslinei vertei.  
 
 Jei dabartinio mazgo vertė yra lygi tikslinei vertei, tada šis mazgas yra būtinas mazgas.  
 
 Kitu atveju, jei mazgo reikšmė nėra lygi tikslinei vertei, pradėkite paiešką kairiajame ir dešiniajame antriniame stulpelyje.  
 
 Jei nerandame mazgo, kurio reikšmė būtų lygi tikslinei, tada reikšmės medyje nėra.  
 
 
    Pagalbinės operacijos dvejetainiame medyje     
 
 
   Medžio aukščio nustatymas    
 
  Raskite mazgo lygį dvejetainiame medyje   
 
  Raskite viso medžio dydį   
 
 
 Dvejetainio medžio įgyvendinimas  
 
 Žemiau yra dvejetainio medžio įterpimo, ištrynimo ir perėjimo kodas:  
C duomenys);  inorderTraversal(root->right); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  printf('%d ', root->duomenys);  preorderTraversal(root->left);  preorderTraversal(root->right); } // Postorder tree traversal (Kairė - Dešinė - Šaknis) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->right);  printf('%d ', root->duomenys); } // Lygio tvarkos medžio traversal funkcija void levelorderTraversal(Node* root) { if (root == NULL) return;  // Lygio užsakymo eilė Node* eilė[100];  int priekyje = 0, gale = 0;  eilė[galinis++] = šaknis;  while (priekis != galinis) { Mazgas* temp = eilė[priekis++];  printf('%d ', temp->duomenys);  // Stumti kairįjį vaiką eilėje if (temp->left) queue[rear++] = temp->left;  // Stumti dešinįjį antrinį eilėje if (temp->right) queue[rear++] = temp->right;  } } /* Tvarkyklės funkcija, skirta patikrinti aukščiau pateiktą algoritmą. */ int main() { Mazgas* root = NULL;  // Mazgų įterpimas root = insert(root, 10);  šaknis = įterpti(šaknis, 20);  šaknis = įterpti(šaknis, 30);  šaknis = įterpti(šaknis, 40);  printf('Išankstinis užsakymas: ');  preorderTraversal(root);  printf('
Inorder traversal: ');  inorderTraversal(root);  printf('
Postorder traversal: ');  postorderTraversal(root);  printf('
Lygio eilės tvarka: ');  levelorderTraversal(root);  // Ištrinkite mazgą su duomenimis = 20 root = deletion(root, 20);  printf('
Užsakymo perėjimas po ištrynimo: ');  inorderTraversal(root);  grąžinti 0; } 

import java.util.LinkedList; import java.util.Queue; // Node class to define the structure of the node class Node {  int data;  Node left, right;  // Parameterized Constructor  Node(int val) {  data = val;  left = right = null;  } } public class BinaryTree {  // Function to insert nodes  public static Node insert(Node root, int data) {  // If tree is empty, new node becomes the root  if (root == null) {  root = new Node(data);  return root;  }  // Queue to traverse the tree and find the position to  // insert the node  Queue q = naujas LinkedList();  q.offer(root);  while (!q.isEmpty()) { Mazgo temp = q.poll();  // Įterpti mazgą kaip kairįjį pirminio mazgo antrinį elementą if (temp.left == null) { temp.left = new Mazgas(duomenys);  pertrauka;  } // Jei kairysis vaikas nėra nulis, stumkite jį į // eilę else q.offer(temp.left);  // Įterpti mazgą kaip dešinįjį pirminio mazgo antrinį elementą if (temp.right == null) { temp.right = new Node(data);  pertrauka;  } // Jei tinkamas vaikas nėra nulis, stumkite jį į // eilę else q.offer(temp.right);  } return root;  } /* funkcija, skirta ištrinti duotą giliausią mazgą (d_mazgas) dvejetainiame medyje */ public static void deletDeepest(mazgo šaknis, mazgo d_mazgas) { Eilė q = naujas LinkedList();  q.offer(root);  // Atlikti lygio užsakymo perėjimą iki paskutinio mazgo Mazgo temp;  while (!q.isEmpty()) { temp = q.poll();  if (temp == d_mazgas) { temp = null;  d_mazgas = null;  grąžinti;  } if (temp.right != null) { if (temp.right == d_mazgas) { temp.right = null;  d_mazgas = null;  grąžinti;  } else q.offer(temp.right);  } if (temp.left != null) { if (temp.left == d_mazgas) { temp.left = null;  d_mazgas = null;  grąžinti;  } else q.offer(temp.left);  } } } /* funkcija ištrinti elementą dvejetainiame medyje */ public static Mazgo ištrynimas(Mazgo šaknis, raktas int) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == raktas) return null;  kitaip grąžinti šaknį;  }  Eilė q = naujas LinkedList();  q.offer(root);  Mazgo temp = naujas mazgas(0);  Mazgo raktas_mazgas = null;  // Atlikite lygio užsakymo perėjimą, kad surastumėte giliausią // mazgą(temp) ir mazgą, kurį reikia ištrinti (key_node), o (!q.isEmpty()) { temp = q.poll();  if (temp.data == raktas) rakto_mazgas = temp;  if (temp.left != null) q.offer(temp.left);  if (temp.right != null) q.offer(temp.right);  } if (rakto_mazgas != null) { int x = temp.duomenys;  rakto_mazgas.duomenys = x;  ištrinti giliausią(šaknis, temp);  } return root;  } // Inorder tree traversal (Left - Root - Dešinė) public static void inorderTraversal(Node root) { if (root == null) return;  inorderTraversal(root.left);  System.out.print(root.data + ' ');  inorderTraversal(root.right);  } // Išankstinio užsakymo medžio traversal (Šaknis - Kairė - Dešinė) public static void preorderTraversal(Node root) { if (root == null) return;  System.out.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Postorder tree traversal (Kairė - Dešinė - Šaknis) public static void postorderTraversal(Node root) { if (root == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Lygio tvarkos medžio traversal funkcija public static void levelorderTraversal(Node root) { if (root == null) return;  // Lygio užsakymo eilė Eilė q = naujas LinkedList();  q.offer(root);  while (!q.isEmpty()) { Mazgo temp = q.poll();  System.out.print(temp.data + ' ');  // Stumti kairįjį vaiką eilėje if (temp.left != null) q.offer(temp.left);  // Stumti dešinįjį vaiką eilėje if (temp.right != null) q.offer(temp.right);  } } /* Tvarkyklės funkcija, skirta patikrinti aukščiau pateiktą algoritmą. */ public static void main(String[] args) { Mazgo šaknis = null;  // Mazgų įterpimas root = insert(root, 10);  šaknis = įterpti(šaknis, 20);  šaknis = įterpti(šaknis, 30);  šaknis = įterpti(šaknis, 40);  System.out.print('Išankstinis užsakymas: ');  preorderTraversal(root);  System.out.print('
Inorder traversal: ');  inorderTraversal(root);  System.out.print('
Postorder traversal: ');  postorderTraversal(root);  System.out.print('
Lygio tvarka: ');  levelorderTraversal(root);  // Ištrinkite mazgą su duomenimis = 20 root = deletion(root, 20);  System.out.print('
Užsakymo perėjimas po ištrynimo: ');  inorderTraversal(root);  } }>> Python   C#   
using System; using System.Collections.Generic; // Node class to define the structure of the node public class Node {  public int data;  public Node left, right;  // Parameterized Constructor  public Node(int val)  {  data = val;  left = right = null;  } } public class Program {  // Function to insert nodes  public static Node Insert(Node root, int data)  {  // If tree is empty, new node becomes the root  if (root == null)  {  root = new Node(data);  return root;  }  // Queue to traverse the tree and find the position to insert the node  Queue q = nauja eilė ();  q.Enqueue(root);  while (q.Count != 0) { Mazgo temp = q.Dequeue();  // Įterpti mazgą kaip kairįjį pirminio mazgo antrinį elementą if (temp.left == null) { temp.left = new Mazgas(duomenys);  pertrauka;  } // Jei kairysis vaikas nėra nulis, stumkite jį į eilę else q.Enqueue(temp.left);  // Įterpti mazgą kaip dešinįjį pirminio mazgo antrinį elementą if (temp.right == null) { temp.right = new Node(data);  pertrauka;  } // Jei tinkamas vaikas nėra nulis, stumkite jį į eilę else q.Enqueue(temp.right);  } return root;  } /* funkcija, skirta ištrinti duotą giliausią mazgą (d_mazgas) dvejetainiame medyje */ public static void DeleteDeepest(mazgo šaknis, mazgo d_mazgas) { Eilė q = nauja eilė ();  q.Enqueue(root);  // Atlikti lygio užsakymo perėjimą iki paskutinio mazgo Mazgo temp;  while (q.Count != 0) { temp = q.Dequeue();  if (temp == d_mazgas) { temp = null;  d_mazgas = null;  grąžinti;  } if (temp.right != null) { if (temp.right == d_mazgas) { temp.right = null;  d_mazgas = null;  grąžinti;  } else q.Enqueue(temp.right);  } if (temp.left != null) { if (temp.left == d_mazgas) { temp.left = null;  d_mazgas = null;  grąžinti;  } else q.Enqueue(temp.left);  } } } /* funkcija ištrinti elementą dvejetainiame medyje */ public static Mazgo ištrynimas(Mazgo šaknis, int raktas) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == raktas) return null;  kitaip grąžinti šaknį;  }  Eilė q = nauja eilė ();  q.Enqueue(root);  Mazgo temp = naujas mazgas(0);  Mazgo raktas_mazgas = null;  // Atlikite lygio tvarką, kad surastumėte giliausią mazgą (temp) ir mazgą, kurį reikia ištrinti (key_node), o (q.Count != 0) { temp = q.Dequeue();  if (temp.data == raktas) rakto_mazgas = temp;  if (temp.left != null) q.Enqueue(temp.left);  if (temp.right != null) q.Enqueue(temp.right);  } if (rakto_mazgas != null) { int x = temp.duomenys;  rakto_mazgas.duomenys = x;  IštrintiDeepest(šaknis, temp);  } return root;  } // Inorder tree traversal (Left - Root - Dešinė) public static void InorderTraversal(Node root) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Išankstinio užsakymo medžio traversal (Šaknis - Kairė - Dešinė) public static void PreorderTraversal(Node root) { if (root == null) return;  Console.Write(root.data + ' ');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Postorder tree traversal (Kairė - Dešinė - Šaknis) public static void PostorderTraversal(Node root) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Lygio tvarkos medžio traversal funkcija public static void LevelorderTraversal(Node root) { if (root == null) return;  // Lygio užsakymo eilė Eilė q = nauja eilė ();  q.Enqueue(root);  while (q.Count != 0) { Mazgo temp = q.Dequeue();  Console.Write(temp.data + ' ');  // Stumti kairįjį vaiką eilėje if (temp.left != null) q.Enqueue(temp.left);  // Stumti dešinįjį vaiką eilėje if (temp.right != null) q.Enqueue(temp.right);  } } /* Tvarkyklės funkcija, skirta patikrinti aukščiau pateiktą algoritmą. */ public static void Main(string[] args) { Mazgo šaknis = null;  // Mazgų įterpimas root = Insert(root, 10);  šaknis = Įterpti(šaknis, 20);  šaknis = Įterpti(šaknis, 30);  šaknis = Įterpti(šaknis, 40);  Console.Write('Išankstinis užsakymas: ');  PreorderTraversal(root);  Console.Write('
Inorder traversal: ');  InorderTraversal(šaknis);  Console.Write('
Postorder traversal: ');  PostorderTraversal(root);  Console.Write('
Lygio eilės tvarka: ');  LevelorderTraversal(root);  // Ištrinkite mazgą su duomenimis = 20 root = Deletion(root, 20);  Console.Write('
Inorder traversal po ištrynimo: ');  InorderTraversal(šaknis);  } }>> Javascript   C++14   
#include  using namespace std; // Node class to define the structure of the node class Node { public:  int data;  Node *left, *right;  // Parameterized Constructor  Node(int val)  {  data = val;  left = right = NULL;  } }; // Function to insert nodes Node* insert(Node* root, int data) {  // If tree is empty, new node becomes the root  if (root == NULL) {  root = new Node(data);  return root;  }  // queue to traverse the tree and find the position to  // insert the node  queue q;  q.push(root);  while (!q.empty()) { Mazgas* temp = q.front();  q.pop();  // Įterpti mazgą kaip kairįjį pirminio mazgo antrinį elementą if (temp->left == NULL) { temp->left = new Node(data);  pertrauka;  } // Jei kairysis vaikas nėra nulis, stumkite jį į // eilę else q.push(temp->left);  // Įterpti mazgą kaip dešinįjį pirminio mazgo antrinį elementą if (temp->right == NULL) { temp->right = new Mazgas(duomenys);  pertrauka;  } // Jei tinkamas vaikas nėra nulis, stumkite jį į // eilę else q.push(temp->right);  } return root; } /* funkcija, skirta ištrinti duotą giliausią mazgą (d_mazgas) dvejetainiame medyje */ void deletDeepest(Node* root, Node* d_node) { eilė q;  q.push(root);  // Atlikti lygio užsakymo perėjimą iki paskutinio mazgo Node* temp;  while (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_mazgas) { temp = NULL;  ištrinti (d_mazgas);  grąžinti;  } if (temp->right) { if (temp->right == d_mazgas) { temp->right = NULL;  ištrinti (d_mazgas);  grąžinti;  } else q.push(temp->right);  } if (temp->left) { if (temp->left == d_mazgas) { temp->left = NULL;  ištrinti (d_mazgas);  grąžinti;  } else q.push(temp->left);  } } } /* funkcija ištrinti elementą dvejetainiame medyje */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == raktas) return NULL;  kitaip grąžinti šaknį;  }  eilė q;  q.push(root);  Mazgas* temp;  Mazgas* rakto_mazgas = NULL;  // Atlikite lygio tvarkos apėjimą, kad surastumėte giliausią // mazgą(temp) ir mazgą, kurį reikia ištrinti (key_node), while (!q.empty()) { temp = q.front();  q.pop();  if (temp->duomenys == raktas) rakto_mazgas = temp;  if (temp->left) q.push(temp->left);  if (temp->right) q.push(temp->right);  } if (rakto_mazgas != NULL) { int x = temp->duomenys;  rakto_mazgas->duomenys = x;  ištrinti giliausią(šaknis, temp);  } return root; } // Inorder tree traversal (Left - Root - Right) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->left);  cout < < root->duomenis < < ' ';  inorderTraversal(root->teisė); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  cout < < root->duomenis < < ' ';  preorderTraversal(root->kairėje);  preorderTraversal(root->right); } // Postorder tree traversal (Kairė - Dešinė - Šaknis) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->right);  cout < < root->duomenis < < ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queue q;  q.push(root);  while (!q.empty()) { Mazgas* temp = q.front();  q.pop();  cout < < temp->duomenis < < ' ';  // Push left child in the queue  if (temp->kairėje) q.push(temp->left);  // Stumti dešinįjį vaiką eilėje if (temp->right) q.push(temp->right);  } } /* Tvarkyklės funkcija, skirta patikrinti aukščiau pateiktą algoritmą. */ int main() { Mazgas* root = NULL;  // Mazgų įterpimas root = insert(root, 10);  šaknis = įterpti(šaknis, 20);  šaknis = įterpti(šaknis, 30);  šaknis = įterpti(šaknis, 40);  cout < < 'Preorder traversal: ';  preorderTraversal(root);  cout  < < '
Inorder traversal: ';  inorderTraversal(root);  cout  < < '
Postorder traversal: ';  postorderTraversal(root);  cout  < < '
Level order traversal: ';  levelorderTraversal(root);  // Delete the node with data = 20  root = deletion(root, 20);  cout  < < '
Inorder traversal after deletion: ';  inorderTraversal(root); } 
    
  Išvestis   
Preorder traversal: 10 20 40 30 Inorder traversal: 40 20 10 30 Postorder traversal: 40 20 30 10 Level order traversal: 10 20 30 40 Inorder traversal after deletion: 40 10 30 
  
 Dvejetainio medžio operacijų sudėtingumo analizė  
 
 
 
 
    Operacijos     
 
    Laiko sudėtingumas     
 
 
    Erdvės sudėtingumas     
  
 
 
 
 
 
    Įdėjimas     
 
 O(N)  
 
 
 O(N)  
  
 
 
 
    Išankstinis užsakymas „Traversal“.     
 
 O(N)  
 
 
 O(N)  
  
 
 
 
 
 Inorder Traversal  
  
 
 
 O(N)  
  
 
 
 O(N)  
  
 
 
 
 Pašto užsakymų pervežimas  
 
 O(N)  
 
 
 O(N)  
  
 
 
 
 Lygio tvarka  
 
 O(N)  
 
 
 O(N)  
  
 
 
 
 
 Ištrynimas  
  
 
 
 O(N)  
  
 
 
 O(N)  
  
 
 
 
 
 Ieškoma  
  
 
 
 O(N)  
  
 
 
 O(N)  
  
 
 
 
 
 Galime naudoti      Morrisas Traversalis              pereiti visus dvejetainio medžio mazgus per O(1) laiką.  
  
 Dvejetainio medžio privalumai  
 
 
    Efektyvi paieška:     Dvejetainiai medžiai yra veiksmingi ieškant konkretaus elemento, nes kiekvienas mazgas turi daugiausia du antrinius mazgus, leidžiančius       Efektyvi atmintis:     Dvejetainiams medžiams reikia mažiau atminties, palyginti su kitomis medžio duomenų struktūromis, todėl jie taupo atmintį.   
 
  Dvejetainius medžius palyginti lengva įdiegti ir suprasti, nes kiekvienas mazgas turi daugiausia du vaikus, kairįjį ir dešinįjį.   
 
 
  Dvejetainio medžio trūkumai   
 
 
     Ribota struktūra:     Dvejetainiai medžiai ribojami iki dviejų antrinių mazgų viename mazge, o tai gali apriboti jų naudingumą tam tikrose programose. Pavyzdžiui, jei medžiui reikia daugiau nei dviejų antrinių mazgų viename mazge, gali būti tinkamesnė kitokia medžio struktūra.   
 
     Nesubalansuoti medžiai:     Nesubalansuoti dvejetainiai medžiai, kai vienas pomedis yra žymiai didesnis už kitą, gali lemti neefektyvias paieškos operacijas. Taip gali nutikti, jei medis nėra tinkamai subalansuotas arba jei duomenys įterpiami neatsitiktina tvarka.   
 
     Erdvės neefektyvumas:     Dvejetainiai medžiai gali būti neefektyvūs, palyginti su kitomis duomenų struktūromis. Taip yra todėl, kad kiekvienam mazgui reikia dviejų antrinių rodyklių, o tai gali būti daug atminties dideliems medžiams.   
 
     Lėtas veikimas blogiausiu atveju:     Blogiausiu atveju dvejetainis medis gali išsigimti arba iškreipti, o tai reiškia, kad kiekvienas mazgas turi tik vieną vaiką. Tokiu atveju paieškos operacijos gali sumažėti iki O(n) laiko sudėtingumo, kur n yra medžio mazgų skaičius.   
 
 
     Dvejetainio medžio programos      
 
 
  Dvejetainis medis gali būti naudojamas     reprezentuoja hierarchinius duomenis     .   
 
  Naudojami Huffman kodavimo medžiai     duomenų glaudinimo algoritmai     .   
 
     Prioritetinė eilė    yra dar viena dvejetainio medžio programa, naudojama ieškant maksimalaus arba minimumo O(1) laiko sudėtingumu.  
 
 Naudinga indeksuojant segmentuotą duomenų bazėje, naudinga saugoti talpyklą sistemoje,  
 
 Dvejetainiai medžiai gali būti naudojami sprendimų medžiams įgyvendinti – tai mašininio mokymosi algoritmo tipas, naudojamas klasifikavimui ir regresinei analizei.  
 
 
 Dažnai užduodami klausimai apie dvejetainį medį  
 
 1. Kas yra dvejetainis medis?  
 
 
 Dvejetainis medis yra nelinijinė duomenų struktūra, susidedanti iš mazgų, kur kiekvienas mazgas turi daugiausiai po du vaikus (kairysis antrinis ir dešinysis vaikas).  
  
 
 2. Kokios yra dvinarių medžių rūšys?  
 
 
 Dvejetainius medžius galima suskirstyti į įvairius tipus, įskaitant pilnus dvejetainius medžius, pilnus dvinarius medžius, tobulus dvejetainius medžius, subalansuotus dvejetainius medžius (pvz., AVL medžius ir raudonai juodus medžius) ir išsigimusius (arba patologinius) dvejetainius medžius.  
  
 
 3. Koks yra dvejetainio medžio aukštis?  
 
 
 Dvejetainio medžio aukštis yra ilgiausio kelio nuo šaknies mazgo iki lapo mazgo ilgis. Tai rodo kraštų skaičių ilgiausiu keliu nuo šaknies mazgo iki lapo mazgo.  
  
 
 4. Koks yra dvejetainio medžio mazgo gylis?  
 
 
 Dvejetainio medžio mazgo gylis yra kelio ilgis nuo šakninio mazgo iki konkretaus mazgo. Šaknies mazgo gylis yra 0.  
  
 
 5. Kaip atliekate medžio perėjimą dvejetainiame medyje?  
 
 
 Medžio perkėlimas dvejetainiame medyje gali būti atliekamas įvairiais būdais: perėjimas pagal užsakymą, perėjimas iš anksto, perėjimas po užsakymo ir perėjimas pagal lygį (taip pat žinomas kaip pločio eiga).  
  
 
 6. Kas yra Inorder perėjimas dvejetainiame medyje?  
 
 
 Inorder traversal mazgai rekursyviai lankomi tokia tvarka: kairysis vaikas, šaknis, dešinysis vaikas. Dėl šios perėjimo mazgai lankomi dvejetainiame paieškos medyje nemažėjančia tvarka.  
  
 
 7. Kas yra išankstinio užsakymo perkėlimas dvejetainiame medyje?  
 
 
 Išankstinio užsakymo eigoje mazgai rekursyviai lankomi tokia tvarka: šaknis, kairysis antrinis, dešinysis antrinis. Dėl šio perėjimo šakninis mazgas yra pirmasis aplankytas mazgas.  
  
 
 8. Kas yra postorder traversal dvejetainiame medyje?  
 
 
 Postorder traversal mazgai rekursyviai lankomi tokia tvarka: kairysis antrinis, dešinysis vaikas ir šaknis. Dėl šio perėjimo šakninis mazgas yra paskutinis aplankytas mazgas.  
  
 
 9. Kuo skiriasi dvejetainis medis nuo dvejetainio paieškos medžio?  
 
 
 Dvejetainis medis yra hierarchinė duomenų struktūra, kurioje kiekvienas mazgas turi daugiausia du antrinius elementus, o dvejetainis paieškos medis yra dvejetainio medžio tipas, kuriame kairiajame antriniame mazgo reikšmes yra mažesnės nei mazgo reikšmės, o dešiniajame antriniame yra verčių. didesnė už mazgo vertę.  
  
 
    10. Kas yra subalansuotas dvejetainis medis?     
 
 
 Subalansuotas dvejetainis medis yra dvejetainis medis, kuriame kiekvieno mazgo kairiojo ir dešiniojo pomedžio aukštis skiriasi daugiausia vienu. Subalansuoti medžiai padeda išlaikyti efektyvias operacijas, tokias kaip paieška, įterpimas ir trynimas, kai laiko sudėtingumas yra artimas O (log n).  
  
 
 Išvada:  
 
 Medis yra hierarchinė duomenų struktūra. Pagrindiniai medžių naudojimo būdai yra hierarchinių duomenų palaikymas, vidutinės prieigos suteikimas ir įterpimo / ištrynimo operacijos. Dvejetainiai medžiai yra ypatingi medžio atvejai, kai kiekvienas mazgas turi daugiausia du vaikus.  
  
 Susiję straipsniai:  
 
 
  Dvejetainio medžio savybės   
 
  Dvejetainių medžių rūšys