L'arbre de recherche binaire en python ne fonctionnait pas

Question

class Node: 
    '''represents a new node in the BST''' 
    def __init__(self,key): 
     self.key=key 
     self.disconnect() 
    def disconnect(self): 
     self.left=None; 
     self.right=None; 
     self.parent=None; 
    def __str__(self): 
     return 'node with kay %s'%self.key 

class BST: 
    def __init__(self): 
     self.root=None 
    def insert(self,t): 
     '''inserts a new element into the tree''' 
     self.find_place(self.root,t) 

    def find_place(self,node,key): 
     """finds the right place of the element recursively""" 
     if node is None: 
      node=Node(key) 
      print node 
     else: 
      if node.key > key: 
       find_place(node.left,key) 
      else: 
       find_place(node.right,key) 
def test(): 
    '''function to test if the BST is working correctly''' 

J'ai écrit le code ci-dessus pour implémenter un arbre de recherche binaire mais la méthode insert ne fonctionne pas comme prévu, elle ne parvient même pas à ajouter l'élément racine. Je ne peux pas comprendre la cause.

Answer 1

Vous n'allez pas ajouter de nœuds à l'arborescence!

Il est plus facile de gérer explicitement l'ajout du nœud racine, comme vous pouvez le voir ci-dessous dans le insert.

Une fonction find_place retournera vraisemblablement le nœud parent et aussi s'il s'agit de l'emplacement gauche ou droit de la clé. J'ai fait une fonction explicite _do_insert ci-dessous que les deux marche et fait l'insertion. À partir de ce moment, vous devez parcourir l'arbre, chaque fois que vous voyez si vous recyclez une branche ou si vous avez atteint un emplacement vide, où vous ajoutez le nouveau nœud.

Il peut être naturel de refactoriser votre code pour mettre la responsabilité de marcher dans l'arbre (et de faire des ajouts, des suppressions et autres) dans la classe Node.

Dans le code ci-dessous, je ne pas tenir compte d'ajouter une clé qui est déjà dans l'arbre, je ne quitte silencieusement:

def insert(self,t): 
    '''inserts a new element into the tree''' 
    if self.root is None: 
     self.root = Node(t) 
    else: 
     self._do_insert(self.root,t) 

def _do_insert(self,parent,t): 
    if t > parent.key: 
     if parent.left is None: 
      parent.left = Node(t) 
     else: 
      self._do_insert(parent.left,t) 
    elif t < parent.key: 
     if parent.right is None: 
      parent.right = Node(t) 
     else: 
      self._do_insert(parent.right,t) 
    else: 
     # raise a KeyError or something appropriate? 
     pass 

Answer 2

Voici une autre BST avec Python, en utilisant une clé de tri

GAUCHE = 0 DROITE = 1 VALUE = 2 SORT_KEY = -1

classe BinarySearchTree (objet):

def __init__(self, sort_key=None): 
    self._root = [] 
    self._sort_key = sort_key 
    self._len = 0 

insérer def (self, val): si self._sort_key est None: sort_key = val // si aucune clé de tri, clé de tri est la valeur autre: sort_key = self._sort_key (val)

node = self._root 
while node: 
    if sort_key < node[_SORT_KEY]: 
     node = node[LEFT] 
    else: 
     node = node[RIGHT] 

if sort_key is val: 
    node[:] = [[], [], val] 
else: 
    node[:] = [[], [], val, sort_key] 
self._len += 1 

def minimum(self): 
    return self._extreme_node(LEFT)[VALUE] 

def maximum(self): 
    return self._extreme_node(RIGHT)[VALUE] 

def find(self, sort_key): 
    return self._find(sort_key)[VALUE] 

def _extreme_node(self, side): 
    if not self._root: 
     raise IndexError('Empty') 
    node = self._root 
    while node[side]: 
     node = node[side] 
    return node 

def _find(self, sort_key): 
    node = self._root 
    while node: 
     node_key = node[SORT_KEY] 
     if sort_key < node_key: 
      node = node[LEFT] 
     elif sort_key > node_key: 
      node = node[RIGHT] 
     else: 
      return node 
    raise KeyError("%r not found" % sort_key) 

La clé de tri est remplacée par la valeur le cas échéant.