Les arbres et tas binomiaux

Arbres binomiaux

• Définition: Un arbre binomial est un arbre enraciné dans lequel les fils de chaque noeud sont ordonnés. Autrement dit, si un noeud a k fils, alors il existe un premier, deuxième, …etc fils

• Un arbre binomial est défini récursivement comme suit:

1) est constitué d’un noeud unique.

2) est constitué de deux arbres binomiaux reliés entre eux de la manière suivante:

La racine de l’un est le fils le plus à gauche de la racine de l’autre.

L’illustration est comme suit:

Propriétés des arbres binomiaux

Soit un arbre binomial.

1. Le nombre de noeuds de est

2. La hauteur de l’arbre est k.

3. Il existe exactement noeuds à la profondeur i, i = 1,2, …, k.

4. La racine a un degré k (supérieur au degré de tout autre noeud).

5. Si les fils de la racine sont numérotés de la gauche vers la droite par k-1, …1,0, alors le fils i est la racine de l’arbre .

Lemme: Le degré maximum d’un noeud quelconque dans un arbre binomial à n noeuds est log n.

Preuve (par récurrence sur k): Pour chaque propriété, la base est l’arbre binaire Vérifier que chaque propriété est valide pour est trivial.

Supposons que ce résultat soit vrai pour .

Maintenant:

1. L’arbre est constitué de deux copies de . Par conséquent,

l’arbre contient + =

noeuds.

Tas binomiaux

Définition: Un tas binomial T est un ensemble d’arbre binomiaux ayant les propriétés suivantes:

1. Chaque arbre binomial de T est ordonné en min-tas (max-tas)

2. Il existe dans T au plus un arbre binomial dont la racine possède un degré donné

Le seconde propriété implique qu’un tas binomial T à n noeuds est constitué d’au plus log n + 1 arbres bonomiaux. En effet, soit la représentation binaire de n

