www.jammni.de

Gepostet:
08.03.2010 16:23

AVL Baum Höhe in Knoten speichern

Hallo ich hab in Haskell noch nicht so viel Erfahrung und komme nicht weiter. Wenn man ein neues Element in einen AVL Baum speichert soll die Höhe der jeweiligen Knoten in den Knoten selber gespeichert werden, damit man beim nächsten Durchlauf nicht alle Höhen wieder von vorn abfragen muss. Hab mir gedacht das ich das als Tupel schreibe. Bekomme leider folgende Fehlermeldung: ERROR file:.\AVLTree.hs:34 - Type error in application
*** Expression : i < v
*** Term : i
*** Type : a
*** Does not match : (Integer,a)
*** Because : unification would give infinite type

Wäre dankbar für Vorschlage, Hinweise.



module AVLTree
where

data (Ord a,Show a) => AVLTree hoehe a = EmptyAVL
                                 | NodeAVL (Integer,a) (AVLTree hoehe a) (AVLTree hoehe a)
    deriving (Show, Eq)
addAVL :: (Ord a, Show a) => a -> AVLTree hoehe a -> AVLTree hoehe a
emptyAVL = EmptyAVL

rotateLeft,rotateRight :: (Ord a,Show a) => AVLTree hoehe a -> AVLTree hoehe a
rotateLeft EmptyAVL   = EmptyAVL
rotateLeft (NodeAVL v (NodeAVL lv lflf lfrt) rt)  
    = NodeAVL lv lflf (NodeAVL v lfrt rt)

rotateRight EmptyAVL  = EmptyAVL
rotateRight (NodeAVL v lf (NodeAVL rv rtlf rtrt)) 
    = NodeAVL rv (NodeAVL v lf rtlf) rtrt

dRotateLeftRight, dRotateRightLeft :: (Ord a,Show a) => AVLTree hoehe a -> AVLTree hoehe a
dRotateRightLeft (NodeAVL v lf
                            (NodeAVL rv (NodeAVL rtlv rtlflf rtlfrt) rtrt))
    = NodeAVL rtlv (NodeAVL v lf rtlflf)
                   (NodeAVL rv rtlfrt rtrt)
dRotateLeftRight (NodeAVL v (NodeAVL lv lflf
                                        (NodeAVL lfrv lfrtlf lfrtrt))rt)
    = NodeAVL lfrv (NodeAVL lv lflf lfrtlf)
                   (NodeAVL v lfrtrt rt)
                   
height EmptyAVL  = 0
height (NodeAVL _ lf rt) = 1 + max (height lf) (height rt)

addAVL i EmptyAVL = NodeAVL i EmptyAVL EmptyAVL
addAVL i (NodeAVL v lf rt) 
   | i < v     = let
                    newlf@(NodeAVL newlfv _ _)  = addAVL i lf 
                  in	
                   if ((height newlf - height rt) == 2)
                   then if i < newlfv
                        then rotateLeft (NodeAVL (height,v) newlf rt)
                        else dRotateLeftRight (NodeAVL (height,v) newlf rt)
                   else (NodeAVL height (v,newlf) rt)
    | i> v     = let
                    newrt@(NodeAVL (height,newrtv) _ _)  = addAVL i rt
                  in
                   if ((height newrt - height lf) == 2)
                   then if i > newrtv
                        then rotateRight (NodeAVL (height,v) lf newrt)
                        else dRotateRightLeft (NodeAVL (height,v) lf newrt)
                   else (NodeAVL (height,v) lf newrt)
    | otherwise = NodeAVL (height,v) lf rt

Zum Seitenanfang

Siracusa

Gepostet:
08.03.2010 18:16

Hallo,

das Problem ist genau das, was die Fehlermeldung sagt ;-) Bei addAVL i (NodeAVL v lf rt) ist das i nach der Typsignatur von addAVL der gleiche Typ, wie die Werte, die im Baum gespeichert sind. Und v ist vom Typ (Integer, a), d.h. du kannst nicht i mit v vergleichen. Eine mögliche Lösung, wäre das Muster zu spezifizieren:
addAVL i (NodeAVL (h,v) lf rt)
wobei v dann der Wert und h die Höhe ist.

Übrigens ist mir aufgefallen, dass du height auf der rechten Seite mal als Funktion und mal als Integer verwendest, das wäre dann auch ein Fehler.

Viele Grüße,

Siracusa

Zum Seitenanfang

ayla

Gepostet:
09.03.2010 11:05

Danke für die Antwort

Zum Seitenanfang

Haskell-Forum