CODEWITHSUNDEEP
haskellrecursionbinary-tree
BryceTheGrand
BryceTheGrand

Reputation: 663

How to delete an element from a Leafy Binary Tree (Haskell)

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?

Upvotes: 0

Views: 662

Answers (2)

amalloy
amalloy

Reputation: 91837

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

Upvotes: 3

HTNW
HTNW

Reputation: 29158

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

Upvotes: 2

Related Questions