你如何在 BST 中 return 包含两个节点的最小子树？

Question

我在Haskell中定义了一个BST:

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

我应该如何 return 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

Answer 1

列举一下吧，没有那么多：

两个值都必须在左子树中找到，然后 return 来自那个的递归结果
一个（或两个）值与当前值匹配，然后尝试找到另一个，如果找到 return 当前节点
必须在左子树中找到较小的值，在右子树中必须找到较大的值，然后尝试找到它们，如果都找到return当前节点
两个值都必须在右子树中找到，然后 return 来自那个的递归结果

为了区分这些情况，你应该只比较a、x和y，而不是使用findElem，就像你区分这三种情况一样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）

，您可能会简化

你如何在 BST 中 return 包含两个节点的最小子树？

How do you return the smallest sub-tree which contains two nodes whose keys are given, in a BST?

haskell

functional-programming

binary-search-tree

subtree