Le but de ce TP est d'implanter les fonctions usuelles telles que la génération exhaustive (fabriquer tous les éléments de l'ensemble), rank et unrank sur l'ensemble des arbres binaires.
Pour représenter les arbres binaires en python, on utilisera la structure suivante.
Exécutez les cellules suivantes et observez les exemples.
In [ ]:
class BinaryTree():
def __init__(self, children = None):
"""
A binary tree is either a leaf or a node with two subtrees.
INPUT:
- children, either None (for a leaf), or a list of size excatly 2
of either two binary trees or 2 objects that can be made into binary trees
"""
self._isleaf = (children is None)
if not self._isleaf:
if len(children) != 2:
raise ValueError("A binary tree needs exactly two children")
self._children = tuple(c if isinstance(c,BinaryTree) else BinaryTree(c) for c in children)
self._size = None
def __repr__(self):
if self.is_leaf():
return "leaf"
return str(self._children)
def __eq__(self, other):
"""
Return true if other represents the same binary tree as self
"""
if not isinstance(other, BinaryTree):
return False
if self.is_leaf():
return other.is_leaf()
return self.left() == other.left() and self.right() == other.right()
def left(self):
"""
Return the left subtree of self
"""
return self._children[0]
def right(self):
"""
Return the right subtree of self
"""
return self._children[1]
def is_leaf(self):
"""
Return true is self is a leaf
"""
return self._isleaf
def _compute_size(self):
"""
Recursively computes the size of self
"""
if self.is_leaf():
self._size = 0
else:
self._size = self.left().size() + self.right().size() + 1
def size(self):
"""
Return the number of non leaf nodes in the binary tree
"""
if self._size is None:
self._compute_size()
return self._size
leaf = BinaryTree()
In [ ]:
t = BinaryTree()
t
In [ ]:
t.size()
In [ ]:
t = BinaryTree([[leaf,leaf], leaf]) # a tree of size 2
t
In [ ]:
t.size()
In [ ]:
t = BinaryTree([leaf, [leaf,leaf]]) # a different tree of size 2
t
In [ ]:
t.size()
In [ ]:
t = BinaryTree([[leaf, leaf], [leaf, leaf]]) # a tree of size 3
t
In [ ]:
t.size()
Il y a 5 arbres binaires de taille 3. L'un deux est celui que nous venons de construire.
Construisez explicitement les 4 autres
In [ ]:
# t1 = BinaryTree(...)
In [ ]:
# t2 = BinaryTree(...)
In [ ]:
# t3 = BinaryTree(...)
In [ ]:
# t4 = BinaryTree(...)
Le but de ce TP est d'implanter les fonctions de la classe BinaryTrees ci-dessous (avec un "s" à la fin) qui représente l'ensemble des arbres binaires d'une taille donnée. La structure de la classe vous est donnée ainsi que les méthodes de base.
Complétez les méthodes manquantes puis exécutez les exemples ci-dessous.
In [ ]:
import math
import random
class BinaryTrees():
def __init__(self, size):
"""
The combinatorial set of binary trees of size `size`
INPUT:
- size a non negative integers
"""
self._size = size
def size(self):
"""
Return the size of the binary trees of the set
"""
return self._size
def __repr__(self):
"""
Default string repr of ``self``
"""
return "Binary Trees of size " + str(self._size)
def cardinality(self):
"""
Return the cardinality of the set
"""
# This is given to you
n = self._size
f = math.factorial(n)
return math.factorial(2*n)/(f*f*(n+1))
def __iter__(self):
"""
Iterator on the elements of the set
"""
# write code here
def first(self):
"""
Return the first element of the set
"""
for t in self:
return t
def rank(self,t):
"""
Return the rank of the binary tree t in the generation order of the set (starting at 0)
INPUT:
- t, a binary tree
"""
# write code here
def unrank(self,i):
"""
Return the binary tree corresponding to the rank ``i``
INPUT:
- i, a integer between 0 and the cardinality minus 1
"""
# write code here
def next(self,t):
"""
Return the next element following t in self
INPUT :
- t a binary tree
OUPUT :
The next binary tree or None if t is the last permutation of self
"""
# write code here
def random_element(self):
"""
Return a random element of ``self`` with uniform probability
"""
# write code here
In [ ]:
BinaryTrees(0)
In [ ]:
list(BinaryTrees(0))
In [ ]:
BinaryTrees(1)
In [ ]:
list(BinaryTrees(1))
In [ ]:
BinaryTrees(2)
In [ ]:
list(BinaryTrees(2))
In [ ]:
BT3 = BinaryTrees(3)
BT3
In [ ]:
list(BT3)
In [ ]:
t = BinaryTree(((leaf, leaf), (leaf, leaf)))
In [ ]:
BT3.rank(t)
In [ ]:
BT3.unrank(2)
In [ ]:
BT3.next(t)
In [ ]:
BT3.random_element()
La suite de tests que nous avions définies sur les permutations peut aussi s'appliquer sur les arbres binaires.
Exécutez la cellule suivante puis vérifiez que les tests passent sur les exemples.
In [ ]:
def test_cardinality_iter(S):
assert(len(list(S)) == S.cardinality())
def test_rank(S):
assert([S.rank(p) for p in S] == range(S.cardinality()))
def test_unrank(S):
assert(list(S) == [S.unrank(i) for i in xrange(S.cardinality())])
def test_next(S):
L = [S.first()]
while True:
p = S.next(L[-1])
if p == None:
break
L.append(p)
assert(L == list(S))
def all_tests(S):
tests = {"Cardinality / iter": test_cardinality_iter, "Rank": test_rank, "Unrank": test_unrank, "Next": test_next}
for k in tests:
print "Testsing: "+ k
try:
tests[k](S)
print "Passed"
except AssertionError:
print "Not passed"
In [ ]:
all_tests(BinaryTrees(3))
In [ ]:
all_tests(BinaryTrees(4))
In [ ]:
all_tests(BinaryTrees(5))
In [ ]:
all_tests(BinaryTrees(6))
Voici une fonction qui calcule un arbre binaire aléatoire. On se demande si chaque arbre est obenu avec une probabilité uniforme.
Exécutez les cellules ci-dessous puis déterminez expérimentalment si la distribution de probabilité est uniforme.
In [ ]:
import random
def random_grow(t):
"""
Randomly grows a binary tree
INPUT:
- t, a binary tree of size n
OUTPUT: a binary tree of size n+1
"""
if t.is_leaf():
return BinaryTree([leaf,leaf])
c = [t.left(),t.right()]
i = random.randint(0,1)
c[i] = random_grow(c[i])
return BinaryTree(c)
def random_binary_tree(n):
"""
Return a random binary tree of size n
"""
t = leaf
for i in xrange(n):
t = random_grow(t)
return t
In [ ]:
random_binary_tree(10)
In [ ]:
In [ ]:
In [ ]:
La hauteur d'un arbre se calcule récursivement : pour une feuille, la hauteur est 0, sinon c'est le max de la hauteur des fils +1.
Rajoutez une méthode height à la classe des arbres binaires et vérifiez son fonctionnement avec les tests suivants.
In [ ]:
assert BinaryTree([[leaf,leaf], leaf]).height() == 2
assert BinaryTree([leaf,[leaf, leaf]]).height() == 2
assert BinaryTree([[leaf,leaf], [leaf,leaf]]).height() == 2
assert BinaryTree([[leaf,[leaf,leaf]], [leaf,leaf]]).height() == 3
Calculez la hauteur moyenne de 100 arbres aléatoire de tailles 10, 100 et de 10 arbres aléatoires de taille 500, d'abord avec la méthode uniforme (de la classe BinaryTrees) puis avec la fonction random_trees interprétez le résultat
In [ ]:
In [ ]: