如何在BST中返回最小的子树，该子树包含两个给出密钥的节点？

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

我应该如何返回包含BST的两个给定键的节点的最小子树？

Answer 1

仅列举案例，没有那么多：

• 两个值都必须在左子树中找到，然后从中返回递归结果
• 一个（或两个）值与当前值匹配，然后尝试查找另一个，如果找到，则返回当前节点
• 必须在左侧子树中找到较小的值，而必须在右侧子树中找到较大的值，然后尝试找到它们，如果都找到，则返回当前节点
• 两个值都必须在正确的子树中找到，然后从中返回递归结果

[区分这些情况，您只应比较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，则可以简化）>