Обновление дерева на основе индекса Haskell - PullRequest
Новая
       23

Обновление дерева на основе индекса Haskell

0 голосов
/ 13 октября 2018

У меня есть деревья вида: 

data Tree a = Leaf | Node (Tree a) a (Tree a)

Я создал функцию для поиска значения узла в дереве по порядку обхода слева направо. 

getElem :: Tree a -> Int -> Maybe a
getElem Leaf _ = Nothing
getElem (Node l x r) n
    | s == n     = Just x
    | n < s      = getElem l n 
    | otherwise  = getElem r (n - s - 1)
  where
    s = size l

Теперь я хочу написать метод, чтобы иметь возможность обновлять дерево.Он должен иметь возможность принимать дерево, индекс и значение и обновлять узел с этим индексом значением.Пока у меня есть: 

update :: Tree a -> Int -> a -> Tree a
update Leaf _ _ = Leaf
update (Node l x r) index c
    | s == index      = (Node l c r)
    | index < s       = update l index c
    | otherwise       = update r (index - s - 1) c
  where
    s = size l

Эта функция может быть добавлена, но она, очевидно, возвращает только сам добавленный узел.Я хочу иметь возможность вернуть все дерево после «обновления» с новым узлом или вернуть дерево как есть, если индекс выходит за пределы.

Может кто-нибудь подсказать мне, как поступить с этим?

Редактировать 1:

Хорошо, я понимаю, что я в основном отбрасываю остаток моего дерева, когда возвращаюсь сюда.Итак: 

update :: Tree a -> Int -> a -> Tree a
update Leaf _ _ = Leaf
update (Node l x r) index c
    | s == index      = (Node l c r)
    | index < s       = update (Node l2 x r) index c
    | otherwise       = update (Node l x r2) (index - s - 1) c
  where
    s = size l
    l2 = l
    r2 = r

Редактировать 2 (Глупый я!): 

update :: Tree a -> Int -> a -> Tree a
update Leaf _ _ = Leaf
update (Node l x r) index c
    | s == index      = (Node l c r)
    | index < s       = (Node (upd l index c) x r)
    | otherwise       = (Node l x (upd r (index - s - 1) c)) 
  where
    s = size l

Мне понадобилось немного времени, чтобы обернуть голову вокруг него.Спасибо за комментарии!

1 Ответ

0 голосов
/ 13 октября 2018

Поскольку в Haskell все данные неизменны , вы не можете "обновить" дерево, вы создаете новое дерево.Это дерево, однако, может иметь ссылки на поддеревья старого дерева.Таким образом, вы не можете построить новое дерево полностью .

Вам удалось создать «обновленный» узел, поэтому теперь единственное, чего не хватает, - это использовать «обновленный»поддерево в новом дереве.В этом дереве вы можете использовать «старое» значение вместе с other поддеревом для создания нового, например: 

update :: Tree a -> Int -> a -> Tree a
update Leaf _ _ = Leaf
update (Node l x r) index c
    | s == index      = Node l c r
    | index < s       = <b>Node</b> (update l index c) <b>x r</b>
    | otherwise       = <b>Node l x (</b>update r (index - s - 1) c<b>)</b>
  where s = size l

Возможно, вам также потребуется изменить LeafВ случае, если вы «считаете» лист как узел.

Деревья с индексами встречаются не очень часто.Кроме того, для повышения производительности лучше отслеживать количество элементов в левом дочернем элементе (или в обоих), поскольку тогда мы можем просто выбрать левый или правый дочерний элемент, не считая дочерние элементы.Отслеживая номер, для дерева complete , обновление дерева является операцией O (log n) , а не O (n) ..

...