AVL Tree en python

Question

J'ai actuellement des problèmes avec un arbre AVL en Python 3. J'ai écrit le code source que je suis, qui est sur une vidéo, mais il agit bizarrement et je ne sais pas pourquoi.

Voici le code:

class Node(object): 
    def __init__(self, data, parentNode): 
     self.data = data 
     self.parentNode = parentNode 
     self.rightChild = None 
     self.leftChild = None 
     self.balance = 0 

    def insert(self, data, parentNode): 
     if data < self.data: 
      if not self.leftChild: 
       self.leftChild = Node(data, parentNode) 
      else: 
       self.leftChild.insert(data, parentNode) 
     else: 
      if not self.rightChild: 
       self.rightChild = Node(data, parentNode) 
      else: 
       self.rightChild.insert(data, parentNode) 

     return parentNode 

    def traverseInOrder(self): 
     if self.leftChild: 
      self.leftChild.traverseInOrder() 

     print(self.data) 

     if self.rightChild: 
      self.rightChild.traverseInOrder() 

    def getMax(self): 
     if not self.rightChild: 
      return self.data 
     else: 
      return self.rightChild.getMax() 

    def getMin(self): 
     if not self.leftChild: 
      return self.data 
     else: 
      return self.leftChild.getMin() 


class BalancedTree(object): 
    def __init__(self): 
     self.rootNode = None 

    def insert(self, data): 

     parentNode = self.rootNode 

     if self.rootNode == None: 
      parentNode = Node(data, None) 
      self.rootNode = parentNode 
     else: 
      parentNode = self.rootNode.insert(data, self.rootNode) 

      self.rebalanceTree(parentNode) 

    def rebalanceTree(self, parentNode): 
     self.setBalance(parentNode) 

     if parentNode.balance < -1: 
      if self.height(parentNode.leftChild.leftChild) >= self.height(parentNode.leftChild.rightChild): 
       parentNode = self.rotateRight(parentNode) 
      else: 
       parentNode = self.rotateLeftRight(parentNode) 
     elif parentNode.balance > 1: 
      if self.height(parentNode.rightChild.rightChild) >= self.height(parentNode.rightChild.leftChild): 
       parentNode = self.rotateLeft(parentNode) 
      else: 
       parentNode = self.rotateRightLeft(parentNode) 

     if parentNode.parentNode is not None: 
      self.rebalanceTree(parentNode.parentNode) 
     else: 
      self.rootNode = parentNode 

    def rotateLeftRight(self, node): 
     print("Rotation left right....") 
     node.leftChild = self.rotateLeft(node.leftChild) 
     return self.rotateRight(node) 

    def rotateRightLeft(self, node): 
     print("Rotation right left....") 
     node.rightChild = self.rotateRight(node.rightchild) 
     return self.rotateLeft(node) 

    def rotateLeft(self, node): 

     print("Rotate left....") 
     b = node.rightChild 
     b.parentNode = node.parentNode 
     node.rightChild = b.leftChild 

     if node.rightChild is not None: 
      node.rightChild.parentNode = node 

     b.leftChild = node 
     node.parentNode = b 

     if b.parentNode is not None: 
      if b.parentNode.rightChild == node: 
       b.parentNode.rightChild = b 
      else: 
       b.parentNode.leftChild = b 

     self.setBalance(node) 
     self.setBalance(b) 

     return b 

    def rotateRight(self, node): 
     print("Rotation right....") 
     b = node.leftChild 
     b.parentNode = node.parentNode 

     node.leftChild = b.rightChild 

     if node.leftChild is not None: 
      node.leftChild.parentNode = node 

     b.rightChild = node 
     node.parentNode = b 

     if b.parentNode is not None: 
      if b.parentNode.rightChild == node: 
       b.parentNode.rightChild = b 
      else: 
       b.parentNode.leftChild = b 

     self.setBalance(node) 
     self.setBalance(b) 

     return b 

    def setBalance(self, node): 
     node.balance = (self.height(node.rightChild) - self.height(node.leftChild)) 

    def height(self, node): 
     if node == None: 
      return -1 
     else: 
      return 1 + max(self.height(node.leftChild), self.height(node.rightChild)) 

Comme je l'ai tester, voici ce qui se passe.

créer un arbre:

tree = BalancedTree() 

J'essaie alors d'insérer 3 intergers.

tree.insert(4) 
tree.insert(2) 

Maintenant, lorsque j'entre le troisième numéro.

tree.insert(3) 

Je reçois cette sortie sans appel de fonctions.

Rotation left right....
Rotate left....
Rotation right....

C'est ce qui se passe. J'essaie de traverser l'arbre. Je reçois cette erreur.

Traceback (most recent call last): File "", line 1, in tree.traverseInOrder() AttributeError: 'BalancedTree' object has no attribute 'traverseInOrder'

Pourtant la vidéo que je suis son code fonctionne bien. Je suis perdu car j'ai relooké le code pour voir si j'ai fait une erreur quelque part et ne semble pas l'avoir fait. Qu'est-ce que je rate? Dans son code, il n'y a pas de fonction traverseInOrder pour l'arbre lui-même. Pourtant, il est capable de l'appeler et de l'exécuter très bien. Quelqu'un peut-il expliquer pourquoi cela se passe? S'il te plaît et merci.

Answer 1

Le problème immédiat est que votre indentation est incorrecte pour l'utilisation que vous donnez. Comme affiché, nœud de classe se compose de seulement ceci:

class Node(object): 

    def __init__(self, data, parentNode): 
    self.data = data 
    self.parentNode = parentNode 
    self.rightChild = None 
    self.leftChild = None 
    self.balance = 0 

Ensuite, vous avez quelques fonctions indépendantes, suivi de votre trivial balancedTree classe, et quelques autres fonctions indépendantes. Cependant, cela ne vous permettrait pas d'insérer une valeur comme vous l'avez fait, il semble donc que le code affiché n'est pas ce qui produit la sortie que vous avez donnée.

---

MISE À JOUR

Je fixe l'indentation. Le code semble insérer correctement et équilibrer l'arbre de 3 nœuds. Cependant, il n'y a pas d'erreur. La ligne de code que vous citez,

tree.traverseInOrder() 

n'apparait pas dans votre code affiché. Sans code précis et le message d'erreur complet, y compris la trace complète, nous ne pouvons pas déboguer votre problème.

J'ai également essayé d'ajouter cette ligne au bas de votre code, et j'ai enfin reçu le message d'erreur que vous citez. Le système d'exécution est correct (pas de surprise): il n'y a pas de méthode traverseInOrder pour la classe BalancedTree. Ce nom existe pour la classe Noeud, mais ce n'est pas ce que vous avez appelé. Vous avez confondu vos deux classes. Triez cela, et le code pourrait bien fonctionner.

Answer 2

Si elle aide, voici un exemple simple de AVL Arbre en python:
https://github.com/jeff-alves/AVLTree