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.