我刚刚从"Learn You a Haskell"一书中读到关于二进制搜索树的内容，我想知道使用该树搜索多个元素是否有效？例如，假设我有一堆对象，其中每个对象都有一些索引，并且
5
/
3 7
/ /
1 4 6 8
如果我需要通过索引8找到一个元素，我只需要执行三个步骤5 -> 7 -> 8，而不是在整个列表上迭代直到结束。但是，如果我需要找到几个对象，比如1、4、6、8，该怎么办？似乎我需要对每个元素5-> 3 -> 1、5 -> 3 -> 4、5 -> 7 -> 6和5 -> 7 -> 8重复相同的操作。
所以我的问题是：使用二进制搜索树来查找多个元素仍然有意义吗？这会比检查每个元素的条件（在最坏的情况下只会导致O（n））更好吗？
此外，如果我需要检查多个属性，最好使用哪种数据结构。例如，在上面的例子中，我只查找id属性，但如果我还需要按name或color等进行搜索，该怎么办？
您可以共享一些工作。请参阅members，它接收一个值列表，并输出一个恰好包含树中输入列表中那些值的列表。注意：输入列表的顺序不在输出列表中。
编辑：实际上，我不确定使用members是否能比使用map member获得更好的性能（从理论角度来看）。我认为如果输入列表是排序的，那么通过将列表拆分为三个（lss、eqs、gts）可以很容易地完成。
data BinTree a
= Branch (BinTree a) a (BinTree a)
| Leaf
deriving (Show, Eq, Ord)
empty :: BinTree a
empty = Leaf
singleton :: a -> BinTree a
singleton x = Branch Leaf x Leaf
add :: (Ord a) => a -> BinTree a -> BinTree a
add x Leaf = singleton x
add x tree@(Branch left y right) = case compare x y of
EQ -> tree
LT -> Branch (add x left) y right
GT -> Branch left y (add x right)
member :: (Ord a) => a -> BinTree a -> Bool
member x Leaf = False
member x (Branch left y right) = case compare x y of
EQ -> True
LT -> member x left
GT -> member x right
members :: (Ord a) => [a] -> BinTree a -> [a]
members xs Leaf = []
members xs (Branch left y right) = eqs ++ members lts left ++ members gts right
where
comps = map (x -> (compare x y, x)) xs
grab ordering = map snd . filter ((ordering ==) . fst)
eqs = grab EQ comps
lts = grab LT comps
gts = grab GT comps
在搜索多个元素时，一个非常可接受的解决方案是使用最有效的算法（在您的情况下是O（logn））一次搜索一个元素。然而，遍历整个树并汇集所有符合特定条件的元素可能非常有利，这实际上取决于您在代码中搜索的位置和频率。如果只在代码中的一个点进行搜索，那么一次性收集树中的所有元素是有意义的，而不是逐个搜索。如果您决定选择该解决方案，那么您可以使用其他数据结构，如列表。
如果你需要检查多个属性，我建议用一个包含所有不同可能标识符（id、color…）的元组来替换"id"。然后你可以解压缩元组并比较你想要的任何标识符。
假设你的二叉树是平衡的，如果你有恒定数量的k个搜索项，那么总时间为O（k*log（n））的k次搜索仍然比单个O（n）搜索要好，在每个字符上，你仍然需要进行k次比较，使其成为O（k*n）。即使搜索项目列表已排序，并且您可以在O（log（k））时间内进行二进制搜索以查看您的当前项目是否匹配，您仍然处于O（n*log（k）），这比树更糟糕，除非k是Theta（n）。
否。
单个搜索为O（logn）。4个搜索是（4logn）。线性搜索是O（n），它将拾取所有项目。btree的树结构意味着要找到多个数据需要遍历（实际上比列表遍历更糟糕）。