Was ist ein AA-Baum in C/C++?

In der Informatik wird ein AA-Baum als eine ausgewogene Baumimplementierung zum effizienten Speichern und Abrufen geordneter Daten definiert. AA-Bäume gelten als Variante von Rot-Schwarz-Bäumen, einem binären Suchbaum, der das effiziente Hinzufügen und Löschen von Einträgen unterstützt. Im Gegensatz zum rot-schwarzen Baum kann der rote Knoten im AA-Baum nur als rechter untergeordneter Knoten und nicht als linker untergeordneter Knoten hinzugefügt werden. Das Ergebnis dieser Operation ist die Simulation eines 2-3-Baums anstelle eines 2-3-4-Baums, wodurch Wartungsvorgänge vereinfacht werden. Der Wartungsalgorithmus für rot-schwarze Bäume muss sieben verschiedene Formen annehmen oder berücksichtigen, um den Baum korrekt auszugleichen.

Im Gegensatz zu rot-schwarzen Bäumen müssen AA-Bäume nur zwei Formen annehmen oder berücksichtigen, da nur das rechte Glied rot sein kann.

Ausgeglichene Rotation

Der Rot-Schwarz-Baum erfordert ein ausgleichendes Metadatenbit (Farbe) pro Knoten, während der AA-Baum O(log(log(N))) Metadatenbits pro Knoten in der Form erfordert einer ganzzahligen „Ebene“. Für AA-Bäume gilt die folgende Invariante:

• Die Ebene jedes Blattknotens wird als 1 betrachtet.

• Die Ebene jedes linken untergeordneten Knotens ist 1 niedriger als die seines übergeordneten Knotens.

• Die Ebene jedes rechten untergeordneten Knotens ist gleich oder um 1 niedriger als die seines übergeordneten Knotens.

• Die Ebene jedes rechten Enkelknotens ist streng kleiner als die seines Großelternknotens.

• Jeder Knoten mit Level größer als 1 hat zwei untergeordnete Knoten.

AA-Bäume neu auszubalancieren ist viel einfacher als rot-schwarze Bäume neu auszubalancieren.

In einem AA-Baum sind nur zwei verschiedene Operationen erforderlich, um das Gleichgewicht wiederherzustellen: „Skew“ und „Split“. Skew wird als Rechtsdrehung behandelt und ersetzt einen Teilbaum, der aus einem linken horizontalen Link besteht, durch einen rechten horizontalen Link. Im Fall von Split handelt es sich um eine Linksdrehung und eine Erhöhung der Ebene, wobei ein Teilbaum, der zwei weniger aufeinanderfolgende rechte horizontale Links enthält, durch zwei oder mehr aufeinanderfolgende rechte horizontale Links ersetzt wird. Die beiden Operationen „Skew“ und „Split“ werden im Folgenden erläutert. Die Definition von

Funktionsversatz lautet wie folgt:

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(left(t)) then
return t
else if level(left(t)) == level(t) then
   Exchange the pointers of horizontal left links.
   l = left(t)
left(t) := right(l)
right(l) := t
return l
else
return t
end if
end function

Funktionsaufteilung ist

wird übersetzt als:

Funktionsteilung. ist

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(right(t)) or nil(right(right(t))) then
return t
else if level(t) == level(right(right(t))) then
We have two horizontal right links. The middle node is taken, elevate it, and return it.
      r = right(t)
right(t) := left(r)
left(r) := t
level(r) := level(r) + 1
return r
else
return t
end if
end function

Split -

Das obige ist der detaillierte Inhalt vonWas ist ein AA-Baum in C/C++?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!