Binärbaum in Datenstruktur (BEISPIEL)
Sarah Chen
Was ist ein Binärbaum?
Das Wort binär bedeutet zwei. In der Baumdatenstruktur bezeichnet „Binärbaum“ einen Baum, in dem jeder Knoten maximal zwei untergeordnete Knoten (linker und rechter Knoten) haben kann. Es ist ein einfacher Binärbaum.
Es gibt jedoch einen anderen Binärbaum, der am häufigsten verwendet wird und mehrere Anwendungsfälle hat. Er heißt Binärer Suchbaum (BST). Dieser Baum kann den Suchalgorithmus deutlich beschleunigen, genauer gesagt mit einer log(n)-Zeitkomplexität. In der Datenstruktur steht n für die Anzahl der Knoten im Binärbaum.
Was sind die Unterschiede zwischen Binärbaum und Binärsuchbaum?
Der Unterschied zwischen dem BST und dem regulären Binärbaum besteht darin, dass der linke BST-Knoten einen kleineren Wert als der Wurzelknoten und der rechte Knoten einen größeren Wert als der Wurzelknoten hat. Der linke Teilbaum enthält also immer einen kleineren Wert als die Wurzel, und der rechte Teilbaum enthält immer einen größeren Wert als die Wurzel.
Beispiel für binäre Suchbäume
Lassen Sie uns das Konzept des binären Suchbaums anhand des folgenden Beispiels demonstrieren.
Hier können Sie alle Knoten der vorgegebenen Disziplin folgen. Es gibt eine Formel für die maximale Anzahl von Knoten im binären Suchbaum. Wenn wir den obigen Baum betrachten, können wir sehen, dass jeder Knoten außer allen Blattknoten zwei untergeordnete Knoten hat. Und die Höhe (h) des angegebenen Binärbaums beträgt 4. Die Formel lautet 2h - 1. Es ergibt also 15.
Das oben dargestellte Bild ist kein vollständiger Binärbaum oder ausgeglichener Binärbaum, sondern wird als vollständiger Binärbaum oder ausgeglichener Binärbaum bezeichnet. Es gibt eine andere Datenstruktur namens AVL (eine andere Art von Binärbaum), die die Höhe des Binärbaums optimiert und die Suche nach dem BST schneller durchführt, wie in Abb. 3.
Versuchen Sie, die geordnete Durchquerung des oben angegebenen Binärbaums zu berechnen. Sie werden feststellen, dass Sie ein nicht abnehmendes sortiertes Array erhalten und die Durchquerungsalgorithmen dieselben sind wie beim Binärbaum.
Arten von Binärbäumen
Hier sind einige wichtige Arten von Binärbäumen:
- Vollständiger Binärbaum: Jeder Knoten in diesem Binärbaum kann 0 oder 2 untergeordnete Knoten haben. In dieser Art von Binärbaum ist nur ein untergeordneter Knoten nicht zulässig. Mit Ausnahme des Blattknotens haben also alle Knoten zwei untergeordnete Knoten.
- Vollständiger Binärbaum: Jeder Knoten kann 0 oder 2 Knoten haben. Es sieht aus wie der vollständige Binärbaum, aber alle Blattelemente sind zum linken Teilbaum geneigt, wohingegen sich im vollständigen Binärbaum Knoten im rechten oder linken Teilbaum befinden können.
- Perfekter Binärbaum: Alle Knoten müssen 0 oder 2 Knoten haben und alle Blattknoten sollten sich auf derselben Ebene oder Höhe befinden. Das obige Beispiel einer vollständigen Binärbaumstruktur ist kein perfekter Binärbaum, da Knoten 6 und Knoten 1,2,3 nicht auf derselben Höhe liegen. Aber das Beispiel des vollständigen Binärbaums ist ein perfekter Binärbaum.
- Entarteter Binärbaum: Jeder Knoten kann nur ein einziges Kind haben. Alle Operationen wie Suchen, Einfügen und Löschen dauern O(N) Zeit.
- Ausgeglichener Binärbaum: In diesem Binärbaum beträgt der Höhenunterschied zwischen linkem und rechtem Teilbaum höchstens 1. Wenn wir also einen Knoten hinzufügen oder löschen, müssen wir die Höhe des Baums wieder ausgleichen. Diese Art von selbstausgeglichenem Binärbaum wird als „Self-Balanced Binary Tree“ bezeichnet AVL-Baum.
Es gibt drei grundlegende BST-Operationen. Diese werden im Folgenden ausführlich erläutert.
Implementierung eines binären Baums in C und 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);
}
Ausgang:
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
Implementierung des Binärbaums 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)
Ausgang:
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
Anwendung des Binärbaums
Hier sind einige häufige Anwendungen von Binary Tree:
- Knotendaten in sortierter Reihenfolge organisieren
- Wird in Map- und Set-Node-Objekten in Programmiersprachenbibliotheken verwendet.
- Suchen nach Elementen in den Datenstrukturen
» Erfahren Sie in unserem nächsten Tutorial mehr über Kombinationsalgorithmus