Questions / réponses

fonction avl_insert

fonction avl_insert

av Ranim Raji -
Antall svar: 1

Bonjour,

Voici ma fonction "avl_insert" avec la fonction "avl_fix":

let avl_fix tree =
    match tree with
        Empty -> Empty
        |Bin (c, Bin (b, Bin(a, t1, t2), t3), t4) ->
            Bin (b, Bin (a, t1, t2), Bin (c, t3,t4) )
        |Bin (a, t1, Bin (b, t2, Bin (c, t3, t4) ) ) ->
            Bin (b, Bin (a, t1, t2), Bin (c, t3,t4) )
        |Bin (c, Bin (a, t1, Bin (b, t2, t3) ), t4) ->
            Bin (b, Bin (a, t1, t2), Bin (c, t3,t4) )
        |Bin (a, t1, Bin (c, Bin (b, t2, t3), t4)) ->
            Bin (b, Bin (a, t1, t2), Bin (c, t3,t4) )
        |_ -> tree

let rec avl_insert tree v =
    match tree with
        Empty -> Bin ((v, 1),Empty, Empty)
        |Bin ((x,m), g, d) when v = x -> Bin ((x,m+1), g, d)
        |Bin ((x,m), g, d) -> if v > x then Bin ((x,m), g, avl_fix (avl_insert d v))
                            else Bin ((x,m), avl_fix (avl_insert g v), d)

L’élément se rajoute bien, mais le réarrangement soit ne se fait pas du tout, soit n'est pas correcte.

Je pense que le problème vient du fait que je n'appelle pas la fonction de réarrangement "avl_fix" au bon moment dans la fonction.

Mais je ne vois pas comment faire ...


Merci d'avance !

Ranim R.



Som svar til Ranim Raji

Re: fonction avl_insert

av Simon Archipoff -

Bonjour,

Je pense que le problème vient du fait qu'il faut ne faire le réarrangement que s'il est nécessaire, autrement dit, dans les motifs de la fonction avl_fix, on devrait retrouver des tests sur la hauteur des sous arbres.

par exemple avec la syntaxe :

 | pattern when condition -> ...

Contrairement aux arbres rouge noir, la condition ne dépend pas seulement de propriétés locales (la couleur des nœuds voisins).

Vous pourrez ensuite si vous le souhaiter optimiser votre code en utilisant la propriété qu'après une insertion dans un AVL, il faut au maximum 1 équilibrage pour retrouver un AVL.

Cordialement,

Simon Archipoff