文章/答案/技术大牛

发布

社区首页 >问答首页 >Haskell -需要将bst的查找el函数改进为d+1复杂度。

问Haskell -需要将bst的查找el函数改进为d+1复杂度。
EN

Stack Overflow用户

提问于 2021-11-23 12:14:44

回答 2查看 78关注 0票数 0

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

naive_find :: (Ord a) => (Tree a) -> a -> Bool
naive_find Empty _ = False
naive_find (Node t1 v t2) x 
    | x == v = True 
    | x  < v = naive_find t1 x 
    | x  > v = naive_find t2 x

这是我当前bst代码的一个片段，当然还有其他功能，但我认为没有必要问这个问题。我需要将上面的2d复杂度降低到d+1，但我是不是总是需要上面的比较来通过搜索树呢？谢谢。感谢你的任何帮助

haskell

functional-programming

binary-search-tree

回答 2

Stack Overflow用户

发布于 2021-11-23 14:13:24

使用compare。它是Data.Ord的一部分

naive_find (Node t1 v t2) x = case compare v x of
    LT -> naive_find t1 x
    EQ -> True
    GT -> naive_find t2 x

票数 3

Stack Overflow用户

发布于 2021-11-23 17:20:52

您不需要>比较，因为那时您已经知道它会成功，所以您可以只使用otherwise

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

naive_find :: (Ord a) => Tree a -> a -> Bool
naive_find Empty _ = False
naive_find (Node t1 v t2) x 
    | x == v    = True 
    | x  < v    = naive_find t1 x 
    | otherwise = naive_find t2 x

票数 -1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/70080736

复制

相似问题

问Haskell -需要将bst的查找el函数改进为d+1复杂度。
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Haskell -需要将bst的查找el函数改进为d+1复杂度。EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Haskell -需要将bst的查找el函数改进为d+1复杂度。
EN