5 Arten von Binärbäumen in der Datenstruktur erklärt

Ein Binärbaum ist eine nichtlineare Baumdatenstruktur, die jeden Knoten mit maximal 2 Kindern enthält. Der Binärname schlägt die Zahl 2 vor, sodass jeder Binärbaum ein linkes und ein rechtes Kind haben kann.

Ein Zeiger stellt einen binären Baum zum obersten Knoten dar, der normalerweise als Wurzel des Baums bekannt ist. Jeder Knoten in einem Binärbaum enthält Daten, einen Zeiger auf das linke Kind und einen Zeiger auf das rechte Kind. Zeiger werden verwendet, um einen binären Baum zu implementieren. Der Wurzelzeiger bezeichnet den ersten Knoten im Baum. Um einen Binärbaum zu erstellen, müssen Sie zuerst einen Knoten erstellen.

Nachdem Sie sich mitdem Binärbaum in der Datenstruktur vertraut gemacht haben , müssen Sie auch die grundlegenden Operationen kennen, die an einem Binärbaum ausgeführt werden.Sie können Funktionen wie das Einfügen eines Elements, das Entfernen eines Elements, das Suchen nach einem Element und das Durchlaufen des Binärbaums ausführen.

Jederbinäre Baum in der Datenstruktur wird beim Rechnen auf zwei verschiedene Arten verwendet.Erstens werden sie verwendet, um auf Knoten in Abhängigkeit von bestimmten Labels oder Werten zuzugreifen, die mit jedem Knoten verknüpft sind. Zweitens werden sie als Datendarstellungen mit einer relevanten verzweigten Struktur verwendet.

Bevor wir die verschiedenenArten von Binärbäumen durchgehen , machen wir uns zuerst mit den Terminologien vertraut, die in einem Binärbaumverwendet werden .

Knoten: Er enthält einen Datenwert in einem Binärbaum.

Wurzel: Der oberste Knoten in einem Binärbaum wird als Wurzel eines Baums bezeichnet.

Größe: Gibt die Anzahl der Knoten in einem Binärbaum an.

Elternknoten: Ein Knoten in einem Binärbaum mit einem Kind.

Kindknoten: Dies ist ein Knoten, der von einem Elternknoten stammt, der sich von der Wurzel des Binärbaums entfernt.

Interner Knoten: Es ist ein Knoten mit mindestens einem Kind in einem binären Baum.

Blattknoten: Es ist ein Knoten ohne Kind.Alternativ ist er ein externer Knoten.

Tiefe eines Knotenbaums: Sie wird im Kontext eines bestimmten Knotens berechnet.Sie wird als die Anzahl der Kanten von einem bestimmten Knoten zur Wurzel bezeichnet.

Interne Pfadlänge eines Baums: Sie bezieht sich auf die Summe der Ebenen jedes internen Knotens in einem Binärbaum.

Externe Pfadlänge eines Baums: Sie ist definiert als die Summe der Ebenen jedes externen Knotens in einem Binärbaum.

Knotenhöhe in einem Baum: Es ist die Anzahl der Kanten von einem bestimmten Knoten zum tiefsten Blattknoten des Binärbaums.Die Höhe der Wurzel wird immer größer sein als die anderer Knoten im Binärbaum.

Schauen wir uns nun die Details von 5Arten von Binärbäumen an.

Arten von Binärbäumen

1. Vollständiger Binärbaum

DieserBinärbaum in der Datenstruktur ist auch unter den Namen -Proper Binary Tree und Strict Binary Tree bekannt.Es ist eine der grundlegendstenArten von Binärbäumen in der Datenstruktur.Ein vollständiger Binärbaum ist als ein Binärbaum definiert, bei dem jeder Knoten zwei oder gar keine Kinder haben sollte.

Er wird alternativ als binärer Baum charakterisiert, in dem jeder Knoten mit Ausnahme der Blattknoten zwei Kinder umfasst. Die Knoten, in denen die Adresse des Wurzelknotens gespeichert ist, werden Kinderknoten der Wurzel genannt. Diese Knoten ohne Kinder werden Blattknoten genannt.

Sie müssen alle Knoten durchlaufen, um zu prüfen, ob ein Baum ein binärer Baum ist. Der Code gibt „False“ zurück, wenn irgendein Knoten ein Kind hat. Es wird „Wahr“ zurückgeben, wenn alle Knoten 0 oder 2 Kinder haben.

Hier sind die Eigenschaften eines vollständigen Binärbaums:

• Die Anzahl der Blattknoten ist gleich der Anzahl der internen Knoten + 1. Wenn beispielsweise die Anzahl der internen Knoten 4 beträgt, ist die Anzahl der Blattknoten gleich 5.
• Die maximale Anzahl von Knoten und die Anzahl von Knoten in einem Binärbaum sind gleich. Es wird als 2h+1 -1 dargestellt.
• Die minimale Anzahl von Knoten in einem vollständigen Binärbaum ist 2h-1.
• Die Mindesthöhe eines vollständigen Binärbaums ist log 2 (n+1) – 1.
• Die maximale Höhe eines vollständigen Binärbaums ist h = (n+1)/2.

2. Perfekter binärer Baum