c’est-à-dire 0,...,)( bbnbin k

Comme le nombre de sommets d’un arbre binomial est , l’arbre binomial apparaît dans l’arbre T si, et seulement si,

nous avons

Exemple: pour n =13, nous avons bien

binaire(13) = <1,1,0,1>

Pour un arbre T binomial à 13 noeuds, il esr constitué des arbres binomiaux et

1ib

23, BB 0B

qui comportent, respectivement, 8, 4 et 1 noeuds. Un autre example

4

8

N=210=102 21 = 2

94

8

21 = 2 20 = 1

94

85

7

22 = 4 21 = 2 20 = 1

4

85

7

22 = 4

N=310=112

N=410=1002

N=510=1012

22 = 4

22 = 4

20 = 1 20 = 121 = 2

Comparaison des efficacités

Opération pire cas (tas binaire) pire cas (tas binomial)

création (1) (1)

insertion (log n) (log n)

minimum (1) (log n)

suppression racine (log n) (log n)

Union (n) (log n)

diminuer clé (log n) (log n)

supprimer un noeud (log n) (log n)

Représentation des tas binomiaux

Chaque arbre binomial se trouvant à l’intérieur d’un tas binomial est stocké dans la représentation “fils gauche, frère droit”

Chaque noeud x comporte:

1. Une clé ou tout autre information utile à l’application en question.

2. Un champ degre[x] représentant le nombre de fils de x.

3. Un pointeur p[x] sur son père

4. Un pointeur fils[x] sur son fils le plus à gauche

5. Un pointeur frere[x] sur le frère qui se trouve immédiatement à sa droite.

Les racines des arbres binomiaux, contenues dans un TAS binomial, sont organisées en liste chaînée, appelée liste des racines.

Les degrés des racines augmentent strictement lorsqu’on parcourt la liste des racines.

Si x est la racine d’un arbre binomial, frere[x] pointe sur la racine suivante dans la liste des racines.

On accède un tas binomial T, par le champ head[T] qui est le pointeur sur le premier élément de la liste des racines du TAS binomial T.

Opérations sur les tas binomiaux1. Création d’un tas binomial

2. Recherche du minimum

3. Union de deux tas binomiaux

4. Insertion d’une nouvelle valeur

5. Suppresion de la racine

6. Diminuer une clé.

7. Suppresion d’un noeud

1. La création d’un nouveau tas binomial

Pour se faire, on crée un objet H avec head[H]=null.

Cette opération se fait bien entendu en (1).

2. Recherche du minimum (maximun)

Puisqu’un TAS binomial est vant tout un tas, la clé minimum se trouve alors dans un noeud racine. Pour ce faire, nous cherchons donc le minimum parmi les élements qui sont atockés dans les racines, reliés à head de H.

Il est clair que la complexité de cette recherche est O(log n), pour la simple raison qu’il faut recherche ce minimum parmi les log n racines qui sont reliées entre elles.

Procédure de base

Avant de procéder aux autres opérations citées précédement, regardond de plus prés l’opération suivante: Lien binomial qui est l’opération de base des autres opérations.

Cette opération consiste à fusionner deux tas binomiaux dont les racines ont le même degré.

Soit donc un arbre Bk-1 de racine y et un autre arbre Ck-1 de racine z. Le noeud z devient la nouvelle racine d’un nouvelle Bk. On suppose ici

que le noeud z est plus petit que le noeud y (min-tas). Mais s’il s’agit d’un max-tas, on prend le max comme illsutré par l’exemple suivant.

Fonction Lien binomial

P[y] = z; le père de y est z.

Fere[y] = fils[z]

Fisl[z] = y

degre[z] = degre[z]+1

Exemple:

Insertion d’un nouvel élément dans H

L’algorithme est comme suit:

1. Convertir l’élément à insérer en un tas binomial

2. Mettre i = 0;

3. Si H contient déjà un

a. enlever de H

b. appliquer la fonction lien binomial à et pour

former

c. mettre i à i+1;

d. répéter l’étape 3.

4. Mettre comme dans H en mettant à jour le degré de sa racine

Illustration

Soit un tas de 4 arbre binomiaux (de 23 éléments) auquel on veut insérér un autre.

i = 0: on enlève de H et on le lie avec pour former :

i =1: enlever de H; ensuite lier à pour donner

i =2: enlever de H; ensuite lier à pour donner

i = 3: H ne contient pas . Par conséquent, on va lier H avec

. Le tas tas binomial H est constitué de deux arbres

binomiaux; Il contient 24 noeuds.

séquence d’insertions et complexité amortie

Insérer 10 insérer 20

Insérer 3

Insérer 8: pour ce faire, on enlève 3 de l’arbre; ensuite 3 et 8 sont liés entre eux; et finalement les deux tas binomiaux sont liés entre eux.

Insérer 30:

Insérer 15: pour ce faire, on enlève 30 de l’arbre; ensuite 30 et 15 sont liés entre eux; et finalement les deux tas

binomiaux de dimension 2 et 4 sont liés entre eux.

Complexité amortie de cette suite d’insertions

Supposons insertions à faire. Alors, il est facile de constater ce qui suit:•Pour n/2 insertions, le tas binomial n’a pas de

. Donc, on aura un seul lien à former.•Pour n/4 insertions, le tas binomial a mais pas de . Autrement dit, on aura 2 liens à effectuer.•Pour n/8 insertions, le tas binomial a et , mais pas de . Autrement dit, on aura 3 liens à faire.

En continuant de cette manière, on arrive à:

•Pour insertions, le tas binomial possède

, , …., mais point de

En additionnant les liens effectués, on obtient:

Autrement dit, la complexité amortie d’une opération d’insertion est O(1).

Union (fusion) de deux TAS binomiaux

Cette opération consiste à fusionner deux tas binomiaux, H1 et H2, en un tas binomial Resultat.

Étape 0:

1. Si aucun de H1 et H2 ne contient , alors ne rien faire

2. Si seul H1 ou H1 contient , alors le mettre dans Resultat.

3. Si H1 et H2 contienent tous les deux , alors

on les lie entre eux pour former . Ensuite, on sauvegarde ce TAS pour l’étape suivante.

Étape i (i = 1,2,…., log n)

Il peut y avoir de 0 à 3 : un de H1, un de H2 et un autre de l’étape précédente.

1. S’il n’y a pas , ne rien faire.

2. S’il n’ y a qu’un seul , le mettre dans le TAS Resultat

3. Sinon, lier deux pour avoir et le sauvegarder pour l’étape suivante.

4. S’il reste encore un , le mettre dans Resultat

S’il reste à la fin un de sauvegardé de la dernière étape, le mettre dans Resultat.

Il y a exactement log n étapes, chacune se fait en O(1). Par conséquent, l’algorithme s’exécute, dans le pire cas, en O(log n).

17

10 44

6

50

48 31

2937

318

24

23 22

8

55

45 32

30

25

712

33

15

41

28H1 H2

17

10 44

6

50

48 31

2937

318

24

23 22

8

55

45 32

30

25

712

33

15

41

28H1H2

17

10 44

6

50

48 31

2937

3

18

24

23 22

8

55

45 32

30

25

712

33

15

41

28

H1H2

17

10 44

6

50

48 31

2937

3

18

24

23 22

8

55

45 32

3025

7

12

33

15

41

28

H1H2

17

10 44

6

50

48 31

2937

3

18

24

23 22

8

55

45 32

3025

7

12

33

15

41

28

H1H2

Suppression du maximum (minimum)

1. Supprimer le Bi contenant le maximum (minimum) de H. Joindre les parties restantes de H en un nouvel arbre binomial H1

2. Supprimer la racine de Bi . Relier les sous-arbres binomiaux de la racine supprimée en un nouvel arbre binomial H2.

3. Fusionner H1 et H2.

Complexité:

• L’étape 1 est clairement en O(1)

• L’étape 2 se calcule comme suit: Comme Bi possède i enfants, il y a i pointeurs. Bi contient 2i

n noeuds, donc i log n. Ce qui nous donne un pire cas de O(log n).

• L’étape 3 est clairement en O(log n)

La complexité totale, dans le pire cas, est donc O(log n).

Exemple de suppression du minimum

17

10 44

6

50

48 31

2918

24

23 22

8

55

45 32

30

12

33

15

41

28

17

10 44

6

50

48 31

2918

24

23 22

8

55

45 32

30

12

33

15

41

28

17

1044

50

48 31

29

18

24

23 22

8

55

45 32

30

12

33

15

41

28

17

1044

50

48 31

29

18

24

23 22

8

55

45 32

30

12

33

15

41

28

17

1044

50

48 31

29

18 24

23 22

8

55

45 32

3012 33

15

41

28

17

1044

50

48 31

29

18 24

23 22

8

55

45 32

3012 33

15

41

28

17

1044

50

48 31

2918 24

23 22

8

55

45 32

3012

33

15

41

28

Diminuer une clé donnée

procedure DecreaseKey(BinomialHeap H, Node P, int Key):

Parent P.Parentwhile Parent 0 and P.Key < Parent.Key do

P.Key Parent.KeyP.Data Parent.DataP ParentParent Parent.Parent

Diminuer une clé

17

1044

50

48 31

2918 24

23 22

8

55

45 32

3012

33

15

41

28

10

17

1044

10

48 31

2918 24

23 22

8

55

45 32

3012

33

15

41

28

17

1044

48

10 31

2918 24

23 22

8

55

45 32

3012

33

15

41

28

17

1044

48

29 31

1018 24

23 22

8

55

45 32

3012

33

15

41

28

17

1044

48

29 31

1518 24

23 22

8

55

45 32

3012

33

10

41

28