8.2 Arbres quadrants de recherche
351
uniforme. Plus précisément, considérons le passage de P n à P n+1 : la probabilité
d’insérer la n + 1-ième clé dans une des (2 d − 1)n + 1 possibilités d’insertion,
ou feuilles de l’arbre complété, qui correspondent chacune à une insertion dans
un sous-espace de [0, 1] d suivant le découpage induit par les n clés, dépend de
la feuille, et n’est plus uniforme (voir l’exercice 8.2 pour un exemple simple
illustrant cette non-équiprobabilité des places d’insertion).
Nous venons ainsi de décrire une loi de probabilité P n , induite sur l’ensemble
Q n des arbres quadrants de taille n par la loi uniforme sur les permutations. Comme
en dimension 1, les P n (n ≥ 0) sont compatibles, le théorème de Kolmogorov [28]
s’applique et les P n permettent de définir une probabilité P sur Q en disant que P
restreint aux arbres quadrants de taille n est égale à P n . Nous travaillons désormais
sous P.
Sous la loi P n définie sur Q n (ou de manière équivalente sous la loi P restreinte à
Q n ), un arbre quadrant τ a ses n clés tirées uniformément dans le domaine [0, 1] d .
En particulier, sa racine est choisie uniformément dans ce domaine.
Nous établissons maintenant les probabilités de partage, i.e., la loi de probabilité
jointe des tailles des sous-arbres, puis nous développons en section 8.2.4 une
approche générale des paramètres additifs qui nous permettra de traiter facilement,
par exemple, le nombre de nœuds de type donné. Nous étudierons enfin la
profondeur d’insertion d’une clé, pour laquelle nous proposons deux approches :
la première, combinatoire, est basée sur la loi des (tailles) des sous-arbres et est
détaillée en section 8.2.5 pour le cas d = 2, la seconde utilise des polynômes de
niveau et se trouve en section 8.2.7 ; au passage nous donnons aussi des résultats
sur la hauteur en section 8.2.6.
8.2.3 Probabilités induites sur les sous-arbres
Le modèle naturel sur les n clés est la loi uniforme dans [0, 1] d , notée Ord d , qui
induit une distribution de probabilité P n sur Q n . Comme déjà pour les arbres binaires
qui sont les formes des arbres binaires de recherche, les arbres quadrants de taille
donnée n, qui sont les formes d’arbres quadrants de recherche à n clés, ne sont pas
équiprobables (cf. l’exercice 8.3).
Soit τ un arbre quadrant de recherche à n clés, tirées uniformément dans le
domaine [0, 1] d ; les tailles de ses sous-arbres τ (0) , τ (1) , . . . , τ (2 d −1) sont notées
n 0 , n 1 , . . . , n 2 d −1 , avec
n 0 + n 1 + · · · + n 2 d −1 = n − 1.
La proposition suivante est un analogue d-dimensionnel de la proposition 2.13
« diviser pour régner » donnée pour les arbres binaires de recherche dans la
section 2.2.3, et dont la démonstration est omise.
351
uniforme. Plus précisément, considérons le passage de P n à P n+1 : la probabilité
d’insérer la n + 1-ième clé dans une des (2 d − 1)n + 1 possibilités d’insertion,
ou feuilles de l’arbre complété, qui correspondent chacune à une insertion dans
un sous-espace de [0, 1] d suivant le découpage induit par les n clés, dépend de
la feuille, et n’est plus uniforme (voir l’exercice 8.2 pour un exemple simple
illustrant cette non-équiprobabilité des places d’insertion).
Nous venons ainsi de décrire une loi de probabilité P n , induite sur l’ensemble
Q n des arbres quadrants de taille n par la loi uniforme sur les permutations. Comme
en dimension 1, les P n (n ≥ 0) sont compatibles, le théorème de Kolmogorov [28]
s’applique et les P n permettent de définir une probabilité P sur Q en disant que P
restreint aux arbres quadrants de taille n est égale à P n . Nous travaillons désormais
sous P.
Sous la loi P n définie sur Q n (ou de manière équivalente sous la loi P restreinte à
Q n ), un arbre quadrant τ a ses n clés tirées uniformément dans le domaine [0, 1] d .
En particulier, sa racine est choisie uniformément dans ce domaine.
Nous établissons maintenant les probabilités de partage, i.e., la loi de probabilité
jointe des tailles des sous-arbres, puis nous développons en section 8.2.4 une
approche générale des paramètres additifs qui nous permettra de traiter facilement,
par exemple, le nombre de nœuds de type donné. Nous étudierons enfin la
profondeur d’insertion d’une clé, pour laquelle nous proposons deux approches :
la première, combinatoire, est basée sur la loi des (tailles) des sous-arbres et est
détaillée en section 8.2.5 pour le cas d = 2, la seconde utilise des polynômes de
niveau et se trouve en section 8.2.7 ; au passage nous donnons aussi des résultats
sur la hauteur en section 8.2.6.
8.2.3 Probabilités induites sur les sous-arbres
Le modèle naturel sur les n clés est la loi uniforme dans [0, 1] d , notée Ord d , qui
induit une distribution de probabilité P n sur Q n . Comme déjà pour les arbres binaires
qui sont les formes des arbres binaires de recherche, les arbres quadrants de taille
donnée n, qui sont les formes d’arbres quadrants de recherche à n clés, ne sont pas
équiprobables (cf. l’exercice 8.3).
Soit τ un arbre quadrant de recherche à n clés, tirées uniformément dans le
domaine [0, 1] d ; les tailles de ses sous-arbres τ (0) , τ (1) , . . . , τ (2 d −1) sont notées
n 0 , n 1 , . . . , n 2 d −1 , avec
n 0 + n 1 + · · · + n 2 d −1 = n − 1.
La proposition suivante est un analogue d-dimensionnel de la proposition 2.13
« diviser pour régner » donnée pour les arbres binaires de recherche dans la
section 2.2.3, et dont la démonstration est omise.