Structures de données IFT-10541 Abder Alikacem Semaine 10 Les arbres SPLAY Département...

Structures de données

IFT-10541

Abder AlikacemAbder Alikacem

Semaine 10

Les arbres SPLAY

Département d’informatique et de génie logiciel

Édition septembre 2009

6

3 8

4

v

z

Arbre SPLAY

Plan

L’heuristique SPLAY

Auto-ajustement (aucune information de hauteur ou de couleur)

Complexité amortie sur n opérations

Règle du 90-10 (90% des opérations effectuées sur 10% des données)

L’heuristique SPLAY

Toujours faire remonter le nœud résultant à la racine:

insertion: le nouvel élément devient la racine

recherche: le dernier noeud accédé devient la racine (recherche réussie ou non)

retrait: d’abord une recherche, puis un retrait

Algorithme (qui ne fonctionne pas)

Rotate-to-root: rotation simple de X avecson parent, jusqu’à ce que X soit à la racine.

Algorithme (qui ne fonctionne pas)

Accéder aux N éléments: N + ∑ i = Θ(N2)

t=N t=N t=N-1 t=N-2

Algorithme (qui ne fonctionne pas)

Accéder aux N éléments: N + ∑ i = Θ(N2)

t=N t=N t=N-1 t=N-2

12

Opération SPLAY qui fonctionne

Au lieu de rotate-to-root, SPLAY:

• X est fils de la racine: rotation simple (zig)• X est vers l’intérieur: rotation double (zigzag)• X est vers l’extérieur: P-G, puis X-P (zigzig)

Zig-Zig

Zig-Zag

Exemple

Exemple

Exemple

Exemple

Exemple

Exemple

Exemple

Exemple

Exemple

Exemple