A Binärer Suchbaum ist eine Datenstruktur, die in der Informatik zur sortierten Organisation und Speicherung von Daten verwendet wird. Jeder Knoten in a Binärer Suchbaum hat höchstens zwei Kinder, a links Kind und a Rechts Kind, mit dem links Kind, das Werte enthält, die kleiner sind als der Elternknoten und der Rechts untergeordneter Knoten, der Werte enthält, die größer als der übergeordnete Knoten sind. Diese hierarchische Struktur ermöglicht eine effiziente suchen , Einfügen , Und Streichung Operationen an den im Baum gespeicherten Daten.
Binärer Suchbaum
Einführung in die binäre Suche:
- Anwendungen von BST
- Anwendung, Vor- und Nachteile des binären Suchbaums
Grundlegende Operationen auf BST:
- Einfügen in den binären Suchbaum
- Suche im binären Suchbaum
- Löschen im binären Suchbaum
- Binary Search Tree (BST) Traversals – Inorder, Preorder, Post Order
- Wandeln Sie einen normalen BST in einen ausgeglichenen BST um
Einfache Standardaufgaben zu BST:
- Iterative Suche im binären Suchbaum
- Ein Programm zum Überprüfen, ob ein Binärbaum BST ist oder nicht
- Konvertierung von binärem Baum in binären Suchbaum
- Suchen Sie den Knoten mit dem Mindestwert in einem binären Suchbaum
- Überprüfen Sie, ob ein Array die Reihenfolge des binären Suchbaums darstellt oder nicht
- Wie kann man feststellen, ob ein Binärbaum höhenausgeglichen ist?
- Sortiertes Array zu ausgeglichenem BST
- Suchen Sie nach identischen BSTs, ohne die Bäume zu erstellen
- Konvertieren Sie BST in Min Heap
- Zweitgrößtes Element in BST
- Fügen Sie alle größeren Werte zu jedem Knoten in einem bestimmten BST hinzu
- Überprüfen Sie, ob zwei BSTs denselben Satz von Elementen enthalten
- Summe der k kleinsten Elemente in BST
Mittlere Standardprobleme bei BST:
- Konstruieren Sie BST aus gegebener Vorbestellungsdurchquerung | Set 1
- Sortierte verknüpfte Liste zu ausgewogenem BST
- Transformieren Sie einen BST in einen Baum mit größerer Summe
- BST zu einem Baum mit der Summe aller kleineren Schlüssel
- Konstruieren Sie BST aus der Durchquerung der gegebenen Ebenenreihenfolge
- Überprüfen Sie, ob das angegebene Array den Level Order Traversal des binären Suchbaums darstellen kann
- Niedrigster gemeinsamer Vorfahre in einem binären Suchbaum
- Finden Sie das k-kleinste Element in BST (Ordnungsstatistik in BST).
- K'th Größtes Element in BST, das konstant zusätzlichen Platz beansprucht
- Größte Zahl in BST, die kleiner oder gleich N ist
- Finden Sie den Abstand zwischen zwei Knoten eines binären Suchbaums
- Größter BST in einem Binärbaum | Satz 2
- Entfernen Sie alle Blattknoten aus dem binären Suchbaum
- Inorder-Nachfolger im binären Suchbaum
- Finden Sie ein Paar mit der angegebenen Summe in BST
- Maximales Element zwischen zwei Knoten von BST
- Finden Sie den größten BST-Teilbaum in einem bestimmten Binärbaum
- Finden Sie ein Paar mit der angegebenen Summe in einem ausgeglichenen BST
- Zwei Knoten eines BST sind vertauscht, korrigieren Sie den BST
- Wie gehe ich mit Duplikaten im binären Suchbaum um?
- Blattknoten aus der Vorbestellung eines binären Suchbaums (unter Verwendung von Rekursion)
Harte Standardprobleme bei BST:
- Konstruieren Sie alle möglichen BSTs für die Schlüssel 1 bis N
- Konvertieren Sie BST direkt in einen Min-Heap
- Überprüfen Sie, ob ein gegebenes Array der Größe n den BST von n Ebenen darstellen kann oder nicht
- Führen Sie zwei BSTs mit begrenztem zusätzlichen Platz zusammen
- K'tes größtes Element in BST, wenn eine Änderung an BST nicht zulässig ist
- Überprüfen Sie, ob die angegebene sortierte Teilsequenz im binären Suchbaum vorhanden ist
- Maximales eindeutiges Element in jedem Subarray der Größe K
- Zählen Sie Paare aus zwei BSTs, deren Summe einem gegebenen Wert x entspricht
- BST-Schlüssel im angegebenen Bereich drucken | O(1) Leerzeichen
- Inorder-Vorgänger und -Nachfolger für einen bestimmten Schlüssel in BST
- Finden Sie heraus, ob es in einem ausgeglichenen BST ein Triplett gibt, das sich zu Null addiert
- Ersetzen Sie jedes Element durch das kleinste größere Element rechts davon
- Inversionen in einem Array zählen | Set 2 (mit selbstausgleichendem BST)
- Blattknoten aus der Vorbestellung eines binären Suchbaums
- Minimal möglicher Wert von |ai + aj – k| für gegebenes Array und k.
- Spezielle zweistellige Zahlen in einem binären Suchbaum
- Zwei ausgeglichene binäre Suchbäume zusammenführen
Einige Quizze:
- „Quiz“ zum binären Suchbaum
- „Quiz“ zu ausgewogenen binären Suchbäumen
Quicklinks:
- Videos zum binären Suchbaum
Empfohlen:
- Lernen Sie Datenstruktur und Algorithmen | DSA-Tutorial