Welche Methoden gibt es, um einen binären Suchbaum in Python zu implementieren?

Einführung in Bäume

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:

1. Verwenden Sie Klassen und rekursive Funktionen zur Implementierung Definieren Sie eine Knotenklasse, einschließlich Knotenwerten, linken und rechten untergeordneten Knoten und anderen Attributen, und implementieren Sie dann Einfügen, Suchen, Löschen und andere Vorgänge über rekursive Funktionen. Das Codebeispiel lautet wie folgt:

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 node

2. Verwenden Sie die Listenimplementierung, indem Sie eine Liste verwenden, um die Elemente des binären Suchbaums zu speichern, und dann Operationen wie Einfügen, Suchen und Löschen über die Positionsbeziehung der Elemente implementieren in der Liste. Das Codebeispiel lautet wie folgt:

class 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:
            self

3. Verwenden Sie ein Wörterbuch zur Implementierung von

wobei der Schlüssel des Wörterbuchs den Knotenwert darstellt und der Wert des Wörterbuchs ein Wörterbuch ist, das die linken und rechten untergeordneten Knoten enthält. Das Codebeispiel lautet wie folgt:

• 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 tree

  Da 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.

4. Verwenden Sie Stack zum Implementieren

• 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 eine Knotenklasse, einschließlich Knotenwert, linker und rechter Unterknoten und anderer Attribute.

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.

Es ist zu beachten, dass es bei dieser Implementierung aufgrund der Verwendung eines Stapels zum Speichern des Prozesses des Durchlaufens des Baums zu einer hohen Speichernutzung kommen kann. Darüber hinaus kann diese Implementierung aufgrund der Eigenschaften des Stapels nur die Tiefendurchquerung (Depth-First Search, DFS) und keine Breitendurchquerung (Breadth-First Search, BFS) unterstützen.

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 root

Das 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!