[PYTHON] Ein 2-minütiger Suchbaum ist ein Verwandter der Hash-Kette !?
Guten Abend (* ´ω ｀)
Als Amateur, Was ist auf den ersten Blick "Baum"? .. (Entschuldigung für alle Experten m (_ _) m)
Die Baumstruktur scheint eine Datenstruktur zu sein, die die hierarchische Beziehung zwischen Daten ausdrückt.
Persönlich sah es aus wie eine Erweiterung der vorherigen Hash-Kette. Ich war aufgeregt, was für ein Denken es war Vorerst werde ich damit spielen (lacht)
test.py
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
Es mag so sein wie es ist, aber ich habe den Inhalt des Knotens geschrieben.
Auf diese Weise können mehr Knoten im linken und rechten Bereich innerhalb des Knotens gespeichert werden.
Ich habe versucht, es etwas holziger zu machen.
Es ist ähnlich wie die Hash-Kette, es ist interessant.
Ich bin sicher, es gibt Regeln zum Speichern von Daten. Ja, es gab Regeln. ..
Ein gegabelter Baum ist ein gegabelter Baum, in dem ** alle Knoten ** die folgenden Bedingungen erfüllen. Der Knotenschlüssel des linken Teilbaums ist ** kleiner ** als dieser Knotenschlüssel Der Knotenschlüssel des rechten Teilbaums ist ** größer ** als dieser Knotenschlüssel
Der linke Teilbaum ist das linke Kind, der rechte Teilbaum ist der rechte Noko, Kind !? (Lacht)
Von wem man rechts oder links urteilt, scheint es kein Problem zu geben, wenn man am Wendepunkt denkt.
Wie ist das? Egal wo Sie sind, die oben genannten Bedingungen sind erfüllt! ??
Aber warum hast du eine solche Regel? (11) Der Grund ist die zuvor angegebene Schlüsseleinstellungsregel. Versuchen Sie, key = 5 zu finden.
- Der Startpunkt beginnt bei 11, der als Root bezeichnet wird. Der Schlüssel, den ich suchte, war 5. Auf der linken Seite wurden Schlüssel gespeichert, die kleiner als der aktuelle Standort (= 11) sind.
- Öffnen wir den linken Zeiger. Da war in diesem Knoten, Schlüssel = 5 !!
Es ist ein glückliches Ziel.
Suchen wir nun nach einem anderen Schlüssel = 9.
Der Übergang ist rot gefärbt.
1.Starten Sie von 11 (root), Schlüssel (= 9) <11, also gehen Sie nach links !!
2. Taste (= 9) ist größer als 5, also gehe nach rechts !!
3. Taste (= 9) ist größer als 7, also gehe nach rechts !!
Es gab Schlüssel = 9 !!, Go ---- Le !!
Ich sehe, indem ich den nächsten Zeiger in der Hash-Kette entwerfe Noch prägnanter realisiert es logisch komplexe Datenstrukturen. groß!!
test.py
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self,key):
#von root starten!!
p = self.root
while True:
#return None, wenn in der Struktur nichts mit root verbunden ist
if p.key is None:
return None
#Wenn der Schlüssel zutreffend ist, p.Rückgabewert
if p.key == key:
return p.value
#Zunächst p oben erwähnt.key ==Da der Schlüssel übergeben wird,
#Beschreiben Sie den Übergang nach rechts oder links unten
elif p.key < key:
p = p.right
else:
p = p.left
Beschreiben Sie vorerst den Basisknoten und Beschreibung zur Suche hinzugefügt. Zu diesem Zeitpunkt hat Tree noch nichts getan. Jetzt gibt es nur noch eine leere Wurzel. Fügen wir hier einen Knoten hinzu.
Lassen Sie uns zunächst aus root erstellen.
test.py
def add(self,key,value):
#Zu Beginn wurde es in Node wie folgt definiert.
#class BinarySearchTree:
# def __init__(self):
# self.root = None
if self.root is None:
#Die entsprechenden Daten können auch in root gespeichert werden.
#left ,Ich werde von nun an gleich machen, also werde ich es vorerst als Keine belassen
self.root = Node(key,value,None,None)
else:
#Wenn der Knoten bereits in root eingefügt ist
#Sie müssen von root ausgehen und weitere Knoten hinzufügen.
#Wie zu erwarten, fügen Sie hinzu_Wir werden den Knoten rekursiv konfigurieren.
BinarySearchTree.add_node(self.root,key,value)
Sobald Sie die Wurzel erstellt haben Basierend auf root werden wir Knoten gemäß der Definition der obigen Dichotomie hinzufügen. Das Folgende ist eine Beschreibung von add_node, die rekursiv verzweigt.
test.py
def add_node(node,key,value):
#Fehler, wenn doppelter Schlüssel gefunden wurde
if key == node.key:
return print("fail to add")
#Neuer Knoten.key <Vorhandener Knoten.Wenn Schlüssel, links speichern!
elif key < node.key:
#Wenn der linke Zeiger leer ist, fügen Sie ihn als neuen Knoten hinzu
if node.left is None:
node.left = Node(key,value,None,None)
#Wenn bereits ein Geschäft übrig ist, verarbeiten Sie es rekursiv
else:
BinarySearchTree.add_node(node.left,key,value)
else:
#Wenn der Zeiger rechts leer ist, fügen Sie ihn als neuen Knoten hinzu
if node.right is None:
node.right = Node(key,value,None,None)
#Wenn rechts bereits ein Geschäft hat, verarbeiten Sie es rekursiv
else:
BinarySearchTree.add_node(node.right,key,value)
return True
Beginnen Sie jedes Mal, wenn Sie add ausführen, mit root, suchen Sie nach dem entsprechenden Zeiger und fügen Sie Node hinzu. Es ist, als ob die von der Wurzel ernährte Pflanze ihrer eigenen Definition von Wachstum folgt. Es ist nur ein "Baum", der nach und nach wächst. Ich möchte eine pulsierende Kreatur sehen.
Machen Sie ein solches Bild, während Sie den Textcode lesen und schreiben Grinst du dich selbst an? !! (* ´з`) Es bedeutet, dass Sie Ihr eigenes Wachstum spüren (lacht).
Als nächstes wird entfernt. Wie bereits erwähnt, beginnt Add mit root und Ich ergreife Maßnahmen, um das relevante Teil zu finden und jederzeit Knoten hinzuzufügen. Daher ist entfernen das gleiche, Gehen Sie zu root, um den Knoten zu finden, den Sie entfernen möchten.
Es ist ein bisschen kompliziert. Es kann zu schwierig sein, darüber nachzudenken, In diesem Fall tauchen Sie bitte ein. m (_ _) m
Lass uns gehen. Wie oben erwähnt, beginnt alles mit root. Es ist vorbei, wenn Sie das haben, was Sie als Wurzel wollen Wenn root überhaupt keinen Schlüssel hat, ist es vorbei, oder? ??
test.py
def remove(self,key):
#Beginnen Sie von der Wurzel mit dem Zeiger als p.
p = self.root
#Ob von rechts oder von links, es ist später eine nützliche Flagge.
direction_is_left = None
while True:
#Wenn root oder Node keinen Schlüssel hat, geben Sie False zurück und beenden Sie das Programm
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
#Wenn der im Knoten enthaltene Schlüssel mit dem Eingabeschlüssel übereinstimmt, brechen Sie währenddessen aus
if p.key == key:
print("find out the Node")
break
#Wenn der Schlüssel nicht dem Knoten entspricht, wählen Sie die Fahrtrichtung nach rechts oder links gemäß der obigen Regel.
#Geben Sie zu diesem Zeitpunkt der Flagge in Fahrtrichtung einen Wert.(direction_is_left)
else:
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
Wie in der folgenden Abbildung gezeigt, hat der zu löschende Knoten keine Kinder und wenn er nur ein Kind hat,
Wie lösche ich es? ??
In diesem Fall scheint es keine Möglichkeit zu geben, etwas zu tun, es sei denn, Sie berühren die übergeordnete linke oder rechte Ebene eine Ebene darüber.
Fügen Sie daher der obigen Beschreibung ein "übergeordnetes Element" hinzu, um das Auffinden des gelöschten Knotens und das Identifizieren des übergeordneten Knotens zu erleichtern.
test.py
def remove(self,key):
p = self.root
parent = None #Himmel(Kara)Bereite die Eltern vor
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
#Es spielt keine Rolle, ob Sie nach rechts oder links gehen, also setzen Sie den Wert von p auf p.left or p.richtig und
#Weisen Sie p vor dem Aktualisieren als übergeordnetes Element zu.
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
Ich werde es wieder posten!
Wenn Sie kein oder nur ein Kind haben, konzentrieren Sie sich auf den linken oder rechten Teil.
test.py
#Es gibt kein Recht, ja, es bezieht sich auf den Fall des linken Teils
if p.right is None:
#Aus der Sicht der Eltern kam p von links, richtig?
if direction_is_left:
#Im Fall der obigen Abbildung links wird links links vom Knoten 1 keine gespeichert.
#In der obigen Abbildung ist im Fall von rechts Knoten 1 für links von Knoten 4 möglich
parent.left = p.left
else:
#??↓ Was ist das?? ('Д').. Es tut mir leid, wie unten gezeigt.
parent.right = p.left
Aber es gibt Zeiten, in denen Sie beispielsweise root entfernen möchten, oder?
In der obigen Beschreibung befindet sich also kein Knoten auf der rechten Seite
Sie müssen den Knoten links ersetzen, damit er root wird, oder?
Wenn Sie also root entfernen möchten, fügen Sie es ebenfalls hinzu.
test.py
if p.right is None:
if p == self.root: #Ich möchte root löschen??
self.root = p.left #Lassen Sie uns nun den linken Knoten wurzeln.
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
Wenn dies ohne das Recht der Fall ist, Es ist das gleiche, auch wenn es kein Links gibt, oder? Deshalb werde ich die Version auch ohne die linke auflisten.
test.py
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
Das ist also der schwierigste Teil,
Was ist, wenn Sie einen Knoten mit zwei untergeordneten Knoten löschen möchten?
Sie möchten 5 wie oben gezeigt entfernen.
Sicher gab es eine solche Regel, oder?
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ Ein gegabelter Baum ist ein gegabelter Baum, in dem ** alle Knoten ** die folgenden Bedingungen erfüllen. Der Knotenschlüssel des linken Teilbaums ist ** kleiner ** als dieser Knotenschlüssel Der Knotenschlüssel des rechten Teilbaums ist ** größer ** als dieser Knotenschlüssel ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Mit anderen Worten, extrahieren Sie den Maximalwert aus dem Kind im linken Teil. Wenn Sie es ersetzen können, können Sie sich mit dem Kind auf der rechten Seite verbinden, richtig?
Das ist richtig, wenn Sie zwei Kinder haben Finden Sie mit der obigen Idee den Maximalwert, Überschreiben Sie den Knoten, den Sie löschen möchten. Bei der Nachbearbeitung wird der maximal gefundene Wert gelöscht. Lassen Sie es uns wie gezeigt in den Code einfügen, 4 ist das Maximum.
test.py
else:
#Sie können die Informationen in 5 später verwenden.
#Lassen wir es als Eltern
parent = p
#Lassen Sie den Knoten links vom Elternteil übrig
left = p.left
#Richtig, weil die Fahrtrichtung links ist
direction_is_left = True
#Wie in der obigen Abbildung gezeigt, sind 4 Knoten, die 5 links entsprechen,
#Dies ist der Maximalwert unter den Kindern im linken Teil.
#Schreiben wir die Informationen von Knoten 5 in Knoten 4 um.
p.key = left.key
p.value = left.value
#Entfernen wir Knoten 4.
#Insbesondere Eltern.von links nach links.Ersetzen Sie links durch 1!!Wie es ist(Lol)
if direction_is_left:
parent.left = left.left
#↓ Was???Dies??
else:
parent.right = left.left
Schließlich gab es eine mysteriöse Beschreibung.
Ein Update, das friedlich geschlossen wurde,
Was ist, wenn die Baumkonfiguration so ist?
Beim Verzweigen von links nach rechts
Der Wert von rechts steigt stetig an.
Wir müssen also einen Weg hinzufügen, um den Maximalwert zu finden.
test.py
else:
parent = p
left = p.left
direction_is_left = True
#Richtige Suche hinzugefügt!!
#left.Aktualisiere links, bis rechts zu Keine wird
while left.right is None:
#Wenn Sie den Knoten rechts finden, aktualisieren Sie den übergeordneten und den linken Knoten
parent = left
left = left.right
#Erklären Sie, dass Sie mit False von rechts gekommen sind
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
#Wenn Sie den von rechts gefundenen Knoten als Maximalwert festlegen möchten,
#left.dem Elternteil überlassen.Nach rechts verbinden.
else:
parent.right = left.left
Aus diesem Grund ist das Entfernen zu einem großen Volumen geworden.
test.py
def remove(self,key):
p = self.root
parent = None
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
else:
parent = p
left = p.left
direction_is_left = True
while left.right is None:
parent = left
left = left.right
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
else:
parent.right = left.left
return True
Wenn Sie sich vorstellen können, was Sie mit entfernen wollen Ich denke du kannst es irgendwie lesen. Vielen Dank für Ihre harte Arbeit (´ ー ｀) y- ~~
Recommended Posts