Der Wurzelknoten hat mindestens zwei untergeordnete Knoten

Jeder Nicht-Wurzelknoten hat mindestens M/2 (aufgerundet) Kinder und höchstens M Kinder.

Jeder Nicht-Root-Knoten verfügt über mindestens M/2-1 (aufgerundete) Schlüsselwörter und diese sind in aufsteigender Reihenfolge angeordnet

Der Wert des untergeordneten Knotens zwischen key[i] und key[i 1] liegt zwischen key[i] und key[i 1]

Alle Blattknoten befinden sich auf derselben Ebene

Natur

suchen

charakteristisch

Fügen Sie Zeiger auf Brüder zwischen den Nicht-Wurzel- und Nicht-Blattknoten des B-Baums hinzu

Unterthema 2

Der Prozess, bei dem ermittelt wird, ob in einer Sammlung von Datenelementen ein Datenelement mit einem Schlüssel vorhanden ist, der einem bestimmten Schlüssel entspricht.

Ergebnis

Suchstruktur

Suchkontext

statische Suche

dynamische Suche

Hash-Suche

Hash-Kollision

Hash-Funktion

Gängige Hash-Funktionen

geschlossenes Hashing

offenes Hashing

Wenn ein Element zur Menge hinzugefügt wird, werden k Hash-Funktionen verwendet, um das Element in k Punkten in einem Bit-Array abzubilden und sie auf 1 zu setzen. Beim Abrufen prüfen Sie einfach, ob sie alle 1 sind. Das ist in Ordnung da es eins gibt. Wenn es Null ist, ist es nicht, wenn alles 1 ist, ist es wahrscheinlich

Es geht darum, einen Satz unordentlicher Daten nach einer bestimmten Regel (aufsteigende oder absteigende Reihenfolge) zu organisieren.

Datenblatt

Sortiercode

Zwei Elemente R[i]R[j], ihr Sortiercode K[i]==K[j], und vor der Sortierung liegt das Element R[i] vor R[j] und die Elemente liegen zwischen R[i ] und Die Reihenfolge von R[j] bleibt unverändert

Sortieren durch Einfügen

Auswahl sortieren

Sortierung tauschen

Zusammenführen, sortieren

nicht vergleichende Sortierung

Scheitel

Seite

gerichteter Graph

Ungerichteter Graph

Wenn es in einem ungerichteten Graphen mit n Eckpunkten n*(n-1)/2 Kanten gibt, gibt es und gibt nur eine Kante zwischen zwei beliebigen Eckpunkten.

Wenn es in einem gerichteten Graphen mit n Eckpunkten n*(n-1) Kanten gibt, dann gibt es nur Kanten in entgegengesetzter Richtung zwischen zwei beliebigen Eckpunkten.

Wenn im ungerichteten Graphen G (u, v) eine Kante in E (G) ist, dann werden u und v als benachbarte Eckpunkte bezeichnet, und (u, v) soll mit den Eckpunkten u verbunden sein und v.

Wenn <u,v> im gerichteten Graphen G eine Kante in E(G) ist, dann heißt der Scheitelpunkt u neben v, und der Scheitelpunkt v grenzt an den Scheitelpunkt u und die Kante <u, v> soll die Summe der Scheitelpunkte sein, mit denen u und v verbunden sind

die Anzahl der damit verbundenen Kanten

Wenn es im Diagramm G = (V, E) eine Reihe von Kanten gibt, die vom Scheitelpunkt vi ausgehen und den Scheitelpunkt vj erreichen können, wird die Scheitelpunktsequenz vom Scheitelpunkt vi nach vj als Pfad vom Scheitelpunkt vi zum Scheitelpunkt vj bezeichnet.

Am Rand angebrachte Dateninformationen

Bei ungewichteten Diagrammen bezieht sich die Pfadlänge einer Kante auf die Anzahl der Kanten auf dem Pfad.

Bei gewichteten Diagrammen bezieht sich die Länge eines Pfades auf die Summe der Gewichte jeder Kante auf dem Pfad.

Wenn sich die Eckpunkte auf dem Pfad nicht wiederholen, wird ein solcher Pfad als einfacher Pfad bezeichnet. Wenn der erste Eckpunkt v1 und der letzte Eckpunkt vm auf dem Pfad zusammenfallen, wird ein solcher Pfad als Schleife oder Ring bezeichnet.

Angenommen, Graph G={V,E} und Graph G1={V1.E1}. Wenn V1 zu V und E1 zu E gehört, dann heißt G1 ein Untergraph von G.

