1

我刚刚从“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等搜索呢？

4

4 回答 4

1

搜索多个元素时，一个完全可以接受的解决方案是使用最有效的算法（在您的情况下为 O(log n)）一次搜索一个。但是，单步遍历整个树并汇集所有符合特定条件的元素可能是非常有利的，这实际上取决于您在代码中搜索的位置和频率。如果您只在代码中的某一点进行搜索，那么一次性收集树中的所有元素而不是逐个搜索它们是有意义的。如果您决定选择该解决方案，那么您可以使用其他数据结构，例如列表。

如果您需要检查多个属性，我建议将“id”替换为包含所有不同可能标识符（id、color、...）的元组。然后，您可以解压缩元组并比较您想要的任何标识符。

于 2012-07-13T18:29:51.283 回答
1

不。

一次搜索是 O(log n)。4 次搜索是 (4 log n)。将拾取所有项目的线性搜索是 O(n)。btree 的树结构意味着查找多个数据需要遍历（实际上比列表遍历更糟糕）。

于 2012-07-13T18:35:16.593 回答
1

你可以分享一些工作。请参阅members，它接受一个值列表并输出一个列表，该列表恰好包含树中输入列表的那些值。注意：输入列表的顺序不会保留在输出列表中。

编辑：我实际上不确定您是否可以通过membersover doing获得更好的性能（从理论的角度来看） 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
于 2012-07-13T19:10:35.560 回答
1

假设你的二叉树是平衡的，如果你有一个常数 k 个搜索项，那么总时间为 O(k * log(n)) 的 k 个搜索仍然比单个 O(n) 搜索要好，其中每个字符，您仍然需要进行 k 比较，使其成为 O(k*n)。即使搜索项列表已排序，并且您可以在 O(log(k)) 时间内进行二进制搜索以查看当前项是否匹配，但您仍然处于 O(n * log(k))，即比树差，除非 k 是 Theta(n)。

于 2012-07-13T18:27:01.927 回答