2014_PyconFr.sagews

bt = BinaryTree([[None,[]],[[],[[[],[]],[None,[]]]]])
latex.eval(latex(bt))

''

bt.node_number()
bt.depth()
bt.is_complete()

11 5 False

BT = BinaryTrees()
BT

Binary trees

BT.cardinality()

+Infinity

BT2 = BinaryTrees(2)
BT2

Binary trees of size 2

BT2.cardinality()

2

latex.eval(latex(BT2[0]))

''

latex.eval(latex(BT2[1]))

''

BT3 = BinaryTrees(3)
BT3.cardinality()

5

for bt in BinaryTrees(3):
    latex.eval(latex(bt))

''

''

''

''

''

BinaryTrees(11).cardinality()

58786

len(list(BinaryTrees(11)))

58786

[BinaryTrees(i).cardinality() for i in xrange(10)]

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

[1/(n+1) * binomial(2*n, n) for n in xrange(10)]

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

def random_binary1(size):
    dw = DyckWords(size).random_element()
    return dw.to_binary_tree()
    
bt1 = random_binary1(11)
bt2 = random_binary1(11)
latex.eval(latex(bt1))
latex.eval(latex(bt2))

''

''

def random_binary2(size):
    p = Permutations(size).random_element()
    return p.binary_search_tree_shape()

bt1 = random_binary2(11)
bt2 = random_binary2(11)
latex.eval(latex(bt1))
latex.eval(latex(bt2))

''

''

mean([float(random_binary1(11).depth()) for i in xrange(1000)])

7.628

mean([float(random_binary2(11).depth()) for i in xrange(1000)])

5.9127

mean([float(random_binary1(100).depth()) for i in xrange(10000)])

30.0557

mean([float(random_binary2(100).depth()) for i in xrange(10000)])

13.3071