Wenn in einem ungerichteten Graphen ein Pfad zwischen zwei Scheitelpunkten vorhanden ist, ist dieser verbunden. Wenn ein beliebiges Scheitelpunktpaar verbunden ist, wird der Graph als verbundener Graph bezeichnet.

In einem gerichteten Graphen gibt es zwischen jedem Paar von Scheitelpunkten vi und vj einen Pfad von vi nach vj, und es gibt auch einen Pfad von vj nach vi.

Der minimal verbundene Teilgraph eines verbundenen Graphen wird Spannbaum des Graphen genannt. Der Spannbaum eines verbundenen Graphen mit n Eckpunkten hat n Eckpunkte und n-1 Kanten.

Adjazenzmatrix

Adjazenzliste

Tiefe zuerst

Breite zuerst

Wenn es sich bei dem ungerichteten Diagramm um ein nicht verbundenes Diagramm handelt, kann der Tiefensuch- oder Breitensuchalgorithmus ausgehend von einem bestimmten Scheitelpunkt im Diagramm nicht alle Scheitelpunkte des Diagramms durchqueren, sondern nur auf alle Scheitelpunkte des größten zugreifen verbundener Teilgraph, in dem sich der Knoten befindet, bilden diese Eckpunkte eine verbundene Komponente

Kriterien

Treffen Sie bei der Lösung von Problemen immer die Wahl, die Ihnen im Moment am besten erscheint, also die lokal optimale Lösung.

Suchen Sie jedes Mal eine Kante mit dem kürzesten Gewicht und nicht mehr auf derselben verbundenen Komponente, um sie dem Spannbaum hinzuzufügen.

Finden Sie nebeneinander

Finden Sie ausgehend von einem Scheitelpunkt in einem gewichteten Diagramm den kürzesten Weg zu einem anderen Scheitelpunkt. Der kürzeste Weg ist die minimale Summe der Gewichte jeder Kante entlang des Pfades.

Daten

Datenelement

Datenelement

Datenstruktur

spezifisches Konzept

Algorithmus

Datenstruktur

Eine Beschreibung der Schritte zur Lösung eines bestimmten Problems, die in einem Computer als endliche Folge von Anweisungen dargestellt werden, wobei jede Anweisung eine oder mehrere Operationen darstellt

Eigenschaften des Algorithmus

Anforderungen an den Entwurfsalgorithmus

durchschnittliche Situation

Worst-Case-Szenario

Best-Case-Szenario

Allgemeine Algorithmus-O(n)-Berechnungsmethode

Zeitkomplexitätsberechnung des Divide-and-Conquer-Algorithmus

Zeitkomplexitätsberechnung eines rekursiven Algorithmus

Rekursiver Algorithmus Raumkomplexitätsalgorithmus

Ein Objekt wird als rekursiv bezeichnet, wenn es sich selbst teilweise enthält oder sich selbst definiert.

Eine Prozedur ruft sich selbst direkt oder indirekt auf

Teilen Sie das Problem in kleinere Probleme auf, die dieselbe Lösung wie das ursprüngliche Problem haben

Reduzieren Sie die Größe des Problems, sodass das neue Problem dieselbe Lösung wie das ursprüngliche Problem hat

Rekursiven Ausgang festlegen

Datenstrukturrekursion

Problemlösungsrekursion

Rekursiver Aufrufstapel

Schwanzrekursion

Zeitkomplexität

Zurückverfolgen

Vorteil

Mangel

Eine spezielle Art einer linearen Tabelle, die das Einfügen und Löschen von Daten nur an einem Ende ermöglicht

Die Datenelemente des sequentiellen Stapels und der Buchsequenztabelle sind gleich. Der Unterschied besteht darin, dass die Push- und Pop-Operationen des sequentiellen Stapels nur an der Spitze des aktuellen Stapels ausgeführt werden dürfen.

Ein Array implementiert zwei Stapel

Prinzip

Anwendungsszenarien

Kopfstopfen entfernt

Halterung passend

Umgekehrter polnischer Ausdruck

Labyrinth-Algorithmus

Implementierungsmethode eins

Implementierungsmethode zwei

falscher Überlauf

Echtes Überlaufphänomen

Eine Ende an Ende verbundene sequentielle Speicherwarteschlange ist eine kreisförmige Warteschlange.

Bestimmen, ob die Warteschlange voll oder leer ist

Die verknüpfte Speicherstruktur der Warteschlange ist eigentlich eine einfach verknüpfte Liste einer linearen Liste, mit der Ausnahme, dass sie nur den Schwanz rein und den Kopf raus haben kann.

Prioritätswarteschlange

Produzenten-Konsumenten-Modell

Nachrichtenwarteschlange

Warteschlangenphänomen

Netzwerkdatenübertragung

Eine Matrix mit vielen Elementen mit demselben Wert oder vielen Nullelementen und der Verteilung von Elementen mit demselben Wert oder Nullelementen weist ein bestimmtes Muster auf

Eine N*N-Matrix, jedes Aij = Aji

Symmetrischer Matrixkomprimierungsspeicher

Die Beziehung zwischen symmetrischen Matrizen und symmetrischem komprimiertem Speicher

M*N-Matrix, die Anzahl der gültigen Werte in der Matrix ist weitaus kleiner als die Anzahl der ungültigen Werte und die Verteilung ist unregelmäßig.

Sparse-Matrix-Komprimierungsspeicher

Vertauschen von Zeilen und Spalten

Schneller Rücklauf

Eine Menge bestehend aus N Knoten (N>=0)

Knoten

Grad des Knotens

Knoten mit Grad 0

Zweigknoten

Vorfahrenknoten

Nachkommenknoten

Elternknoten

Bruderknoten

Grad des Baumes

Knotenebene

Baumtiefe

geordneter Baum

ungeordneter Baum

Wald

Verzeichnisaufbau

Sammlung Venn-Diagramm

Elternvertretung

Kindervertretung

Eltern-Kind-Vertretung

Vertretung des Kindesbruders

Computerverzeichnis

Ein Binärbaum ist eine endliche Menge von Knoten. Die Menge ist entweder leer oder besteht aus einem Wurzelknoten und zwei Binärbäumen, die als linker Teilbaum und rechter Teilbaum bezeichnet werden.

Jeder Knoten hat höchstens zwei Teilbäume

Die Teilbäume eines Binärbaums können in linke und rechte Teilbäume unterteilt werden und ihre Reihenfolge kann nicht umgekehrt werden.

Alle Zweigknoten haben linke und rechte Teilbäume, und alle Blattknoten befinden sich auf derselben Ebene.

Wenn die Struktur eines Binärbaums mit N Knoten mit der Struktur der ersten N Knoten eines vollständigen Binärbaums übereinstimmt, spricht man von einem vollständigen Binärbaum.

Wenn die Ebene des Wurzelknotens mit 1 angegeben ist, gibt es höchstens 2^(i-1) (i>=1) Knoten auf der i-ten Ebene eines nicht leeren Binärbaums.

Wenn die Tiefe eines Binärbaums mit nur dem Wurzelknoten mit 1 angegeben wird, beträgt die maximale Anzahl von Knoten eines Binärbaums mit einer Tiefe von K 2^k-1 (k>=0).

Wenn für jeden Binärbaum die Anzahl der Blattknoten n0 und die Anzahl der Nicht-Blattknoten mit Grad 2 n2 beträgt, dann ist n0 = n2 · 1

Wenn für einen vollständigen Binärbaum mit n Knoten alle Knoten beginnend bei 0 in der Reihenfolge von oben nach unten und von links nach rechts nummeriert sind, dann gilt für den Knoten mit der Seriennummer i:

sequentielle Speicherung

Kettenspeicher

Simulationszeiger (statische verknüpfte Liste)

Erstellung eines Binärbaums

Durchquerung eines Binärbaums

Konvertieren Sie den Binärbaum entsprechend der Durchquerung des Binärbaums in eine lineare Sequenz

Rekursives Durchlaufen kann zu einem Stapelüberlauf führen

Die nicht rekursive Version macht das Programm möglicherweise weniger effizient

Es ist schwierig, den Vorgänger oder Nachfolger eines Knotens in einer bestimmten Traversierungsform zu finden.

Es gibt eine große Anzahl von Nullzeigerfeldern im Baum, die Verschwendung verursachen.

Wenn der linke Zeiger eines Knotens leer ist, soll der Zeiger auf den Vorgängerknoten des Knotens zeigen, der beim Durchlaufen des Binärbaums auf eine bestimmte Weise erhalten wurde.

Wenn der rechte Zeiger eines Knotens null ist, soll der Zeiger auf den Nachfolgeknoten des Knotens zeigen, der durch Durchlaufen des Binärbaums gemäß einer bestimmten Durchlaufmethode erhalten wurde.

Die Funktion besteht darin, zu unterscheiden, ob es sich um einen untergeordneten Knoten, einen Vorläufer oder einen Nachfolger handelt.

leftThread

rightThread

Zeiger auf den Vorgänger- oder Nachfolgerknoten im Knoten

Binärbaum mit Knoten des Binärbaums und Hinweisen

