Ein Baum unterscheidet sich von einer verknüpften Liste oder einer Hash-Tabelle. Es handelt sich um eine nichtlineare Datenstruktur. Bäume werden in binäre Bäume, binäre Suchbäume, B-Bäume, B+-Bäume und rot-schwarze Bäume unterteilt , usw.
Baum ist eine Datenstruktur, bei der es sich um eine Sammlung hierarchischer Beziehungen handelt, die aus n begrenzten Knoten bestehen. Wenn Sie ein Bild verwenden, um es darzustellen, können Sie sehen, dass es wie ein umgedrehter Baum aussieht. Daher bezeichnen wir diese Art von Datenstruktur zusammenfassend als Baum, mit der Wurzel oben und den Blättern unten. Ein allgemeiner Baum hat die folgenden Eigenschaften:
Jeder Knoten hat 0 oder mehr untergeordnete Knoten
Ein Knoten ohne übergeordneten Knoten wird Wurzelknoten genannt
Jeder Nicht-Wurzelknoten hat und hat nur einen übergeordneten Knoten Knoten
Jeder untergeordnete Knoten kann in mehrere disjunkte Teilbäume unterteilt werden
Die Definition eines Binärbaums lautet: Jeder Knoten hat höchstens zwei untergeordnete Knoten. Das heißt, jeder Knoten kann nur die folgenden vier Situationen haben:
Sowohl der linke Teilbaum als auch der rechte Teilbaum sind leer.
Nur der linke Teilbaum existiert Der linke Teilbaum existiert sowohl im Baum als auch im rechten Teilbaum Der linke Teilbaum ist nicht leer, dann sind die Werte aller Knoten im linken Teilbaum kleiner als der Wert des Wurzelknotens. Wenn sein rechter Teilbaum nicht leer ist, dann sind die Werte aller Knoten im rechten Teilbaum sind größer als der Wert des Wurzelknotens.
Seine linken und rechten Teilbäume sind jeweils auch binäre Suchbäume.
Listen Sie mehrere gängige Implementierungsmethoden in Python auf:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
if self.root is None:
self.root = Node(value)
else:
self._insert(value, self.root)
def _insert(self, value, node):
if value < node.data:
if node.left is None:
node.left = Node(value)
else:
self._insert(value, node.left)
elif value > node.data:
if node.right is None:
node.right = Node(value)
else:
self._insert(value, node.right)
def search(self, value):
if self.root is None:
return False
else:
return self._search(value, self.root)
def _search(self, value, node):
if node is None:
return False
elif node.data == value:
return True
elif value < node.data:
return self._search(value, node.left)
else:
return self._search(value, node.right)
def delete(self, value):
if self.root is None:
return False
else:
self.root = self._delete(value, self.root)
def _delete(self, value, node):
if node is None:
return node
elif value < node.data:
node.left = self._delete(value, node.left)
elif value > node.data:
node.right = self._delete(value, node.right)
else:
if node.left is None and node.right is None:
del node
return None
elif node.left is None:
temp = node.right
del node
return temp
elif node.right is None:
temp = node.left
del node
return temp
else:
temp = self._find_min(node.right)
node.data = temp.data
node.right = self._delete(temp.data, node.right)
return node
def _find_min(self, node):
while node.left is not None:
node = node.left
return nodeclass BST:
def __init__(self):
self.values = []
def insert(self, value):
if len(self.values) == 0:
self.values.append(value)
else:
self._insert(value, 0)
def _insert(self, value, index):
if value < self.values[index]:
left_child_index = 2 * index + 1
if left_child_index >= len(self.values):
self.values.extend([None] * (left_child_index - len(self.values) + 1))
if self.values[left_child_index] is None:
self.values[left_child_index] = value
else:
self._insert(value, left_child_index)
else:
right_child_index = 2 * index + 2
if right_child_index >= len(self.values):
self.values.extend([None] * (right_child_index - len(self.values) + 1))
if self.values[right_child_index] is None:
self.values[right_child_index] = value
else:
self._insert(value, right_child_index)
def search(self, value):
if value in self.values:
return True
else:
return False
def delete(self, value):
if value not in self.values:
return False
else:
index = self.values.index(value)
self._delete(index)
return True
def _delete(self, index):
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
if left_child_index < len(self.values) and self.values[left_child_index] is not None:
self._delete(left_child_index)
if right_child_index < len(self.values) and self.values[right_child_index] is not None:
self3. Verwenden Sie ein Wörterbuch zur Implementierung von
def insert(tree, value):
if not tree:
return {value: {}}
elif value < list(tree.keys())[0]:
tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value)
else:
tree[list(tree.keys())[0]][value] = {}
return tree
def search(tree, value):
if not tree:
return False
elif list(tree.keys())[0] == value:
return True
elif value < list(tree.keys())[0]:
return search(tree[list(tree.keys())[0]], value)
else:
return search(tree[list(tree.keys())[0]].get(value), value)
def delete(tree, value):
if not search(tree, value):
return False
else:
if list(tree.keys())[0] == value:
if not tree[list(tree.keys())[0]]:
del tree[list(tree.keys())[0]]
elif len(tree[list(tree.keys())[0]]) == 1:
tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0]
else:
min_key = min(list(tree[list(tree.keys())[0]+1].keys()))
tree[min_key] = tree[list(tree.keys())[0]+1][min_key]
tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]]
del tree[list(tree.keys())[0]]
elif value < list(tree.keys())[0]:
tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value)
else:
tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value)
return treeDa das Wörterbuch ungeordnet ist, kann diese Implementierung dazu führen, dass der binäre Suchbaum unausgeglichen ist, was sich auf die Effizienz von Einfüge-, Such- und Löschvorgängen auswirkt.
Mit Stack (Stack) können Sie einen einfachen binären Suchbaum implementieren, der Operationen wie Einfügen, Suchen und Löschen durch Iteration implementieren kann. Der spezifische Implementierungsprozess ist wie folgt:
Definieren Sie einen Stapel und schieben Sie zunächst den Wurzelknoten auf den Stapel.
Wenn der Stapel nicht leer ist, nehmen Sie das oberste Element des Stapels heraus und bearbeiten Sie es: Wenn der einzufügende Wert kleiner als der aktuelle Knotenwert ist, fügen Sie den einzufügenden Wert als linken untergeordneten Knoten ein Schieben Sie den linken untergeordneten Knoten auf den Stapel. Wenn der einzufügende Wert größer als der aktuelle Knotenwert ist, fügen Sie den einzufügenden Wert als rechten untergeordneten Knoten ein und verschieben Sie den rechten untergeordneten Knoten auf den Stapel oder gelöscht ist gleich dem aktuellen Knotenwert, geben Sie den Knoten zurück oder löschen Sie ihn.
Nachdem der Vorgang abgeschlossen ist, fahren Sie fort, den nächsten Knoten vom Stapel zu nehmen und zu arbeiten, bis der Stapel leer ist.
Das Folgende ist ein Pseudocode-Beispiel:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(root, value):
if not root:
return Node(value)
stack = [root]
while stack:
node = stack.pop()
if value < node.data:
if node.left is None:
node.left = Node(value)
break
else:
stack.append(node.left)
elif value > node.data:
if node.right is None:
node.right = Node(value)
break
else:
stack.append(node.right)
def search(root, value):
stack = [root]
while stack:
node = stack.pop()
if node.data == value:
return True
elif value < node.data and node.left:
stack.append(node.left)
elif value > node.data and node.right:
stack.append(node.right)
return False
def delete(root, value):
if root is None:
return None
if value < root.data:
root.left = delete(root.left, value)
elif value > root.data:
root.right = delete(root.right, value)
else:
if root.left is None:
temp = root.right
del root
return temp
elif root.right is None:
temp = root.left
del root
return temp
else:
temp = root.right
while temp.left is not None:
temp = temp.left
root.data = temp.data
root.right = delete(root.right, temp.data)
return rootDas obige ist der detaillierte Inhalt vonWelche Methoden gibt es, um einen binären Suchbaum in Python zu implementieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
