algorithm - 如何从 Haskell 中的排序列表创建索引二叉树？

Question

我正在尝试从排序列表中创建一棵树，以便稍后可以搜索它。

问题是

如果找到数字，我必须返回该数字的索引，否则我返回-1，所以我创建了这个函数。

data Tree e i = Leaf e i | Node (Tree e i) e i (Tree e i)
    

occurs :: Int -> Tree Int Int -> Int 
occurs x (Leaf y i)     | x == y    = i 
                        | otherwise = -1
occurs x (Node l y i r) | x == y    = i 
                        | x < y     = occurs x l 
                        | otherwise = occurs x r 

我的输入以格式(作为字符串)发送

3       # The length of as
1 5 7   # as
2       # The length of bs
5 6     # bs

我收到 2 个列表 as 和 bs as 将是树，bs 是我想检查它们是否存在于树中(以及位置)的数字

预期输出是:

1
-1

其中 5 在索引 1 上找到，但未找到 6，因此我返回 -1

所以我正在解析输入:

parse :: [Int] -> ([Int], [Int])
parse (n: xs) = (take n xs, tail $ drop n xs) 

solve :: [Int] -> [Int]
solve xs = func as bs
    where (as, bs) = parse xs

main ::IO ()
main = interact $ unlines . map show . solve . map read . words

然后我需要调用一个函数 func ，它将从列表 as 创建我的树，然后使用 occurrs 函数进行搜索bs

中每个元素的树

所以我的问题是

• 如何创建树以使其包含列表中的索引？
• 我的类型是否以正确的方式创建来解决这个问题？

我的 Haskell 水平 = 达到 GH 的 Cambridge Haskell 书中的类型和类章节，并关注 YouTube 上的 HaskellRank 系列。

Answer 1

您可以使用分而治之的方法构建二叉搜索树，并保留“发生”方法的类似版本:

1. 将有序列表中心的元素作为根。如果有平局(列表的长度为偶数)，请选择您喜欢的任何一个。没关系。
2. 递归地解决所选索引左侧的所有元素的问题，并将返回的树添加为当前根的左子节点。如果左侧没有元素，则在左侧子元素上添加空引用。
3. 递归地解决所选索引右侧的所有元素的问题，并将返回的树添加为当前根的右子节点。如果右侧没有元素，则在右侧子元素上添加空引用。

这种分而治之的方法保证了树的 O(log n) 高度，其中 n 是有序列表的长度。树的构造是 O(n) 并且是正确的二叉搜索树，因为随着列表的排序，我们知道左侧的所有元素都低于或等于当前的元素，而右侧的所有元素都大于或等于当前的元素。等于当前值。

类型创建是有缺陷的，因为树的构造依赖于叶节点和不具有空左子节点和右子节点的节点，这在几乎所有输入中都是不正确的。你可以尝试构建一棵有 2 个节点的树来看看我的意思。其他与 Haskell 设计不一样的地方是使用 -1 作为不存在的解决方案，因为 Haskell 有一个为这些情况创建的 Maybe 集成类型，但如果你需要这样做，那是你的最终选择。