Speichern Sie alle Elemente in einem eindimensionalen Array in Form eines vollständigen Binärbaums und erfüllen Sie Ki<=K2*i 1 und Ki<=K2*i 2 (Ki>=K2*i 1 und Ki>=K2*i 2 ), dieser Heap wird als Min-Heap (Max-Heap) bezeichnet.

kleiner Haufen

großer Haufen

Wenn i=0, ist Knoten i der Wurzelknoten und hat keinen übergeordneten Knoten, andernfalls ist der übergeordnete Knoten von Knoten i (i-1)/2

Wenn 2*i 1>n-1, dann hat Knoten i kein linkes Kind, andernfalls ist das linke Kind von Knoten i Knoten 2*i 1

Wenn 2*i 1>n-1, dann hat Knoten i kein linkes Kind, andernfalls ist das linke Kind von Knoten i Knoten 2*i 2

Von oben nach unten anpassen

Prioritätswarteschlange

Weg

Pfadlänge

Der Baum mit der kleinsten gewichteten Pfadlänge wird Huffman-Baum genannt

Konstruieren Sie einen Wald aus n Binärbäumen mit nur Wurzelknoten. Jeder Binärbaum hat nur einen Wurzelknoten mit einer Gewichtung.

Wiederholen Sie die folgenden Schritte, bis in F nur noch ein Baum übrig ist

Codierung

Wenn der linke Teilbaum nicht leer ist, sind die Werte aller Knoten im linken Teilbaum kleiner als der Wert des Wurzelknotens

Sein rechter Teilbaum ist nicht leer, dann sind die Werte aller Knoten im rechten Teilbaum größer als der Wert des Wurzelknotens

Seine linken und rechten Teilbäume sind ebenfalls binäre Suchbäume.

suchen

einfügen

löschen

Leistungsanalyse des binären Suchbaums

Seine linken und rechten Teilbäume sind beide AVL-Bäume

Der absolute Wert der Differenz zwischen den Höhen des linken Teilbaums und des rechten Teilbaums (als Ausgleichsfaktor bezeichnet) überschreitet nicht 1 (-1, 0, 1).

Wenn ein Baum sehr ausgeglichen ist, handelt es sich um einen AVL-Baum. Wenn es n Knoten hat, kann seine Höhe bei 0 (lgn) gehalten werden und die durchschnittliche Suchkomplexität beträgt O (lgn).

linke Unirotation

rechte Unirotation

Doppelte Drehung nach links und rechts

Doppelte Rechts- und Linksdrehung

Wenn es sich um einen leeren Baum handelt, ist er nach dem Einfügen der Wurzelknoten und gibt direkt nach dem Einfügen „true“ zurück.

Wenn der Baum nicht leer ist, suchen Sie nach der Einfügeposition. Wenn der Schlüssel während des Suchvorgangs gefunden wird, schlägt die Einfügung fehl und gibt direkt false zurück.

Knoten einfügen

Aktualisieren Sie den Ausgleichsfaktor und passen Sie den Baum an

Der gelöschte Knoten hat nur das linke untergeordnete Element

Der gelöschte Knoten hat nur das richtige Kind

Der gelöschte Knoten hat sowohl linke als auch rechte untergeordnete Knoten.

Die Wurzel des höheren Teilbaums des Elternteils ist q

Der Rot-Schwarz-Baum ist ein binärer Suchbaum. Er fügt jedem Knoten ein Speicherbit hinzu, um die Farbe des Knotens darzustellen, und stellt so sicher, dass der längste Pfad nicht das Doppelte des kürzesten Pfads überschreitet, was ungefähr ausgeglichen ist.

Jeder Knoten ist entweder rot oder schwarz

Der Wurzelknoten des Baums ist schwarz

Wenn ein Knoten rot ist, sind seine beiden untergeordneten Knoten schwarz (es gibt keine zwei aufeinanderfolgenden roten Knoten).

Für jeden Knoten enthalten die einfachen Pfade von diesem Knoten zu allen seinen untergeordneten Blattknoten die gleiche Anzahl schwarzer Knoten (die Anzahl schwarzer Knoten ist auf jedem Pfad gleich).

Jeder Blattknoten ist schwarz (Blattknoten beziehen sich hier auf leere Knoten)

Wenn der Baum leer ist, muss der neue Knoten nach dem Einfügen in Schwarz geändert werden.

Der übergeordnete Knoten des eingefügten Knotens ist schwarz und verletzt keine Eigenschaften. Er kann direkt eingefügt werden.

Situation drei

Situation vier

Situation fünf

C STL-Bibliothek – Map/Set Multimap Multiset

Java-Bibliothek

Linux Kernel

einige andere Bibliotheken