Ein perfekter Binärbaum ist eine dieserArten von Binärbäumen , bei denen jeder Knoten 0 oder 2 Kinder haben muss und die Ebene jedes Blattknotens gleich sein muss.Mit anderen Worten, perfekteBinärbäume in der Datenstruktur sind als solche Bäume definiert, bei denen alle inneren Knoten zwei Zweige besitzen und die Knoten ohne Zweige (Blattknoten) auf derselben Ebene existieren.

In diesem Zusammenhang ist die Ebene eines Knotens der Abstand oder die Höhe vom Wurzelknoten. Einen perfekten Binärbaum kann man sich als vollständigen Binärbaum vorstellen, bei dem auch die letzte Ebene vollständig besetzt ist.

Lernen SieData Science-Kurseonline von den besten Universitäten der Welt.Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.

3. Vollständiger Binärbaum

Ein vollständiger Binärbaum ist eine dieser Arten von Binärbäumen in der Datenstruktur , bei denen alle Ebenen des Baums vollständig gefüllt sind.Die letzte Ebene des Binärbaums kann vollständig gefüllt sein oder auch nicht. Allerdings muss sich jeder Knoten auf der letzten Ebene des Knotens ganz links befinden. Die Knoten müssen von links aufgenommen werden.

Sie sind eine der wesentlichenArten von Binärbäumen, da sie das beste Verhältnis zwischen der Anzahl der Knoten und der Höhe eines Baums bieten.

Hier sind die wichtigsten Eigenschaften eines vollständigen Binärbaums:

• Die maximale Knotenzahl beträgt 2 h+1 – 1.
• Die Mindestknotenzahl beträgt 2 h .
• Die Mindesthöhe beträgt log 2 (n+1) – 1.

4. Ausgewogener Binärbaum

In ausgeglichenen Binärbäumen ist die Höhe eines Baums log 2 der Gesamtzahl der Knoten. Angenommen, die Höhe des Baums ist h und die Gesamtzahl der Knoten des Baums ist n. Die Gleichung zur Berechnung der Höhe lautet h = log(n). Der Höhenunterschied zwischen einem rechten Teilbaum und einem linken Teilbaum darf maximal „1“ betragen.

Die Differenz kann andere Werte wie 0 und -1 haben. Diese Arten von Binärbäumen werden auch als AVL-Bäume bezeichnet.Eines der bekanntesten Beispiele für balancierte Binärbäume ist der Rot-Schwarz-Baum.

Sie können den folgenden Code implementieren, um eine ausgeglichene Binärstruktur auszuführen.

privater Klassenknoten {

privater int-Wert;

privater Knoten links;

privater Knoten rechts;

}

public boolean isBalanced(Knoten n) {

if (balancedtreeHeight(n) > -1)

gib true zurück;

falsch zurückgeben;

}

public int balancetreeHeight(Knoten n) {

wenn (n == null)

0 zurückgeben;

int h1 = balancetreeHeight(n.right);

int h2 = balancetreeHeight(n.left);

wenn (h1 == -1 || h2 == -1)

Rückgabe -1;

wenn (Math.abs(h1 – h2) > 1)

Rückgabe -1;

wenn (h1 > h2)

gib h1 + 1 zurück;

gib h2 + 1 zurück;

}

Sehen Sie sich unsere US - Data Science-Programme an

5. Degenerierter Binärbaum

Ein degenerierter Binärbaum ist eine der weniger häufig verwendetenArten von binären Suchbäumen .Es ist ein binärer Baum, in dem jeder Knoten nur ein Kind hat, dh ein linkes oder rechtes Kind. Kein Knoten sollte sowohl linke als auch rechte Kinder haben.

Lesen Sie unsere beliebten US - Data Science-Artikel

Abschluss

Es ist wichtig zu verstehen,was ein Binärbaum in der Datenstruktur ist, wenn Sie ihn für verschiedene Anwendungen verwenden möchten.Die Implementierung verschiedener Funktionen in Binärbäumen kann Ihnen dabei helfen, Daten effizient zu organisieren und zu speichern.

Das Studium mehrerer Arten von Binärbäumen hilft Ihnen, Operationen in Zeitkomplexität effektiver durchzuführen. Die Data-Science-Grundlagen, einschließlich derbinären Baumdatenstruktur, helfen Ihnen, Ihre Data-Science-Reise einfach zu beginnen.Anschließend können Sie an fortgeschrittenen Data-Science-Projekten arbeiten, um Ihre Fähigkeiten und Ihr Portfolio zu erweitern.

Beginnen Sie Ihre Reise zum maschinellen Lernen auf upGrad

Wenn Sie Data Science lernen möchten, können Sie den Master of Science in Data Science von upGrad absolvieren . Dieser 24-monatige Kurs vermittelt Fähigkeiten wie Python, Bereitstellung von ML-Modellen, BD-Verarbeitung mit Spark, Predictive Analytics & Statistics sowie überwachte und nicht überwachte ML-Modelle. Der Studiengang eignet sich für ambitionierte Manager, MBA-Absolventen, Ingenieure und Professionals in verschiedenen Bereichen.

Der Abschluss dieses Kurses hilft Ihnen, als Data Engineer, Big Data Analyst, Machine Learning Engineer und Data Scientist zu arbeiten.