Comment puis-je implémenter un arbre en Python ?

Question

J'essaie de construire un arbre général.

Existe-t-il des structures de données intégrées dans Python pour l'implémenter ?

Answer 1

Python ne dispose pas d'une gamme aussi étendue de structures de données "intégrées" que Java. Cependant, comme Python est dynamique, il est facile de créer un arbre général. Par exemple, un arbre binaire pourrait être :

class Tree:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

Vous pouvez l'utiliser comme ceci :

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"

Si vous avez besoin d'un nombre arbitraire d'enfants par nœud, utilisez une liste d'enfants :

class Tree:
    def __init__(self, data):
        self.children = []
        self.data = data

left = Tree("left")
middle = Tree("middle")
right = Tree("right")
root = Tree("root")
root.children = [left, middle, right]

Answer 2

Vous pouvez essayer :

from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'

Comme suggéré ici : https://gist.github.com/2012250

Answer 3

Il n'y a pas d'arbres intégrés, mais vous pouvez facilement en construire un en sous-classant un type Node à partir de List et en écrivant les méthodes de traversée. Si vous faites cela, j'ai trouvé que bissecter utile.

Il existe également de nombreuses implémentations sur PyPi que vous pouvez parcourir.

Si je me souviens bien, la bibliothèque standard de Python n'inclut pas les structures de données arborescentes pour la même raison que la bibliothèque de classes de base de .NET : la localité de la mémoire est réduite, ce qui entraîne plus de ratés de cache. Sur les processeurs modernes, il est généralement plus rapide de mettre une grande partie de la mémoire dans le cache, et les structures de données "riches en pointeurs" annulent cet avantage.

Answer 4

J'ai implémenté un arbre raciné comme un dictionnaire {child:parent} . Ainsi, par exemple, avec le nœud racine 0 un arbre pourrait ressembler à ça :

tree={1:0, 2:0, 3:1, 4:2, 5:3}

Cette structure permettait de remonter assez facilement le long d'un chemin de n'importe quel nœud à la racine, ce qui était pertinent pour le problème sur lequel je travaillais.

Answer 5

J'ai implémenté des arbres en utilisant des dicts imbriqués. C'est assez facile à faire, et cela a fonctionné pour moi avec des ensembles de données assez importants. J'ai posté un exemple ci-dessous, et vous pouvez en voir plus à l'adresse suivante Code Google

  def addBallotToTree(self, tree, ballotIndex, ballot=""):
    """Add one ballot to the tree.

    The root of the tree is a dictionary that has as keys the indicies of all 
    continuing and winning candidates.  For each candidate, the value is also
    a dictionary, and the keys of that dictionary include "n" and "bi".
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.

    If candidate c is a winning candidate, then that portion of the tree is
    expanded to indicate the breakdown of the subsequently ranked candidates.
    In this situation, additional keys are added to the tree[c] dictionary
    corresponding to subsequently ranked candidates.
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
    tree[c][d]["n"] is the number of ballots that rank c first and d second.
    tree[c][d]["bi"] is a list of the corresponding ballot indices.

    Where the second ranked candidates is also a winner, then the tree is 
    expanded to the next level.  

    Losing candidates are ignored and treated as if they do not appear on the 
    ballots.  For example, tree[c][d]["n"] is the total number of ballots
    where candidate c is the first non-losing candidate, c is a winner, and
    d is the next non-losing candidate.  This will include the following
    ballots, where x represents a losing candidate:
    [c d]
    [x c d]
    [c x d]
    [x c x x d]

    During the count, the tree is dynamically updated as candidates change
    their status.  The parameter "tree" to this method may be the root of the
    tree or may be a sub-tree.
    """

    if ballot == "":
      # Add the complete ballot to the tree
      weight, ballot = self.b.getWeightedBallot(ballotIndex)
    else:
      # When ballot is not "", we are adding a truncated ballot to the tree,
      # because a higher-ranked candidate is a winner.
      weight = self.b.getWeight(ballotIndex)

    # Get the top choice among candidates still in the running
    # Note that we can't use Ballots.getTopChoiceFromWeightedBallot since
    # we are looking for the top choice over a truncated ballot.
    for c in ballot:
      if c in self.continuing | self.winners:
        break # c is the top choice so stop
    else:
      c = None # no candidates left on this ballot

    if c is None:
      # This will happen if the ballot contains only winning and losing
      # candidates.  The ballot index will not need to be transferred
      # again so it can be thrown away.
      return

    # Create space if necessary.
    if not tree.has_key(c):
      tree[c] = {}
      tree[c]["n"] = 0
      tree[c]["bi"] = []

    tree[c]["n"] += weight

    if c in self.winners:
      # Because candidate is a winner, a portion of the ballot goes to
      # the next candidate.  Pass on a truncated ballot so that the same
      # candidate doesn't get counted twice.
      i = ballot.index(c)
      ballot2 = ballot[i+1:]
      self.addBallotToTree(tree[c], ballotIndex, ballot2)
    else:
      # Candidate is in continuing so we stop here.
      tree[c]["bi"].append(ballotIndex)