Umgang mit doppelten Schlüsseln innerhalb eines AVL-Baums

Question

Ich möchte mein machen avl-tree unterstützen doppelte Schlüssel, es gibt jedoch ein Problem mit dem Standardverhalten von binary search tree mit Duplikaten, dass die Rotation dazu führen könnte, dass Knoten mit gleichem Schlüssel links und rechts vom übergeordneten Element liegen.

Wenn zum Beispiel drei Knoten alle mit Schlüssel A hinzugefügt werden, führt der Baum eine Drehung durch, die etwa so aussieht:

   A
  /  \ 
 A    A

Daher wird es ein Problem sein, alle Einträge mit diesem Schlüssel zu erhalten ... und die Suche in beide Richtungen ist nicht gut.

Die Lösung, an die ich gedacht habe, besteht darin Mit Key gibt dieses Array zurück.

Gibt es andere Methoden zum Umgang mit Duplikaten?

Das Einfügeelement benötigt einen Schlüssel und einen Wert.Daher muss ich die Werte speichern, um sie von findAll mit einer bestimmten Schlüsselmethode zurückzugeben.

Answer 1

Ein weiterer allgemeiner Ansatz ist intern auf den Wert Teil des Schlüssels, so dass Sie nicht wirklich doppelte Schlüssel haben mehr. Sie beide müssen die Schlüssel und den Wert ohnehin um einen Eintrag aus einem Baum zu löschen, die Duplikate erlaubt.

für einen Schlüssel suchen, ohne den Wert zu kennen, würden Sie dann tun so etwas wie (Pseudo-Code):

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

Lassen Sie jeden Knoten eine Anzahl enthalten:Das Hinzufügen von Duplikaten erhöht die Anzahl, das Entfernen verringert die Anzahl, es sei denn, sie ist 1. In diesem Fall wird der gesamte Knoten entfernt.