Dieser Artikel bietet Ihnen eine detaillierte Einführung (Codebeispiel) über binäre Suchbäume in Python. Ich hoffe, dass er für Freunde hilfreich ist.
1. Binärer Suchbaum
**Binärer Suchbaum (BST-Binärsuche). Baum)** ist ein spezieller Binärbaum, der größer als der Wert des linken untergeordneten Knotens und kleiner oder gleich dem Wert des rechten untergeordneten Knotens ist. Search Tree) kann einen sortierten Satz von Elementen erhalten, und der Zeitaufwand für das Einfügen und Löschen ist ebenfalls relativ vernünftig, aber ein Nachteil besteht darin, dass der Speicheraufwand etwas groß ist.
Eigenschaften binärer Suchbäume
1. Für jeden Knoten x ist der Schlüssel in seinem linken Teilbaum nicht größer als x.key und der Schlüssel in seinem rechten Teilbaum ist nicht kleiner als x .Schlüssel.
2. Verschiedene binäre Suchbäume können denselben Wertesatz darstellen.
3. Die Grundoperationen eines binären Suchbaums sind proportional zur Höhe des Baums. Wenn es sich also um einen vollständigen Binärbaum handelt, beträgt die schlechteste Laufzeit Θ(lgn), wenn es sich jedoch um einen linearen Baum handelt, der durch verbunden ist n Knoten, dann Die schlechteste Laufzeit ist Θ(n).
4. Der Wurzelknoten ist der einzige Knoten, dessen übergeordneter Zeiger auf den NIL-Knoten zeigt.
5. Jeder Knoten enthält mindestens vier Attribute: Schlüssel, links, rechts und übergeordneter Knoten. Beim Erstellen eines binären Suchbaums muss ein Vergleichsalgorithmus für den Schlüssel vorhanden sein.
2. Implementierung des binären Suchbaums
Baums:
class TreeNode:
def __init__(self,key,val,left=None,right=None,parent=None):
self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0Da wir nun die BinarySearchTree-Shell und TreeNode haben, ist es an der Zeit, die Put-Methode zu schreiben, die es uns ermöglicht, einen binären Suchbaum zu erstellen. Die Put-Methode ist eine Methode der BinarySearchTree-Klasse. Diese Methode prüft, ob der Baum bereits eine Wurzel hat. Wenn kein Root vorhanden ist, erstellt put einen neuen TreeNode und macht ihn zum Root des Baums. Wenn der Wurzelknoten bereits vorhanden ist, ruft put die private rekursive Hilfsfunktion _put auf, um den Baum gemäß dem folgenden Algorithmus zu durchsuchen:
Durchsuchen Sie ausgehend von der Wurzel des Baums die Binärdatei Baum, der den neuen Schlüssel mit den aktuellen Knotenschlüsseln zum Vergleich abgleicht. Wenn der neue Schlüssel kleiner als der aktuelle Knoten ist, wird der linke Teilbaum durchsucht. Wenn der neue Schlüssel größer als der aktuelle Knoten ist, wird der rechte Teilbaum durchsucht.
Wenn es kein linkes (oder rechtes) Kind gibt, nach dem gesucht werden muss, finden wir die Position im Baum, an der der neue Knoten erstellt werden soll.
Um einen Knoten zum Baum hinzuzufügen, erstellen Sie ein neues TreeNode-Objekt und fügen Sie das Objekt in den im vorherigen Schritt ermittelten Knoten ein.
Beim Einfügen wird er immer als Blattknoten in den Baum eingefügt.
Wenn eine Sequenz zum Aufbau eines binären Suchbaums angegeben wird, ist der binäre Suchbaum eindeutig Sequenzen werden verwendet. Wörter werden verwendet, um mögliche Binärbäume (in beliebiger Reihenfolge angeordnet) zu konstruieren, die im Allgemeinen nicht eindeutig sind.
def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root = TreeNode(key,val)
self.size = self.size + 1
def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)Das Obige zeigt den Python-Code zum Einfügen eines neuen Knotens in den Baum. Die _put-Funktion wird rekursiv gemäß den oben genannten Schritten geschrieben. Beachten Sie, dass beim Einfügen eines neuen untergeordneten Knotens in den Baum currentNode als übergeordneter Knoten an den neuen Baumknoten übergeben wird.
Ein wichtiges Problem bei unserer Implementierung des Einfügens besteht darin, dass doppelte Schlüssel nicht korrekt verarbeitet werden können. Wenn unser Baum implementiert ist, erstellt ein doppelter Schlüssel einen neuen Knoten mit demselben Schlüsselwert im rechten Teilbaum des Knotens mit dem ursprünglichen Schlüssel. Dies hat zur Folge, dass der Knoten mit dem neuen Schlüssel bei der Suche nie gefunden wird. Eine bessere Möglichkeit, das Einfügen eines doppelten Schlüssels zu handhaben, besteht darin, den alten Wert durch den Wert zu ersetzen, der dem neuen Schlüssel zugeordnet ist.
Sobald der Baum erstellt ist, besteht die nächste Aufgabe darin, den Abruf des Werts für einen bestimmten Schlüssel zu implementieren. Die get-Methode ist einfacher als die put-Methode, da sie den Baum einfach rekursiv durchsucht, bis sie einen nicht übereinstimmenden Blattknoten erreicht oder einen passenden Schlüssel findet. Wenn ein passender Schlüssel gefunden wird, wird der in der Nutzlast des Knotens gespeicherte Wert zurückgegeben.
Wenn der binäre Suchbaum nicht leer ist:
Vergleichen Sie zuerst den angegebenen Wert mit dem Schlüsselwort des Wurzelknotens. Wenn sie gleich sind, ist die Suche erfolgreich
Wenn es kleiner als der Schlüsselwortwert des Wurzelknotens ist, durchsuchen Sie rekursiv den linken Teilbaum
Wenn es größer als der Schlüsselwortwert von ist Suchen Sie im Wurzelknoten rekursiv nach dem rechten Teilbaum. Teilbaum
Wenn der Teilbaum leer ist, ist die Suche erfolglos
def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
return res.payload
else:
return None
else:
return None
def _get(self,key,currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key,currentNode.leftChild)
else:
return self._get(key,currentNode.rightChild)
def __getitem__(self,key):
return self.get(key)Die erste Aufgabe besteht darin, den Baum zu durchsuchen, um den zu löschenden Knoten zu finden. Wenn der Baum mehrere Knoten hat, suchen wir mit der Methode _get, um den TreeNode zu finden, der gelöscht werden muss. Wenn der Baum nur einen Knoten hat, bedeutet das, dass wir die Wurzel des Baums löschen, aber wir müssen trotzdem prüfen, ob der Schlüssel der Wurzel mit dem Schlüssel übereinstimmt, den wir löschen möchten. In beiden Fällen löst der del-Operator einen Fehler aus, wenn der Schlüssel nicht gefunden wird.
def delete(self,key):
if self.size > 1:
nodeToRemove = self._get(key,self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self.size-1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError('Error, key not in tree')
def __delitem__(self,key):
self.delete(key)Sobald wir den Knoten für den Schlüssel gefunden haben, den wir löschen möchten, müssen wir drei Situationen berücksichtigen:
Der zu löschende Knoten hat keine untergeordneten Elemente.
Der zu löschende Knoten hat nur einen untergeordneten Knoten.
Der zu löschende Knoten hat zwei untergeordnete Knoten.
第一种情况：
如果当前节点没有子节点，我们需要做的是删除节点并删除对父节点中该节点的引用。
第二种情况：
如果一个节点只有一个孩子，那么我们可以简单地促进孩子取代其父。此案例的代码展示在下一个列表中。当你看这个代码，你会看到有六种情况要考虑。由于这些情况相对于左孩子或右孩子对称，我们将仅讨论当前节点具有左孩子的情况。决策如下：
如果当前节点是左子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的左子节点引用以指向当前节点的左子节点。
如果当前节点是右子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的右子节点引用以指向当前节点的左子节点。
如果当前节点没有父级，则它是根。在这种情况下，我们将通过在根上调用replaceNodeData 方法来替换 key，payload，leftChild 和 rightChild 数据。
第三种情况：
最难处理的情况。 如果一个节点有两个孩子，那么我们不太可能简单地提升其中一个节点来占据节点的位置。 然而，我们可以在树中搜索可用于替换被调度删除的节点的节点。 我们需要的是一个节点，它将保留现有的左和右子树的二叉搜索树关系。 执行此操作的节点是树中具有次最大键的节点。 我们将这个节点称为后继节点，我们将看一种方法来很快找到后继节点。 继承节点保证没有多于一个孩子，所以我们知道使用已经实现的两种情况删除它。 一旦删除了后继，我们只需将它放在树中，代替要删除的节点。
找到后继的代码如下所示，是 TreeNode 类的一个方法。此代码利用二叉搜索树的相同属性，采用中序遍历从最小到最大打印树中的节点。在寻找接班人时，有三种情况需要考虑：
如果节点有右子节点，则后继节点是右子树中的最小的键。
如果节点没有右子节点并且是父节点的左子节点，则父节点是后继节点。
如果节点是其父节点的右子节点，并且它本身没有右子节点，则此节点的后继节点是其父节点的后继节点，不包括此节点。
def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ
def findMin(self):
current = self
while current.hasLeftChild():
current = current.leftChild
return current
def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent二叉搜索树的深度越小，那么搜索所需要的运算时间越小。一个深度为log(n)的二叉搜索树，搜索算法的时间复杂度也是log(n)。然而，我们在二叉搜索树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8，7，6，5，4，3，2，1的顺序插入节点，那么就是一个深度为n的二叉树。那么，搜索算法的时间复杂度为n。
在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。
如何减少树的深度呢？
一种想法是先填满一层，再去填充下一层，这样就是一个完全二叉树(complete binary tree)。这样的二叉树实现插入算法会比较复杂。另一种比较容易实现的树状数据结构——AVL树，其搜索算法复杂度为log(n)。
在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树随时都保持平衡。这种树被称为AVL树，命名源于其发明者：G.M. Adelson-Velskii 和 E.M. Landis。
Die AVL-Baumimplementierung des abstrakten Datentyps „Map“ ähnelt einem regulären binären Suchbaum. Der einzige Unterschied besteht darin, wie der Baum ausgeführt wird. Um unseren AVL-Baum zu implementieren, müssen wir den Ausgleichsfaktor für jeden Knoten im Baum im Auge behalten. Wir tun dies, indem wir uns die Höhen der linken und rechten Teilbäume jedes Knotens ansehen. Formaler definieren wir den Gleichgewichtsfaktor eines Knotens als die Differenz zwischen der Höhe des linken Teilbaums und der Höhe des rechten Teilbaums.
balanceFac tor=height(leftSub Tree)−height(right SubTree)Unter Verwendung der oben angegebenen Definition des Balancefaktors sagen wir, dass ein Teilbaum linkslastig ist, wenn der Balancefaktor größer als Null ist . Wenn der Balancefaktor kleiner als Null ist, ist der Teilbaum rechtslastig. Wenn der Ausgleichsfaktor Null ist, ist der Baum perfekt ausgeglichen. Um einen AVL-Baum zu implementieren und die Vorteile eines ausgeglichenen Baums zu nutzen, definieren wir den Baumausgleich, wenn der Ausgleichsfaktor -1,0 oder 1 ist. Sobald der Gleichgewichtsfaktor eines Knotens im Baum außerhalb dieses Bereichs liegt, benötigen wir eine Prozedur, um den Baum wieder ins Gleichgewicht zu bringen.
Nh=1+Nh−1+Nh−2 Diese Formel ist der Fibonacci-Folge sehr ähnlich. Mit dieser Formel können wir die Höhe eines AVL-Baums aus der Anzahl der Knoten im Baum ableiten. Je größer die Zahlen der Fibonacci-Folge werden, desto näher kommt Fi/Fi−1 dem Goldenen Schnitt Φ
Zu jedem Zeitpunkt ist die Höhe unseres AVL-Baums gleich einer Konstante, die der Logarithmus von ist Anzahl der Knoten im Baum (1,44) mal. Das sind gute Nachrichten für die Suche in unserem AVL-Baum, da es die Suche auf O(logN) beschränkt.
Um eine korrekte Rechtsdrehung durchzuführen, müssen wir Folgendes tun:
Hinweis: Da die neue Wurzel der linke Knoten der alten Wurzel ist, muss der linke Knoten der alten Wurzel nach der Bewegung leer sein. Zu diesem Zeitpunkt können Sie den linken Knoten direkt zum verschobenen alten Stamm hinzufügen. 
Um eine Linksdrehung durchzuführen, müssen wir in ähnlicher Weise Folgendes tun:
Machen Sie den rechten Knoten (B) zur Wurzel des Teilbaums.
Verschieben Sie den alten Wurzelknoten (A) auf den linken Knoten des neuen Wurzelknotens.
Wenn die neue Wurzel (B) ursprünglich einen linken Knoten hat, dann soll der linke Knoten des ursprünglichen B zum rechten Knoten des neuen linken Wurzelknotens (A) werden.
Wenn der untergeordnete Knoten wie in der Abbildung gezeigt 4 statt 2 ist, versuchen Sie es mit einer einzelnen Rotation. Sie werden feststellen, dass das Problem nicht gelöst werden kann.
Um dieses Problem zu lösen, müssen wir die folgenden Regeln verwenden:
Wenn der Teilbaum nach links gedreht werden muss, um ihn auszubalancieren, überprüfen Sie zunächst den Balancefaktor des rechten Knotens. Wenn der rechte Knoten linkslastig ist, wird der rechte Knoten nach rechts gedreht und dann wird der ursprüngliche Knoten nach links gedreht.
Wenn der Teilbaum nach rechts gedreht werden muss, um ihn auszubalancieren, prüfen Sie zunächst den Balancefaktor des linken Knotens. Wenn der linke Knoten rechtslastig ist, wird der linke Knoten nach links gedreht und dann wird der ursprüngliche Knoten nach rechts gedreht.
Die Lösung ist derzeit die Doppelrotation. 
Doppelte Rotation besteht eigentlich aus zwei einzelnen Rotationen: Der Teilbaum mit Wurzelknoten 4 führt zuerst eine einzelne Drehung nach links aus, und dann führt der Teilbaum mit Wurzelknoten 5 eine einzelne Drehung nach rechts aus. Dadurch werden die ACL-Eigenschaften des Baums wiederhergestellt.
Für AVL-Bäume kann nachgewiesen werden, dass beim Hinzufügen eines neuen Knotens die Eigenschaften des AVL-Baums immer durch eine Rotation wiederhergestellt werden können.
Wenn wir einen neuen Knoten einfügen, wohin dreht er sich? Sollten wir eine Einzelrotation oder eine Doppelrotation verwenden? 
Wir befolgen die folgenden grundlegenden Schritte:
Fügen Sie Knoten gemäß der binären Suchbaummethode und der neuen hinzu Der sogenannte Knoten ist ein Blattknoten.
Beginnen Sie beim neu hinzugefügten Knoten und verfolgen Sie den Weg zurück zum ersten unausgeglichenen Knoten (5).
(Wenn Sie bis zum Wurzelknoten zurückverfolgen und es keinen unausgeglichenen Knoten gibt, bedeutet dies, dass der Baum bereits der AVL-Eigenschaft entspricht.)
Suchen Sie die gebrochene Kante (5 ->3) und Bestimmen Sie die Richtung der gebrochenen Saite (linke Seite von 5)
Nehmen Sie das untere Ende der gebrochenen Saite (3) als Wurzelknoten und bestimmen Sie welche der beiden Teilbäume hat die größere Tiefe (linker Teilbaum oder rechter Teilbaum).
(Die Tiefe der beiden Teilbäume kann nicht gleich sein und der Teilbaum mit einer größeren Tiefe enthält neue Knoten.)
Wenn die Richtungen in den Schritten 2 und 3 gleich sind ( beide links oder beide rechts) erfordert eine einzelne Drehung des Teilbaums mit dem unausgeglichenen Knoten als Wurzelknoten.
Andernfalls drehen Sie den Teilbaum, der am unausgeglichenen Knoten wurzelt, doppelt.
Der Rot-Schwarz-Baum ist ein häufig verwendeter ausgewogener binärer Suchbaum. Er ist komplex, aber seine Funktionsweise liefert gute Optimierungsergebnisse. Die Laufzeit im schlechten Fall, d. h. die Komplexität der Operation, verschlechtert sich nicht und ist in der Praxis effizient: Es kann eine einzelne Suche, Einfügung und Löschung in O(logn)-Zeit durchgeführt werden, wobei n die Anzahl der Elemente im Baum ist Nummer.
Der Rot-Schwarz-Baum ist ein sehr interessanter, ausgewogener Suchbaum. Seine statistische Leistung ist besser als die des ausgeglichenen Binärbaums (AVL-Baum), daher wird an vielen Stellen der Rot-Schwarz-Baum verwendet. In C++ STL wenden viele Teile (derzeit einschließlich set, multiset, map, multimap) Varianten des Rot-Schwarz-Baums an (der Rot-Schwarz-Baum in SGI STL weist einige Änderungen auf, Diese Änderungen sorgen für eine bessere Leistung sowie Unterstützung für Mengenoperationen.
Die Hauptregeln für rot-schwarze Bäume:
Die Hauptregeln für rot-schwarze Bäume lauten wie folgt:
Knoten sind rot oder schwarz.
Die Wurzel ist schwarz.
Alle Blätter sind schwarz (Blätter sind NIL-Knoten).
Jeder rote Knoten muss zwei schwarze untergeordnete Knoten haben. (Es kann nicht auf allen Pfaden von jedem Blatt zur Wurzel zwei aufeinanderfolgende rote Knoten geben.)
Alle einfachen Pfade von jedem Knoten zu jedem seiner Blätter enthalten die gleiche Anzahl schwarzer Knoten.
Die in den Rot-Schwarz-Baum eingefügten Knoten sind alle rot. Dies ist kein Zufall, da das Einfügen eines roten Knotens weniger wahrscheinlich gegen die Rot-Schwarz-Regel verstößt als das Einfügen eines schwarzen Knotens. Der Grund dafür ist: Das Einfügen eines schwarzen Knotens ändert immer die schwarze Höhe (Verstoß gegen Regel 4), aber das Einfügen eines roten Knotens hat nur eine halbe Wahrscheinlichkeit, gegen Regel 3 zu verstoßen. Darüber hinaus ist ein Verstoß gegen Regel 3 leichter zu korrigieren als ein Verstoß gegen Regel 4.
Beim Einfügen eines neuen Knotens kann dieses Gleichgewicht zerstört werden. Der rot-schwarze Baum korrigiert das Gleichgewicht hauptsächlich auf drei Arten, indem er die Knotenfarbe ändert: Linksdrehung und Rechtsdrehung. (Spezifische Regeln weggelassen)
Da jeder Rot-Schwarz-Baum auch ein spezialisierter binärer Suchbaum ist, sind die schreibgeschützten Vorgänge am Rot-Schwarz-Baum dieselben wie die schreibgeschützten Vorgänge am gewöhnlichen binären Suchbaum. Das Einfügen und Löschen von Vorgängen in einem rot-schwarzen Baum entspricht jedoch nicht mehr den Eigenschaften eines rot-schwarzen Baums. Die Wiederherstellung der Eigenschaften eines Rot-Schwarz-Baums erfordert einen kleinen (O(logn)) Farbwechsel (eigentlich sehr schnell) und nicht mehr als drei Baumrotationen (zwei für Einfügevorgänge). Obwohl das Einfügen und Löschen komplex ist, kann die Operationszeit dennoch auf O(logn)-Zeiten gehalten werden.
Die Höhe eines rot-schwarzen Baums mit n internen Knoten beträgt höchstens 2lg(n+1).
Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in binäre Suchbäume in Python (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
