3
\$\begingroup\$

I'm after creating an insert function for a 2 4 tree in Haskell. I'm just wondering if this is the best way to implement it (especially when handling the Root4s), or is there a better way. I know it's quite bulky, but I couldn't see another way of handling the roots with 4 branches.

insertRoot :: Ord t => t -> Tree t -> Tree t

insertRoot x Empty = Root2 x Empty Empty

insertRoot x (Root2 y Empty Empty)
          | x <= y = Root3 (x,y) Empty Empty Empty
          | otherwise = Root3 (y,x) Empty Empty Empty

insertRoot x (Root3 (y,z) Empty Empty Empty)
          | x <= y = Root4 (x,y,z) Empty Empty Empty Empty
          | x > y && x <= z = Root4 (y,x,z) Empty Empty Empty Empty
          | otherwise = Root4 (y,z,x) Empty Empty Empty Empty

insertRoot x (Root2 y left right)
          | x <= y =
              case left of (Root4 (i,j,k) tree1 tree2 tree3 tree4) -> if x <= j then Root3 (j,y) (insertRoot x (Root2 i tree1 tree2)) (Root2 k tree3 tree4) right
                                                                           else Root3 (j,y) (Root2 i tree1 tree2) (insertRoot x (Root2 k tree3 tree4)) right
                           _ -> Root2 y (insertRoot x left) right
          | otherwise = 
              case right of (Root4 (i,j,k) tree1 tree2 tree3 tree4) -> if x <= j then Root3 (y,j) left (insertRoot x (Root2 i tree1 tree2)) (Root2 k tree3 tree4)
                                                                            else Root3 (y,j) left (Root2 i tree1 tree2) (insertRoot x (Root2 k tree3 tree4))
                            _ ->  Root2 y left (insertRoot x right)

insertRoot x (Root3 (a,b) left middle right)
          | x <= a = 
              case left of (Root4 (i,j,k) tree1 tree2 tree3 tree4) -> if x <= j then Root4 (j,a,b) (insertRoot x (Root2 i tree1 tree2)) (Root2 k tree3 tree4) middle right
                                                                           else Root4 (j,a,b) (Root2 i tree1 tree2) (insertRoot x (Root2 k tree3 tree4)) middle right
                           _ -> Root3 (a,b) (insertRoot x left) middle right
          | x > a && x <= b = 
              case middle of (Root4 (i,j,k) tree1 tree2 tree3 tree4) -> if x <= j then Root4 (a,j,b) left (insertRoot x (Root2 i tree1 tree2)) (Root2 k tree3 tree4) right
                                                                             else Root4 (a,j,b) left (Root2 i tree1 tree2) (insertRoot x (Root2 k tree3 tree4)) right
                             _ -> Root3 (a,b) left (insertRoot x middle) right
          | otherwise = 
              case right of (Root4 (i,j,k) tree1 tree2 tree3 tree4) -> if x <= j then Root4 (a,b,j) left middle (insertRoot x (Root2 i tree1 tree2)) (Root2 k tree3 tree4)
                                                                            else Root4 (a,b,j) left middle (Root2 i tree1 tree2) (insertRoot x (Root2 k tree3 tree4))
                            _ -> Root3 (a,b) left middle (insertRoot x right)

insertRoot x (Root4 (a,b,c) left mleft mright right)
          | x <= b = Root2 b (insertRoot x (Root2 a left mleft)) (Root2 c mright right)
          |otherwise = Root2 b (Root2 a left mleft) (insertRoot x (Root2 c mright right))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.