Beste Antwort
Es gibt verschiedene Arten von Baumdatenstrukturen. Einige von ihnen sind
- Binärbaum : Dies ist die grundlegendste Basis der Baumstruktur. Wobei jeder Knoten maximal zwei untergeordnete Knoten haben kann. Ein perfekter Binärbaum ist ein Binärbaum, in dem alle inneren Knoten zwei untergeordnete und alle haben Blätter haben dieselbe Tiefe oder dieselbe Ebene. Ein vollständiger Binärbaum (manchmal als richtiger [15] oder ebener Binärbaum bezeichnet) ist ein Baum, in dem jeder Knoten im Baum entweder 0 oder 2 Kinder hat. In einem ist Binärbaum Jede Ebene, außer möglicherweise die letzte, ist vollständig gefüllt, und alle Knoten in der letzten Ebene sind so weit wie möglich links. Im unendlich vollständig Binärbaum, jeder Knoten hat zwei untergeordnete Elemente.
- Binärer Suchbaum: BST ist ein Binärbaum mit bestimmten Eigenschaften B. und das untergeordnete Element des angegebenen Knotens enthält einen Wert, der kleiner als der angegebene Knoten ist, und das rechte untergeordnete Element enthält einen Knoten, der größer als der angegebene Knoten ist.
- AVL-Baum oder höhenausgeglichener Binärbaum : Dies ist eine Variation des Binärbaums, bei der der Höhenunterschied zwischen dem linken und dem rechten Teilbaum höchstens 1 betragen kann. Wenn sie sich zu irgendeinem Zeitpunkt um mehr als eins unterscheiden, wird ein Neuausgleich durchgeführt Stellen Sie diese Eigenschaft wieder her. Das Suchen, Einfügen und Löschen dauert sowohl im Durchschnitt als auch im schlimmsten Fall O (log n), wobei n die Anzahl der Knoten im Baum vor der Operation ist.
- Rot-Schwarz-Baum : Eine andere Variante des Binärbaums, die dem AVL-Baum ähnelt, ist ein selbstausgleichender binärer Suchbaum. In diesem Baum sind die Knoten entweder rot oder schwarz gefärbt.
- Spreizbaum: Ein Spreizbaum ist ein sich selbst anpassender binärer Suchbaum mit dem Zusätzliche Eigenschaften, auf die kürzlich zugegriffen wurde, können schnell wieder auf Elemente zugreifen. Alle normalen Operationen in einem binären Suchbaum werden mit einer Grundoperation kombiniert, die als Spreizen bezeichnet wird. Wenn Sie den Baum für ein bestimmtes Element anzeigen, wird der Baum neu angeordnet, sodass das Element an der Wurzel des Baums platziert wird.
- N-ary tree: In diesem Baum wird die Begrenzung des Binärbaums aufgehoben. Hier kann ein Knoten höchstens n Kinder haben. Wie ein binärer Baum kann es ein vollständiger, vollständiger oder perfekter n-ary Baum sein. N-ary ist seit einiger Zeit als Wald bekannt.
- Trie-Struktur : In der Informatik ein Trie, auch digitaler Baum und manchmal Radix genannt Baum oder Präfixbaum (da sie nach Präfixen durchsucht werden können) ist eine geordnete Baumdatenstruktur, die zum Speichern einer dynamischen Menge oder eines assoziativen Arrays verwendet wird, in der die Schlüssel normalerweise Zeichenfolgen sind. Alle Nachkommen eines Knotens haben ein gemeinsames Präfix der diesem Knoten zugeordneten Zeichenfolge, und die Wurzel ist der leeren Zeichenfolge zugeordnet.
- Suffixbaum : Trie und Suffixbaum sind eng miteinander verbunden. Ein Suffixbaum (auch PAT-Baum oder in einer früheren Form Positionsbaum genannt) ist ein komprimierter Versuch, der alle Suffixe des angegebenen Textes als Schlüssel und Positionen im Text als Werte enthält. Suffixbäume ermöglichen besonders schnelle Implementierungen vieler wichtiger Zeichenfolgenoperationen.
- Huffman-Baum: Der Huffman-Baum ist ein frequenzsortierter Binärbaum, der beim Komprimieren häufig verwendet wird Daten. Der Huffman-Baum ist so konstruiert, dass er einem langen Text basierend auf seiner Häufigkeit ein kurzes Codewort zuweist.
- Heap-Struktur [Wie vorgeschlagen bearbeiten ]: Die Heap-Struktur ist eine weitere weit verbreitete Baumstruktur mit einer bestimmten Reihenfolgeseigenschaft. Es gibt zwei Arten von Heaps: Min-Heap und Max-Heap. In einem Min-Heap muss das übergeordnete Element eines Knotens kleiner sein als die Werte aller seiner untergeordneten Knoten. In ähnlicher Weise haben die Eltern im Max-Heap immer einen höheren Wert als alle ihre Kinder. Eine häufige Implementierung von Heap ist Binärer Heap, bei dem jeder Elternteil höchstens zwei untergeordnete Elemente haben kann.
Andere beliebte Baumstrukturen umfassen B. -Baum, B + – Baum, R-Baum, Zähl-B-Baum, KD-Baum (oder K-dimensionales BST), Entscheidungsbaum (a Variante von n-ary tree), Markelbaum, Fenwick-Baum (oder binärer Indexbaum), Bereichsbaum.
Antwort
- Vorlage als Code durch Bilden eines Abhängigkeitsbaums.
Nehmen Sie sich jetzt 5 Minuten Zeit, um ausführlich zu erklären, wie wir den Baum als Datenstruktur zur Lösung unseres komplexen Anwendungsfalls verwendet haben.
Um das Szenario zu erläutern, nehmen wir ein kleines Beispiel für das Abrufen von Daten von einer API über eine tokenbasierte Authentifizierung.
Wenn Sie dieses Kunststück erreichen möchten,
- Sie erhalten zuerst den Benutzernamen, das Kennwort und die Mandanteninformationen und rufen die API auf, um das Token abzurufen.
- Rufen Sie dann mit dem abgerufenen Token die aktive API auf, indem Sie diese in den Headern der Anforderung übergeben.
Dies ist ein sehr einfaches Szenario, aber die Dinge werden ziemlich komplex, wenn Sie eine Kette ausführen müssen von 10 APIs, die jeweils voneinander abhängig sind.
Hier haben wir diesen Ansatz für den Abhängigkeitsbaum entwickelt.
Zuerst müssen wir eine bilden Vorlage wie diese
Danach bilden wir einen Abhängigkeitsbaum wie diesen
Alles, was als $ {} definiert ist, bedeutete dies Es hängt von der Ausgabe anderer Variablen ab.
ResourceOps bedeutet, dass APIs ausgeführt werden müssen.
Auf diese Weise wird der Abhängigkeitsbaum erstellt.
- Wir bewerten Parameter, die unabhängig und unabhängig sind Hängen Sie sie an den Stamm an.
- Wir kommen dann zu Ressourcenoperationen und verstehen, dass dies von den an den Stammknoten angehängten Werten abhängt. Also lösen wir sie von der Wurzel und hängen sie dann an einen neuen Knoten an.
- Das Gleiche gilt für alle Ressourcenoperationen und Ausgabe.
Sobald wir den Abhängigkeitsbaum erstellt haben, gehen wir Führen Sie den Blattknoten aus, und führen Sie ihn zum übergeordneten Element mit dem Ergebnis der Blattknotenausführung aus. Anschließend ist er übergeordnet und übergeordnet, bis wir den obersten Knoten erreichen.
Sobald wir den obersten Knoten erreicht haben, erhalten wir das Ergebnis und kehren als http-Erfolgsantwort zurück.
Wenn bei der Ausführung ein Fehler auftritt, geben wir die Fehlerantwort lesbar zurück.
Ich glaube nicht, dass ich ein bisschen davon erklärt habe, aber ich möchte nur hervorheben, wie Wir haben ein reales Problem mit der Baumdatenstruktur gelöst, damit dynamische Aktionen ausgeführt werden können, ohne dass ein Entwickler Code schreibt.