E Rappel des notations utilisées
493
E.2.4 Arbres et sous-arbres associés à un arbre donné τ
– τ arbre binaire : sous-arbres gauche et droit τ (g) et τ (d) .
– Si u est un nœud de τ , alors τ u est le sous-arbre de τ dont la racine est u.
– τ arbre planaire non réduit à une feuille : τ i est le i-ième sous-arbre de la racine,
pour i compris entre 1 et l’arité de la racine.
– τ arbre marqué : π(τ ) est la forme de τ ; C(τ ) est l’arbre des rangs, obtenu par
marquage canonique de τ .
E.3 Constructions combinatoires
– SEQ : suite-de
– SEQ >0 : suite-non-vide-de
– SET : ensemble-de
– MSET : multi-ensemble
– MSET p : multi-ensemble de p éléments
Si A est un alphabet, A
∗ est la suite des mots finis sur A ; ε ∈ A
∗ est le mot
vide.
E.4 Notations probabilistes
L(X) :
loi (ou distribution) d’une variable aléatoire X.
L(X|Y = y) et L(X|Y ) : loi conditionnelle de X sachant Y .
P-p.s. :
un événement A est vrai P-p.s. quand P(A) = 1.
P(A, B) pour deux événements A et B : signifie P(A ∧ B) ou encore P(A ∩ B).
δ x : mesure de Dirac en x : mesure de masse 1 sur l’ensemble {x}, où x ∈ R d .
1 A :
fonction indicatrice de l’ensemble A : 1 A (x) = 1
quand x ∈ A et 1 A (x) = 0 quand x /
∈ A. Conséquence
: 1 A (x) = δ x (A).
X + est la partie positive de la variable aléatoire X, autrement dit : X + = max
(0, X).
Loi uniforme :
U.
Loi uniforme sur [0, 1] d : Ord d , pour d ≥ 1.
Loi Ord sur l’ensemble des arbres binaires de recherche, dite aussi modèle des
permutations uniformes : lorsque les clés insérées sont indépendantes et de même
loi. Loi Ord d sur les arbres quadrants de recherche,
quand les clés sont prises dans un ensemble qui est un
produit cartésien de d ensembles.