Introduction: Arbres de recherche + Rappel: Arbres binaires de

  • View
    223

  • Download
    5

Embed Size (px)

Text of Introduction: Arbres de recherche + Rappel: Arbres binaires de

  • Introduction: Arbres de recherche+

    Rappel: Arbres binaires de recherche

  • Dictionnaires ordonns:

    Oprations principales:

    trouver(k):find(k):

    Si le dictionnaire a une entre de cl k, retourne la valeur associe cette entre, sinon retoune NULL.

    insrer(k,v): put(k,v):

    insrer lentre (k,v) dans le dictionnaire

    enlever(k): remove(k):

    Si le dictionnaire a une entre de cl k, lenlever et retourner sa valeur associe, sinon retourner NULL

    findAll(k): Retourne un itrateur de toutes les entres de cl k, ou NULL si aucune entre de cl k

    removeAll(k): Si le dictionnaire a une ou plusieurs entres de cl k, les enlever et retourner un itrateur des valeurs associes chacune de ces entres, sinon retouner NULL

    IFT2810, A2009, Sylvie HamelUniversit de Montral 1Arbres de Recherche: Intro+Binaires

  • Dictionnaires ordonns (suite)Oprations principales (suite):

    successeurs(k): successors(k):

    Retourne un itrateur des entres dont la cl est plus grande ou gale k; en ordre croissant

    prdcesseurs(k): predecessors(k):

    Retourne un itrateur des entres dont la cl est plus petite ou gale k; en ordre dcroissant

    closestKeyBefore(k): Retourne la cl (ou la valeur) de lentre ayant la plus grande cl plus petite ou gale kclosestValBefore(k):

    closestKeyAfter(k): Retourne la cl (ou la valeur) de lentre ayant la plus petite cl plus grande ou gale kclosestValAfter(k):

    2Arbres de Recherche: Intro+BinairesIFT2810, A2009, Sylvie HamelUniversit de Montral

  • Arbres binaires de recherche

    Splay treeArbres AVL Arbres rouges-noirs

    Arbres de recherchegnraliss

    Recherche externe

    Arbres (2,4)

    Introduction:

    3Arbres de Recherche: Intro+BinairesIFT2810, A2009, Sylvie HamelUniversit de Montral

  • 5

    Arbres binaires de recherche

    6

    92

    41 8

    Un arbre binaire de recherche est un arbre binaire qui garde en mmoire des entres (cl-valeur) dans ses noeuds internes et qui satisfait la proprit suivante:

    Les noeuds externes ne gardent en mmoire aucune entre

    Un parcours symtrique de larbre visite les cls en ordre croissant

    Arbres de Recherche: Intro+Binaires

    Soient , et trois noeuds tels que est dans lesous-arbre gauche de et dans son sous-arbre droit.Alors, on a

    u v w uv w

    cle(u) < cle(v) cle(w)

    IFT2810, A2009, Sylvie HamelUniversit de Montral

  • 6Arbres de Recherche: Intro+Binaires

    Chercher dans un arbre binaire de recherche6

    92

    41 8

    Lide:

    6 ?

    2 ? 9 ?

    1 ? 4 ? 8 ?

    IFT2810, A2009, Sylvie HamelUniversit de Montral

  • 7Arbres de Recherche: Intro+Binaires

    Chercher dans un arbre binaire de recherchePour chercher un lment de cl k dans un arbre binaire de recherche, on va suivre un chemin descendant en commenant la recherche la racine.Exemple 1: Chercher(4)

    6

    92

    41 8

    6

    Le prochain noeud visit dpend du rsultat de la comparaison de k avec la cl du noeud dans lequel on se trouve.

    Si on trouve un noeud interne de cl k, on retourne la valeur correspondant cette entre de cl k

    Sinon, on retourne NULL

    Exemple 1: Chercher(3)

    4 =

    w6

    92

    41 8

    5w

    Si k nest pas dans larbre lalgorithme chercher(k) se terminera dans une feuille w

    On insre k dans et on change en un noeud interne

    w w

    IFT2810, A2009, Sylvie HamelUniversit de Montral

  • 10Arbres de Recherche: Intro+Binaires

    Insrer dans un arbre binaire de recherche

    Exemple 2: Insrer(5,v)

    Si k est dans larbre lalgorithme chercher(k) se terminera sur un noeud interne v. On appelle rcursivement lalgorithme sur le filsDroit(v),jusqu ce quon arrive un noeud externe w

    5

    7

    9

    8

    2

    51

    6

    7

    2

    5

    =

    5 =

    6

    w

    On insre k dans et on change en un noeud interne

    w w

    53 wOn trouve le noeud interne y qui suit w

    lors dun parcours symtrique de larbre etson fils gauche x

    On enlve lentre dans w et on la remplace par lentre dans y

    On enlve les noeuds y et x

    5

    1

    8

    6 9

    w

    2

    8

    6

    5y

    x

    IFT2810, A2009, Sylvie HamelUniversit de Montral

  • 13Arbres de Recherche: Intro+Binaires

    Performance:

    Considrons un dictionnaire ordonn avec n entres implment laide dun arbre ordonn de hauteur h

    Lespace utilis est en O(n)

    Les oprations dinsertion, de recherche et desuppressions se font en O(h)

    La hauteur h est O(n) dans le pire des cas et O(log n) dans le meilleur cas

    IFT2810, A2009, Sylvie HamelUniversit de Montral