Удалить элемент в дереве в Haskell

Question

Я хочу взять двоичное дерево поиска и элемент, а затем удалить его из дерева (если оно присутствует).

Вот мой код:

data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
  deriving Show

type BSTree a = BinaryTree a

treeDelete :: (Ord a) => (BSTree a) -> a -> (BSTree a)
treeDelete a btree = case btree of
  Null -> Null
  Node Null val Null
     |a==val -> Null
     |otherwise -> Node Null val Null
  Node left val right
         |a==val-> Node left Null right
         |otherwise -> (treeDelete a left) val (treeDelete a right)

Answer 1

Вы можете:

1. Изменить определение структуры данных как

data BinaryTree a = Null | Node (BinaryTree a) (Maybe a) (BinaryTree a)

, что является упрощенным трехблочным кодом, набранным [Bool].

Определить поведение поворота (как в сбалансированном дереве), чтобы заполнить пробел после удаления. Вращение не уникально. Например, для отложенной карты в пакете контейнера удаление сбалансированного дерева определяется как:

data Map k a  = Bin Size k a (Map k a) (Map k a)
              | Tip

type Size     = Int

delete :: Ord k => k -> Map k a -> Map k a
delete = go
  where
    go :: Ord k => k -> Map k a -> Map k a
    go !_ Tip = Tip
    go k t@(Bin _ kx x l r) =
        case compare k kx of
            LT | l' == l -> t
               | otherwise -> balanceR kx x l' r
               where l' = go k l
            GT | r' == r -> t
               | otherwise -> balanceL kx x l r'
               where r' = go k r
            EQ -> glue l r

balanceR, balanceL и glue - вращение для балансировки глубины. в сбалансированном дереве. http://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Map-Lazy.html