Quelles sont les méthodes pour implémenter un arbre de recherche binaire en python

Introduction à l'arbre

L'arbre est différent de la liste chaînée ou de la table de hachage. Il s'agit d'une structure de données non linéaire qui est divisée en arbre binaire, arbre de recherche binaire, arbre B, arbre B+. , arbres rouges et noirs et ainsi de suite.

Un arbre est une structure de données, qui est un ensemble de relations hiérarchiques composées de n nœuds limités. Si vous utilisez une image pour le représenter, vous pouvez voir qu’il ressemble à un arbre à l’envers. Par conséquent, nous appelons collectivement ce type de structure de données un arbre, avec la racine en haut et les feuilles en bas. Un arbre général a les caractéristiques suivantes :

• Chaque nœud a 0 ou plusieurs nœuds enfants

• Aucun. Le nœud du nœud parent est appelé nœud racine. 🎜#Chaque nœud enfant peut être divisé en plusieurs sous-arbres disjoints

• La définition d'un arbre binaire est la suivante : chaque nœud a au plus deux nœuds enfants. Autrement dit, chaque nœud ne peut avoir que les quatre situations suivantes :

• Le sous-arbre de gauche et le sous-arbre de droite sont vides

#🎜🎜 #

Seul le sous-arbre de gauche existe

• Seul le sous-arbre de droite existe

• Le sous-arbre de gauche et Le bon sous-arbre existe

• Arbre de recherche binaire
  L'arbre de recherche binaire est également appelé arbre de tri binaire, il peut s'agir d'un arbre vide, ou un arbre binaire avec les propriétés suivantes :

• Si son sous-arbre gauche n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre gauche sont inférieures à celle du nœud racine Si son sous-arbre droit n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre droit sont supérieures à la valeur du nœud racine

Son nœud gauche et les sous-arbres de droite sont également respectivement Arbre de recherche binaire

• Répertoriez plusieurs méthodes d'implémentation courantes en Python :
  1 Utilisez des classes et des fonctions récursives pour implémenter #. 🎜 🎜#
En définissant une classe de nœud, y compris la valeur du nœud, les sous-nœuds gauche et droit et d'autres attributs, puis l'insertion, la recherche, la suppression et d'autres opérations sont implémentées via des fonctions récursives. L'exemple de code est le suivant :

• 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. Utilisez une liste pour implémenter

En utilisant une liste pour stocker les éléments de l'arbre de recherche binaire, puis en les insérant via la relation de position des éléments dans la liste, la recherche, la suppression et d'autres opérations. L'exemple de code est le suivant :

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. Utilisez un dictionnaire pour implémenter

où la clé du dictionnaire représente la valeur du nœud et la valeur du dictionnaire est un dictionnaire contenant les nœuds enfants gauche et droit. L'exemple de code est le suivant :

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

Étant donné que le dictionnaire n'est pas ordonné, cette implémentation peut entraîner un déséquilibre de l'arbre de recherche binaire, affectant l'efficacité des opérations d'insertion, de recherche et de suppression.

4. Utilisez la pile pour implémenter

En utilisant la pile (Stack), un simple arbre de recherche binaire peut être implémenté et des opérations telles que l'insertion, la recherche et la suppression peuvent être implémentées de manière itérative. Le processus de mise en œuvre spécifique est le suivant :

Définissez une classe de nœud, y compris la valeur du nœud, les sous-nœuds gauche et droit et d'autres attributs.

Définissez une pile et poussez d'abord le nœud racine sur la pile.

Lorsque la pile n'est pas vide, sortez l'élément supérieur de la pile et opérez dessus : si la valeur à insérer est inférieure à la valeur actuelle du nœud, la valeur à insérer est utilisée comme Insérer le nœud enfant gauche et pousser le nœud enfant gauche sur la pile ; si la valeur à insérer est supérieure à la valeur actuelle du nœud, insérer la valeur à insérer comme nœud enfant droit et pousser le nœud enfant de droite sur la pile ; si la valeur à trouver ou à supprimer est égale à la valeur actuelle du nœud, renvoie ou supprime le nœud.
Une fois l'opération terminée, continuez à prendre le nœud suivant de la pile et opérez jusqu'à ce que la pile soit vide.
Il convient de noter que dans cette implémentation, en raison de l'utilisation d'une pile pour stocker le processus de parcours de l'arborescence, cela peut entraîner une utilisation élevée de la mémoire. De plus, en raison des caractéristiques de la pile, cette implémentation ne peut prendre en charge que la recherche en profondeur d'abord (Depth-First Search, DFS) et ne peut pas prendre en charge la recherche en largeur d'abord (BFS).

• Ce qui suit est un exemple de pseudocode :

  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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!