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

Question

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

问题是

我必须 return 数字的索引，如果它被找到，否则我 return -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

在索引 1 上找到 5 而找不到 6，所以我 return -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 中创建我的树，然后使用 occurs 函数在树中搜索 bs

所以我的问题是

我怎样才能使树包含列表中的索引？
我的类型是否以正确的方式创建来解决这个问题？

我的 Haskell 级别 = 达到了类型和类章节，在 GH 的剑桥 Haskell 书中，并关注了 youtube 上的 HaskellRank 系列。

Answer 1

您可以使用分而治之的方法构建二叉搜索树，并保留与您的 'occurs' 方法类似的版本：

取有序列表中心的元素为根。如果有关系（列表长度为偶数），请选择您喜欢的任何一个。没关系。
递归解决所选索引左侧所有元素的问题，并将返回的树添加到当前根的左侧 child。如果左边没有元素则在左边添加空引用 child.
递归解决所选索引右侧所有元素的问题，并将返回的树添加为当前根的右侧 child。如果右边没有元素则在右边添加空引用child.

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

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

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

How can I create an indexed binary tree from a sorted list in Haskell?

algorithm

binary-tree

haskell

data-structures

问题是

所以我的问题是