0

So, this tree is NOT a Binary Search Tree. It is in no particular order, and is just in this order for quick access to specific indices (nth element), rather than whether an element exists or not.

The form of the Tree is like so:

data Tree a = Leaf a | Node Int (Tree a) (Tree a) deriving Show

For this specific tree, the "Int" from the Node constructor is the number of elements underneath that node (or number of leaves).

Using this structure, I copied parts of the Tree functions available in a lecture I found online (that I slightly modified when trying to understand):

buildTree :: [a] -> Tree a
buildTree = growLevel . map Leaf
    where
    growLevel [node]   = node
    growLevel l        = growLevel $ inner l

    inner []           = []
    inner (e1:e2:rest) = e1 <> e2 : inner rest
    inner xs = xs

    join l@(Leaf _)       r@(Leaf _)       = Node 2 l r
    join l@(Node ct _ _)  r@(Leaf _)       = Node (ct+1) l r
    join l@(Leaf _)       r@(Node ct _ _)  = Node (ct+1) l r
    join l@(Node ctl _ _) r@(Node ctr _ _) = Node (ctl+ctr) l r

And I was able to create some basic functions for moving through a tree. I made one that finds the nth element and returns it. I also made a Path datatype and implemented a function to return the path (in left and rights) to a specific index, and one function that can travel through a path and return that Node/Leaf.

Now, what I would like to make is a delete function. The problem here is with the fact that the tree is "leafy", or at least that is what is causing me difficulties.

If I end up with a Leaf at the deletion path, there is no "Null" or equivalent item to replace it with. Additionally, if I try to stop at the last path (like [L]), and check if that's a Node or not, then if it's a leaf replace the whole node with the opposite side etc., I run into the problem of changing the whole tree to reflect that change, not just return the end of the deletion, and change all the numbers from the tree to reflect the change in leaves.

I would like order to be preserved when deleting an item, like if you were to use a list as a simpler example:

del 4 [1, 2, 3, 4, 5, 6, 7] = [1, 2, 3, 4, 6, 7]

If there is a simpler way to structure the Tree (that still can contain duplicate elements and preserve order) what is it?

Is there some way to delete an element using this method?

Improve this question
4
  • Side note: would it not be better to write join/(<>) as just l <> r = Node (count l + count r) l r, extracting count :: Tree a -> Int as its own function? I think you'd also want to add a bang to Node: Node !Int (Tree a) (Tree a). Commented Aug 19, 2019 at 19:22
  • @HTNW If I implemented a count function, wouldn't the counting of the whole node every time I change something defeat the purpose of the speed of a Tree? Also, I don't quite understand bang patterns completely, but from what I do understand, that does seem like a good idea. Commented Aug 19, 2019 at 19:32
  • 1
    As in count (Leaf _) = 1; count (Node n _ _) = n. count makes the point of the tree more clear: a Tree is a normal binary tree, except the count function is more efficient than normal. Commented Aug 19, 2019 at 19:33
  • empty = Node 0 empty empty. Commented Aug 21, 2019 at 19:13

2 Answers 2

Reset to default
3

If I ... replace the whole node with the opposite side ... I run into the problem of changing the whole tree to reflect that change, not just return the end of the deletion, and change all the numbers from the tree to reflect the change in leaves.

Well, not the whole tree - just the path from the deleted node back to the root. And isn't that exactly what you want?

I guess the first step would be, define what you mean by "delete". Should the indexes of undeleted nodes remain the same after deletion, or should nodes after the deleted node have their indexes reduced by one? That is, given:

tree :: [a] -> Tree a
-- get and del both 0-indexed, as in your example
get :: Int -> Tree a -> Maybe a
del :: Int -> Tree a -> Tree a

then of course 

get 5 $ tree [1..7]

should yield Just 6. But what about

get 5 . del 4 $ tree [1..7]

? If you want this to still yield Just 6 (there is a "blank" spot in your tree where 5 used to be), that is a rather tricky concept, I think. You can put Nothings in to make space, if you define Leaf (Maybe a) instead of Leaf a, but this only papers over the problem: inserts will still shift indices around.

I think it is much simpler for this to yield Just 7 instead, making del 4 $ tree [1..7] the same as tree [1,2,3,4,6,7]. If this is your goal, then you simply must renumber all the nodes on the path from the deleted node back to the root: there is no getting around the fact that they all have one fewer leaf descendant now. But the other nodes in the tree can remain untouched.

For reference, one possible implementation of del:

count :: Tree a -> Int
count (Leaf _) = 1
count (Node s _ _) = s

del :: Int -> Tree a -> Maybe (Tree a)
del n t | n < 0 || n >= size || size <= 1 = Nothing
        | otherwise = go n t
  where size = count t
        go n (Leaf _) = Nothing
        go n (Node s l r) | n < size = reparent flip l r
                          | otherwise = reparent id r l
          where reparent k c o = pure . maybe o (k (Node (s - 1)) o) $ go n c
                size = count l
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

If I end up with a Leaf at the deletion path, there is no "Null" or equivalent item to replace it with.

Well, make one :). This is what Maybe is for: when you delete an element from a Tree, you cannot expect to get a Tree back, because Tree is defined to be nonempty. You need to explicitly add the possibility of emptiness by wrapping in Maybe. Deletion may also fail with an out-of-bounds error, which I represent with Either Int and incorporate into the logic.

delete :: Int -> Tree a -> Either Int (Maybe (Tree a))
delete i t | i >= max = Left (i - max) where max = count t
delete _ (Leaf _) = Right Nothing
delete i (Node n l r) = case delete i l of
  Left i' -> Just <$> maybe l (Node (n - 1) l) <$> delete i' r
  Right l' -> Right $ Just $ maybe r (\x -> Node (n - 1) x r) l'

Where count is as I recommended in the comments:

count :: Tree a -> Int
count (Leaf _) = 1
count (Node n _ _) = n
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.