data avl t = empty | node t (avl t) (avl t) int deriving (eq, ord, show) insertnode :: (ord a) => -> avl -> avl insertnode x empty = node x empty empty 0 insertnode x (node n left right balancefactor) | x < n = let leftnode = insertnode x left in balancetree (node n leftnode right ((treeheight leftnode) - (treeheight right))) | otherwise = let rightnode = insertnode x right in balancetree (node n left rightnode ((treeheight left) - (treeheight rightnode))) findnode :: avl -> findnode empty = error "findnode empty" findnode (node _ _ _) = findleftnode :: avl -> avl findleftnode empty = error "findleftnode empty" findleftnode (node _ left _ _) = left findrightnode :: avl -> avl findrightnode empty = error "findrightnode empty" findrightnode (node _ _ right _) = right findbalancefactor :: avl -> int findbalancefactor empty = 0 findbalancefactor (node _ _ _ bf) = bf treeheight :: avl -> int treeheight empty = 0 treeheight (node _ left right _) = 1 + (max (treeheight left) (treeheight right)) balancetree :: avl -> avl balancetree empty = empty balancetree (node r empty empty bf) = node r empty empty bf balancetree (node r left right bf) | bf == -2 && rbf == -1 = let rl = (findleftnode right) in (node (findnode right) -- (node r left rl ((treeheight left) - (treeheight rl))) -- "right right" case (findrightnode right) ((1 + (max (treeheight left) (treeheight rl))) - (treeheight (findrightnode right))) ) | bf == -2 && rbf == 1 = let rl = findleftnode right rr = findrightnode right in (node (findnode (rl)) -- (node r left (findleftnode rl) ((treeheight left) - (treeheight (findleftnode rl)))) -- "right left" case (node (findnode right) (findrightnode rl) rr ((treeheight (findrightnode rl)) - (treeheight rr))) ((max (treeheight left) (treeheight (findleftnode rl))) - (max (treeheight (findrightnode rl)) (treeheight rr))) ) | bf == 2 && lbf == 1 = let lr = findrightnode left in (node (findnode left) -- (findleftnode left) -- "left left" case (node r lr right ((treeheight lr) - (treeheight right))) ((treeheight (findleftnode left)) - (1 + (max (treeheight lr) (treeheight right)))) ) | bf == 2 && lbf == -1 = let lr = findrightnode left ll = findleftnode left in (node (findnode lr) -- (node (findnode left) ll (findleftnode lr) ((treeheight ll) - (treeheight (findleftnode lr)))) -- "left right" case (node r (findrightnode lr) right ((treeheight (findrightnode lr)) - (treeheight right))) ((max (treeheight ll) (treeheight (findleftnode lr))) - (max (treeheight(findrightnode lr)) (treeheight right))) ) | otherwise = (node r left right bf) rbf = findbalancefactor right lbf = findbalancefactor left
this current state of implementation of avl tree. normal input usually:
insertnode 4 (node 2 (node 1 empty empty 0) (node 3 empty empty 0) 0)
which results in:
node 2 (node 1 empty empty 0) (node 3 empty (node 4 empty empty 0) (-1)) (-1)
i want have function display inputted tree in neat fashion, example, tree directly above:
2 1 empty empty 3 empty 4 empty empty
does have suggestions how implemented? wish nodes displayed only, , once reaches end of branch prints "empty". i've hit quite brick wall , tried few attempts little success.
edit: hi guys, quick responses. suggestions work, however, implementation of displaying tree without use of packages or libraries. sorry not clarifying this!
what you're looking pretty printer! use “pretty” package on hackage.
import text.prettyprint
your tree pretty simple structure, i'm going define in 1 shot. there many helpful combinators in text.prettyprint
though, check them out! they're easy use in ghci too, when don't understand documentation, give whirl.
prettytree :: show t => avl t -> doc prettytree empty = text "empty" prettytree (node t l r _) = text (show t) $+$ nest 1 (prettytree l) $+$ nest 1 (prettytree r)
doc
has show
instance fine with, or can use more powerful styling functions.
λ let tree = node 2 (node 1 empty empty 0) (node 3 empty (node 4 empty empty 0) (-1)) (-1) λ prettytree (tree :: avl int) 2 1 empty empty 3 empty 4 empty empty
if wanted without external dependencies, crib style sub in own shims combinators.
type doc = [string] text :: string -> doc text = pure indent :: doc -> doc indent = map (' ':) vertical :: doc -> doc -> doc vertical = (++) prettytree :: show t => avl t -> doc prettytree empty = text "empty" prettytree (node t l r _) = vertical (text (show t)) (indent (vertical (prettytree l) (prettytree r))) render :: doc -> string render = concat
Comments
Post a Comment