suchen
HeimWeb-Frontendjs-TutorialBinäre Suchbäume (BST) verstehen

Ich habe einige Probleme im Zusammenhang mit binären Suchbäumen gelöst und dachte, es könnte interessant sein, mein Gedächtnis zu überprüfen und das, was ich gelernt habe, mit meinen Followern zu teilen! Also los geht's:

Was ist ein binärer Suchbaum (BST)?

Ein binärer Suchbaum (BST) ist eine grundlegende Datenstruktur in der Informatik, die ein effizientes Suchen, Einfügen und Löschen von Daten ermöglicht. Es handelt sich um eine baumbasierte Struktur, bei der jeder Knoten höchstens zwei Kinder hat und das linke Kind immer kleiner ist als der Elternknoten, während das rechte Kind schon ist größer.

Hauptmerkmale eines BST

1. Effiziente Suche: Mit einer zeitlichen Komplexität von O(log n) für ausgeglichene Bäume.

2. Dynamische Struktur: Knoten können dynamisch hinzugefügt oder entfernt werden.

3. Hierarchische Darstellung: Nützlich bei der hierarchischen Datendarstellung, wie einem Dateisystem oder einem Stammbaum.


Lassen Sie uns in die praktische Implementierung eines binären Suchbaums mithilfe von TypeScript eintauchen.

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    root: Node | null;

    constructor() {
        this.root = null;
    }

    insert(value: number): void {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }

        let currentNode = this.root;
        while (true) {
            if (value  Root -> Right
    inOrderTraversal(node: Node | null = this.root): void {
        if (node !== null) {
            this.inOrderTraversal(node.left);
            console.log(node.value);
            this.inOrderTraversal(node.right);
        }
    }
}

// Usage
const bst = new BinarySearchTree();
bst.insert(47);
bst.insert(21);
bst.insert(76);
bst.insert(18);
bst.insert(52);
bst.insert(82);

console.log("Contains 21:", bst.contains(21)); // true
console.log("Contains 99:", bst.contains(99)); // false

console.log("In-order Traversal:");
bst.inOrderTraversal();


Diagrammdarstellung des BST

So würde der binäre Suchbaum nach dem Einfügen der Werte 47, 21, 76, 18, 52, 82 aussehen:

Understanding Binary Search Trees (BST)


Wie es funktioniert

  1. Einfügen: Neue Werte werden basierend auf Vergleichen platziert. Kleinere Werte gehen nach links und größere Werte nach rechts.

  2. Suche (Enthält): Je nach Wert nach links oder rechts durchlaufen, bis der Knoten gefunden wird oder die Durchquerung an einem Nullknoten endet.

  3. Traversal: In-Order-Traversal besucht Knoten in sortierter Reihenfolge (Links -> Root -> Rechts).


Warum binäre Suchbäume verwenden?

  1. Effiziente Suchvorgänge: Die Suche in einem BST kann sehr effizient sein, wenn der Baum ausgeglichen ist.

  2. Dynamische Größe: Sie können Elemente hinzufügen oder entfernen, ohne die Größe von Arrays ändern oder Elemente verschieben zu müssen.

  3. Sortierte Daten: Durchläufe stellen Daten in sortierter Reihenfolge bereit, was in Szenarien wie Prioritätswarteschlangen und In-Memory-Datenbanken nützlich ist.


Randfälle, die Sie im Hinterkopf behalten sollten

  1. Duplikate: Standard-BSTs verarbeiten standardmäßig keine doppelten Werte. Möglicherweise müssen Sie Logik implementieren, um Duplikate zuzulassen oder abzulehnen, z. B. das Speichern einer Zählung in jedem Knoten oder das Überspringen doppelter Einfügungen.

  2. Unausgeglichene Bäume: Wenn Werte in sortierter Reihenfolge eingefügt werden (z. B. 1, 2, 3, 4, ...), wird der BST verzerrt und verschlechtert sich zu einer verknüpften Liste mit O(n) Zeitkomplexität für Operationen. Der Einsatz von selbstausgleichenden BSTs (z. B. AVL-Bäume, Rot-Schwarz-Bäume) hilft, dieses Problem zu mildern.

  3. Leerer Baum: Überprüfen Sie immer, ob der Baum leer ist (d. h. this.root === null), um Laufzeitfehler bei Vorgängen wie „Contains“ oder „Traversal“ zu verhindern.

  4. Randknoten: Berücksichtigen Sie in Szenarien wie dem Entfernen von Knoten Randfälle, z. B. Knoten mit nur einem Kind, ohne Kinder oder als Wurzelknoten.

  5. Leistung: Wenn Ihr Datensatz groß ist oder in sortierten Blöcken vorliegt, sollten Sie eine Neuausrichtung oder die Verwendung einer geeigneteren Datenstruktur für effiziente Suchvorgänge in Betracht ziehen.

Um die Effizienz sicherzustellen, sollte der BST ausgeglichen bleiben. Unausgeglichene Bäume können die Leistung auf O(n) verschlechtern. Erwägen Sie die Verwendung selbstausgleichender Bäume wie AVL oder Rot-Schwarz-Bäume für eine durchgängig optimierte Leistung. Über die anderen Bäume werde ich später in einem Beitrag sprechen.


Anwendungsfälle von BSTs in Softwareanwendungen

Binäre Suchbäume (BSTs) sind mehr als nur eine Datenstruktur, die man in Lehrbüchern findet – sie haben unzählige praktische Anwendungen! Hier sind einige praktische Möglichkeiten, wie BSTs in der Informatik verwendet werden:

  • Datenbanken und Indizierung: Ausgeglichene BSTs (wie AVL oder Red-Black Trees) finden bei der Datenbankindizierung häufig im Hintergrund statt. Sie machen Bereichsabfragen und Suchvorgänge äußerst effizient.

  • In-Memory sortierte Daten: Müssen Sie die Daten sortiert halten, während Sie dynamisch hinzufügen und suchen? BSTs sind Ihre Anlaufstelle. Denken Sie an Echtzeitanalyse- oder Überwachungssysteme.

  • Symboltabellen in Compilern: Compiler verlassen sich auf BSTs, um Symboltabellen zum Speichern und schnellen Zugriff auf Bezeichner und ihre Attribute zu implementieren.

  • Autovervollständigung und Rechtschreibprüfung: Haben Sie sich jemals gefragt, wie die automatische Vervollständigung funktioniert? BST-Varianten wie ternäre Suchbäume werden verwendet, um Wörterbücher effizient zu organisieren.

  • Prioritätsplanung: Während Heaps häufiger vorkommen, können BSTs auch in dynamischen Planungssystemen verwendet werden, in denen sich Prioritäten ständig ändern.

  • Geografische Daten (GIS): BSTs helfen in GIS-Systemen, indem sie räumliche Daten speichern und abrufen – z. B. das Finden von Standorten in der Nähe oder das Filtern nach einem Bereich.

  • Datenkomprimierung: Die Huffman-Codierung, ein wichtiger Bestandteil von Datenkomprimierungsalgorithmen, verwendet eine spezielle Art von Binärbaum, um Datensymbolen Codes variabler Länge zuzuweisen.

  • Gaming-Systeme: BSTs ermöglichen dynamische Bestenlisten und Anzeigetafeln, indem sie die Ergebnisse sortiert halten und Ranglisten in Echtzeit abrufen.

  • Netzwerk und Routing: Routing-Tabellen basieren manchmal auf BST-ähnlichen Strukturen, um effiziente Pfade für die Datenübertragung zu bestimmen.

  • Versionskontrollsysteme: Systeme wie Git verwenden baumartige Strukturen (BST-inspiriert), um Commits und Versionen innerhalb eines Directed Asymmetric Graph (DAG) effizient zu verwalten.

BSTs gibt es überall, von der Stromversorgung der Werkzeuge, die wir täglich verwenden, bis hin zur Lösung komplexer Rechenprobleme. Ziemlich cool, oder?

Aber es ist wichtig, sich ihrer Einschränkungen und Grenzfälle bewusst zu sein. Wenn Sie diese Nuancen verstehen, können Sie effizientere und zuverlässigere Systeme entwerfen.

Sind Sie bei der Arbeit mit BSTs auf interessante Herausforderungen oder Lösungen gestoßen? Lassen Sie uns unten diskutieren! ?

Das obige ist der detaillierte Inhalt vonBinäre Suchbäume (BST) verstehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Ersetzen Sie Stringzeichen in JavaScriptErsetzen Sie Stringzeichen in JavaScriptMar 11, 2025 am 12:07 AM

Detaillierte Erläuterung der Methode für JavaScript -Zeichenfolge und FAQ In diesem Artikel werden zwei Möglichkeiten untersucht, wie String -Zeichen in JavaScript ersetzt werden: Interner JavaScript -Code und interne HTML für Webseiten. Ersetzen Sie die Zeichenfolge im JavaScript -Code Die direkteste Möglichkeit ist die Verwendung der Ersatz () -Methode: str = str.replace ("find", "ersetzen"); Diese Methode ersetzt nur die erste Übereinstimmung. Um alle Übereinstimmungen zu ersetzen, verwenden Sie einen regulären Ausdruck und fügen Sie das globale Flag G hinzu:: STR = Str.Replace (/fi

Erstellen Sie Ihre eigenen AJAX -WebanwendungenErstellen Sie Ihre eigenen AJAX -WebanwendungenMar 09, 2025 am 12:11 AM

Hier sind Sie also bereit, alles über dieses Ding namens Ajax zu lernen. Aber was genau ist das? Der Begriff AJAX bezieht sich auf eine lose Gruppierung von Technologien, mit denen dynamische, interaktive Webinhalte erstellt werden. Der Begriff Ajax, ursprünglich von Jesse J geprägt

10 JQuery Fun- und Games -Plugins10 JQuery Fun- und Games -PluginsMar 08, 2025 am 12:42 AM

10 Fun JQuery Game -Plugins, um Ihre Website attraktiver zu machen und die Stickinität der Benutzer zu verbessern! Während Flash immer noch die beste Software für die Entwicklung von lässigen Webspielen ist, kann JQuery auch überraschende Effekte erzielen und zwar nicht mit reinen Action -Flash -Spielen vergleichbar sind, aber in einigen Fällen können Sie auch einen unerwarteten Spaß in Ihrem Browser haben. JQuery Tic Toe Game Die "Hello World" der Game -Programmierung hat jetzt eine Jquery -Version. Quellcode JQuery Crazy Word Kompositionsspiel Dies ist ein Spiel mit der Füllung, und es kann einige seltsame Ergebnisse erzielen, da das Wort nicht kennt. Quellcode JQuery Mine Sweeping Game

JQuery Parallax Tutorial - Animated Header HintergrundJQuery Parallax Tutorial - Animated Header HintergrundMar 08, 2025 am 12:39 AM

Dieses Tutorial zeigt, wie ein faszinierender Parallaxen -Hintergrundeffekt mit JQuery erstellt wird. Wir werden ein Header -Banner mit geschichteten Bildern bauen, die eine atemberaubende visuelle Tiefe erzeugen. Das aktualisierte Plugin funktioniert mit JQuery 1.6.4 und später. Laden Sie die herunter

Wie erstelle ich meine eigenen JavaScript -Bibliotheken?Wie erstelle ich meine eigenen JavaScript -Bibliotheken?Mar 18, 2025 pm 03:12 PM

In Artikel werden JavaScript -Bibliotheken erstellt, veröffentlicht und aufrechterhalten und konzentriert sich auf Planung, Entwicklung, Testen, Dokumentation und Werbestrategien.

Wie optimiere ich den JavaScript -Code für die Leistung im Browser?Wie optimiere ich den JavaScript -Code für die Leistung im Browser?Mar 18, 2025 pm 03:14 PM

In dem Artikel werden Strategien zur Optimierung der JavaScript -Leistung in Browsern erörtert, wobei der Schwerpunkt auf die Reduzierung der Ausführungszeit und die Minimierung der Auswirkungen auf die Lastgeschwindigkeit der Seite wird.

Erste Schritte mit Matter.js: EinführungErste Schritte mit Matter.js: EinführungMar 08, 2025 am 12:53 AM

Matter.js ist eine in JavaScript geschriebene 2D -Motorhilfe -Physik -Engine. Diese Bibliothek kann Ihnen helfen, die 2D -Physik in Ihrem Browser problemlos zu simulieren. Es bietet viele Merkmale, wie die Möglichkeit, starre Körper zu erstellen und physikalische Eigenschaften wie Masse, Fläche oder Dichte zuzuweisen. Sie können auch verschiedene Arten von Kollisionen und Kräften simulieren, wie z. B. die Schwerkraft Reibung. Matter.js unterstützt alle Mainstream -Browser. Darüber hinaus ist es für mobile Geräte geeignet, da es Berührungen erkennt und reagiert. Alle diese Funktionen machen es Ihre Zeit wert, zu lernen, wie man die Engine benutzt. In diesem Tutorial werde ich die Grundlagen dieser Bibliothek, einschließlich ihrer Installation und Nutzung, behandeln und a bereitstellen

Automatische Aktualisierung der Div -Inhalte mit JQuery und AjaxAutomatische Aktualisierung der Div -Inhalte mit JQuery und AjaxMar 08, 2025 am 12:58 AM

Dieser Artikel zeigt, wie Sie den Inhalt eines DIV automatisch alle 5 Sekunden mit JQuery und Ajax aktualisieren können. Das Beispiel holt und zeigt die neuesten Blog -Beiträge aus einem RSS -Feed zusammen mit dem letzten Aktualisierungstempel. Ein Ladebild ist Optiona

See all articles

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heiße Werkzeuge

SecLists

SecLists

SecLists ist der ultimative Begleiter für Sicherheitstester. Dabei handelt es sich um eine Sammlung verschiedener Arten von Listen, die häufig bei Sicherheitsbewertungen verwendet werden, an einem Ort. SecLists trägt dazu bei, Sicherheitstests effizienter und produktiver zu gestalten, indem es bequem alle Listen bereitstellt, die ein Sicherheitstester benötigen könnte. Zu den Listentypen gehören Benutzernamen, Passwörter, URLs, Fuzzing-Payloads, Muster für vertrauliche Daten, Web-Shells und mehr. Der Tester kann dieses Repository einfach auf einen neuen Testcomputer übertragen und hat dann Zugriff auf alle Arten von Listen, die er benötigt.

EditPlus chinesische Crack-Version

EditPlus chinesische Crack-Version

Geringe Größe, Syntaxhervorhebung, unterstützt keine Code-Eingabeaufforderungsfunktion

SAP NetWeaver Server-Adapter für Eclipse

SAP NetWeaver Server-Adapter für Eclipse

Integrieren Sie Eclipse mit dem SAP NetWeaver-Anwendungsserver.

Herunterladen der Mac-Version des Atom-Editors

Herunterladen der Mac-Version des Atom-Editors

Der beliebteste Open-Source-Editor

PHPStorm Mac-Version

PHPStorm Mac-Version

Das neueste (2018.2.1) professionelle, integrierte PHP-Entwicklungstool