350
8 Arbres m-aires et quadrants
multi-dimensionnelles de dimension d ≥ 2 fixée, et tenons compte de ceci pour
choisir le type d’arbres de recherche dans lequel seront stockées les clés : les arbres
quadrants de recherche, que nous avons définis en section 3.2.2 (b). Rappelons
aussi que nous notons Q leur ensemble, et Q n l’ensemble des arbres quadrants de
recherche contenant n clés.
Pour les analyses, nous nous ramenons au cas où la distribution sur les clés est
prise uniforme sur [0, 1] d : chaque coordonnée est une variable aléatoire uniforme
à valeurs dans l’intervalle [0, 1], et les coordonnées sont supposées indépendantes.
De plus, nous supposons que les différentes clés sont indépendantes ; les clés sont
donc presque sûrement toutes distinctes.
Comme pour les arbres binaires de recherche (cf. section. 2.2.3), nous mettons en
relation un arbre quadrant avec un ensemble de clés et un ordre d’insertion de ces
clés ; plusieurs ordres d’insertion donnent la même forme d’arbre. Il se pose alors
la question de définir ce que nous entendons par « loi de probabilité d’un arbre »,
et nous le ferons par analogie avec les arbres binaires de recherche. Rappelons donc
d’abord le cas des arbres binaires de recherche, qui correspond à d = 1.
– Les n clés d’un arbre binaire de recherche sont tirées de façon indépendante dans
l’intervalle [0, 1] muni de la loi uniforme, que nous notons Ord 1 . C’est le modèle
des permutations uniformes : seul l’ordre des clés, et non leurs valeurs, compte,
et nous obtenons la même forme d’arbre en insérant la permutation associée à
la statistique d’ordre des n clés. La même distribution sur les arbres est donc
obtenue en tirant uniformément n clés dans [0, 1] ou en tirant uniformément une
permutation de S n .
– La loi Ord 1 sur les clés induit une loi de probabilité P n sur l’ensemble B n des
arbres binaires à n nœuds. De plus, l’insertion d’une nouvelle clé, en d’autres
termes le passage de P n à P n+1 , se fait uniformément : la probabilité d’insérer la
n + 1-ième clé à la place correspondant à la k-ième possibilité d’insertion d’un
arbre aléatoire τ n , sous la distribution de probabilité P n , est uniforme et vaut
1
n + 1
.
Pour les arbres quadrants avec d ≥ 2, nous avons l’analogue de la situation
précédente.
– L’analogue de B n est maintenant Q n , ensemble des formes d’arbres quadrants
sur n clés.
– Nous nous plaçons dans le cas où les n clés sont des variables aléatoires i.i.d.
de loi uniforme dans [0, 1] d ; notons cette loi Ord d . Comme pour la dimension
d = 1, les valeurs exactes des clés n’importent pas ; seule compte la géométrie
du découpage de l’espace qu’elles induisent. En d’autres termes, nous obtenons
la même distribution sur les arbres, en tirant uniformément et indépendamment
n clés de [0, 1] d , ou en tirant uniformément un élément de S d
n .
– Toujours en poursuivant l’analogie avec la dimension d = 1, la loi Ord d sur les
clés induit une distribution de probabilité P n sur Q n . La différence avec le cas
d = 1 vient du fait que l’insertion d’une nouvelle clé ne se fait plus de façon
8 Arbres m-aires et quadrants
multi-dimensionnelles de dimension d ≥ 2 fixée, et tenons compte de ceci pour
choisir le type d’arbres de recherche dans lequel seront stockées les clés : les arbres
quadrants de recherche, que nous avons définis en section 3.2.2 (b). Rappelons
aussi que nous notons Q leur ensemble, et Q n l’ensemble des arbres quadrants de
recherche contenant n clés.
Pour les analyses, nous nous ramenons au cas où la distribution sur les clés est
prise uniforme sur [0, 1] d : chaque coordonnée est une variable aléatoire uniforme
à valeurs dans l’intervalle [0, 1], et les coordonnées sont supposées indépendantes.
De plus, nous supposons que les différentes clés sont indépendantes ; les clés sont
donc presque sûrement toutes distinctes.
Comme pour les arbres binaires de recherche (cf. section. 2.2.3), nous mettons en
relation un arbre quadrant avec un ensemble de clés et un ordre d’insertion de ces
clés ; plusieurs ordres d’insertion donnent la même forme d’arbre. Il se pose alors
la question de définir ce que nous entendons par « loi de probabilité d’un arbre »,
et nous le ferons par analogie avec les arbres binaires de recherche. Rappelons donc
d’abord le cas des arbres binaires de recherche, qui correspond à d = 1.
– Les n clés d’un arbre binaire de recherche sont tirées de façon indépendante dans
l’intervalle [0, 1] muni de la loi uniforme, que nous notons Ord 1 . C’est le modèle
des permutations uniformes : seul l’ordre des clés, et non leurs valeurs, compte,
et nous obtenons la même forme d’arbre en insérant la permutation associée à
la statistique d’ordre des n clés. La même distribution sur les arbres est donc
obtenue en tirant uniformément n clés dans [0, 1] ou en tirant uniformément une
permutation de S n .
– La loi Ord 1 sur les clés induit une loi de probabilité P n sur l’ensemble B n des
arbres binaires à n nœuds. De plus, l’insertion d’une nouvelle clé, en d’autres
termes le passage de P n à P n+1 , se fait uniformément : la probabilité d’insérer la
n + 1-ième clé à la place correspondant à la k-ième possibilité d’insertion d’un
arbre aléatoire τ n , sous la distribution de probabilité P n , est uniforme et vaut
1
n + 1
.
Pour les arbres quadrants avec d ≥ 2, nous avons l’analogue de la situation
précédente.
– L’analogue de B n est maintenant Q n , ensemble des formes d’arbres quadrants
sur n clés.
– Nous nous plaçons dans le cas où les n clés sont des variables aléatoires i.i.d.
de loi uniforme dans [0, 1] d ; notons cette loi Ord d . Comme pour la dimension
d = 1, les valeurs exactes des clés n’importent pas ; seule compte la géométrie
du découpage de l’espace qu’elles induisent. En d’autres termes, nous obtenons
la même distribution sur les arbres, en tirant uniformément et indépendamment
n clés de [0, 1] d , ou en tirant uniformément un élément de S d
n .
– Toujours en poursuivant l’analogie avec la dimension d = 1, la loi Ord d sur les
clés induit une distribution de probabilité P n sur Q n . La différence avec le cas
d = 1 vient du fait que l’insertion d’une nouvelle clé ne se fait plus de façon