Как вы возвращаете наименьшее поддерево, которое содержит два узла, ключи которых даны, в BST? - PullRequest
Новая
       92

Как вы возвращаете наименьшее поддерево, которое содержит два узла, ключи которых даны, в BST?

2 голосов
/ 11 апреля 2020

Я определил BST в Haskell: 

data BST a = BST a (BST a) (BST a) | BSTNil deriving Show

и некоторых подобных операциях: 

findElem :: (Ord a, Eq a) => BST a -> a -> Maybe a
findElem BSTNil _ = Nothing
findElem (BST a left right) x
        | x == a = Just x
        | x < a = findElem left x
        | x > a = findElem right x

inorder :: BST a -> [a]
inorder BSTNil = []
inorder (BST a left right) = inorder left ++ [a] ++ inorder right

Как мне вернуть наименьшее поддерево, содержащее два узлы, ключи которых даны, из BST?

Вот что я получил до сих пор: 

subTree :: (Ord a, Eq a) => BST a -> a -> a -> Maybe (BST a)
subTree BSTNil _ _ = Nothing
subTree (BST a left right) x y 
     | findElem (BST a left right) x == Nothing = Nothing
     | findElem (BST a left right) y == Nothing = Nothing
     | findElem left x /= Nothing && findElem left y /= Nothing = subTree 
                                                                  left x y
     | findElem right x /= Nothing && findElem right y /= Nothing = subTree 
                                                                    right x y

1 Ответ

3 голосов
/ 11 апреля 2020

Просто перечислите случаи, их не так много:

  • оба значения должны быть найдены в левом поддереве, а затем верните рекурсивный результат из этого
  • one (или обоих ) значения соответствуют текущему значению, затем попытайтесь найти другое, и если найдено, верните текущий узел
  • , меньшее значение должно быть найдено в левом поддереве, а большее значение должно быть найдено в правом поддереве, затем попробуйте чтобы найти их и, если оба найдены, вернуть текущий узел
  • , оба значения должны быть найдены в правом поддереве, а затем вернуть рекурсивный результат из этого

Для различения guish в этих случаях вы должны сравнивать только a, x и y, а не использовать findElem, как вы это делали для различения guish трех случаев в функции findElem. (Вы можете позвонить findElem, хотя, если вам нужно найти единственный элемент в поддереве). Так что я бы сделал 

subTree :: (Ord a, Eq a) => BST a -> a -> a -> Maybe (BST a)
subTree BSTNil _ _ = Nothing
subTree t@(BST a left right) x y
     | x < a && y < a = subTree left x y
     | x == a         = findElem t y *> Just t
     | y == a         = findElem t x *> Just t
     | x > a && y > a = subTree right x y
     | otherwise      = findElem t y *> findElem t x *> Just t -- x < a < y or y < a < x

(Как упомянул @Will Ness, вы могли бы упростить, если знаете - или принудительно - что x <= y)

...