[Haskell-beginners] Tying the knot with binary trees
Michael Schober
Micha-Schober at web.de
Sat Apr 14 14:04:37 CEST 2012
Hi again,
thanks for your comments. I've tried your code, but unfortunately that
doesn't seem to do the trick.
The problem is that Leaves do not know their
>> parents, so one solution is to change your data type to this:
>>
>> data BinTree a =
>> Leaf { lfather :: BinTree a } |
>> Node { value :: a
>> , left :: BinTree a
>> , right :: BinTree a
>> , father :: BinTree a
>> }
>>
>> then insert would become
>> insert v' (Leaf parent) = let result = Node v' (Leaf result) (Leaf
>> result) parent
>> insert v' n = ...
I was reluctant to this version at first, but I gave it a try. You can
find it attached in the alt-linked-tree.hs (I hope it's okay to attach
code in files, but the code grew beyond snippetery and this way it's
probably more comfortable to test it).
Unfortunately, this doesn't work as well. The actual insert code in this
version looks like this:
-- inserts an element into a binary search tree
insert :: Ord a => a -> BinTree a -> BinTree a
insert v' (Leaf parent) =
let result = Node v' (Leaf result) (Leaf result) parent
in result
insert v' n@(Node v l r p) =
case compare v' v of
EQ -> n
LT -> let inserted = insert v' l
result = Node v inserted r p
in result
GT -> let inserted = insert v' r
result = Node v l inserted p
in result
I think the problem here is, that I don't modify the parent, but I
cannot seem to wrap my head around it today.
>> Otherwise you'll have to pass the parent down along the tree as you
>> modify it as such:
>>
>> insert v' Leaf = mkRoot v'
>> insert v' n@(Node v l r f) = case compare v v' of
>> EQ -> n
>> GT -> (Node v (insert' v' l n) r f)
>> LT -> (Node v l (insert' v' r n) f)
>>
>> insert' v' Leaf parent = Node v' Leaf Leaf parent
>> insert' v' n@(Node v l r f) parent = case compare v v' of
>> EQ -> n
>> GT -> let result = Node v (insert' v' l result) r parent in result
>> LT -> let result = Node v l (insert' v' r result) parent in result
>>
>> You require a base case because the first node has no parent to insert with.
This looks pretty much like my code from the beginning, but it doesn't
work as well. However, in the meantime I played around with some
complexer trees to come across a deficit pattern, but it's really
strange. It seems to me as if random subtrees are missing. Sometimes
there are siblings as expected, sometimes even children of these
siblings, but there never seems to be a working tree.
I have an intuition that it could be the case that I have to modify the
parent as well in the recursive case, but I don't know how yet.
Anyway, I'll let it go for the weekend and return to doubly linked lists
for now. Maybe implementing more features for those will help me get a
better intuition for these kind of problems.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: alt-linked-tree.hs
Type: text/x-haskell
Size: 3101 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120414/dfbe8d78/attachment.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linked-tree.hs
Type: text/x-haskell
Size: 4526 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120414/dfbe8d78/attachment-0001.hs>
More information about the Beginners
mailing list