class Node:
  def __init__(id, symbol = None):
    self.id = id
    self.valeur = 1
    self.symbol = symbol
    self.pere = None
    self.gauche = None
    self.droit = None
    self.special = False

def modification(H, s):
  if s in [t.valeur for t in H]:
    Q = getNode(H, s)
    if ((Q.pere == getSpecialNode(H).pere) and (Q.pere == finBloc(H, Q)):
      Q = Q.pere
  else:
    special = getSpecialNode(H)
    Q = special.pere
    special = Node(special.id)
    special.left = Node(special.id - 2, pere = special)
    special.right = Node(special.id -1, pere = special, valeur = s)
  return traitement(H, Q)

def traitement(H, Q):
  C = getChemin(Q)
  xs = [t.valeur for t in C]
  if isIncrementable(H, Q):
    [t.valeur += 1 for t in C]
    return H
  else:
    m = getFirstIndex(H, C).id
    b = finBloc(H, m)
    ajouterUne(getChemin(Q, m))
    # Fini ici

def getFirstIndex(H, C)
  for n in C:
    if n.pere and n.weight >= getNext(H, n.id).weight:
      return n

def isIncrementable(H, C):
  for n in C:
    if n.pere and n.weight >= getNext(H, n.id).weight:
      return False
  return True

def getNext(H, id):
  for node in H:
    if node.id == (id + 1):
      return node

def getChemin(Q, chemin = []):
  if Q.pere:
    return getChemin(Q.pere, chemin.append(Q))
  else:
    return chemin

def getNode(H, s):
  for node in H:
    if node.valeur == s:
      return node

def getSpecialNode(H):
  for node in H:
    if node.special:
      return node

############################

H = [Node(100)]
for char in "ab":
  H = modification(H, char)