1

「LearnYouaHaskell」の本から二分探索木について読んだばかりですが、この木を使用して複数の要素を検索することが効果的かどうか疑問に思っています。たとえば、すべてのオブジェクトにインデックスが付いているオブジェクトがたくさんあるとします。

        5
      /   \
     3     7
    / \   / \
   1   4 6   8

インデックス8で要素を見つける必要がある場合は、5 -> 7 -> 8リスト全体を最後まで繰り返すのではなく、3つの手順を実行するだけで済みます。しかし、1、4、6、8など、いくつかのオブジェクトを見つける必要がある場合はどうなりますか？要素ごとに同じアクションを繰り返す必要があるようです5-> 3 -> 1 5 -> 3 -> 4、、。5 -> 7 -> 65 -> 7 -> 8

だから私の質問は：複数の要素を見つけるために二分探索木を使用することはまだ意味がありますか？各要素の状態をチェックするよりも良いでしょうか（最悪の場合、O（n）のみになります）。

また、複数の属性をチェックする必要がある場合は、どのようなデータ構造を使用するのが適していますか。たとえば、上記の例では、id属性のみを検索していましたが、、、などで検索する必要がある場合はどうnameなりcolorますか？

4

4 に答える 4

1

作業の一部を共有できます。を参照membersしてください。これは、値のリストを受け取り、ツリーにある入力リストの値のリストを正確に出力します。注：入力リストの順序は、出力リストでは保持されません。

members編集：やり過ぎで（理論的な観点から）より良いパフォーマンスを得ることができるかどうかは実際にはわかりませんmap member。入力リストを並べ替えれば、リストを3つ（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

二分木がバランスが取れていると仮定すると、検索アイテムの数が一定である場合、合計時間が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 に答える
1

複数の要素を検索する場合の非常に受け入れられる解決策は、最も効率的なアルゴリズム（この場合はO（log n））を使用して一度に1つずつ検索することです。ただし、ツリー全体をステップスルーし、特定の条件に一致するすべての要素をプールすることは非常に有利な場合があります。これは、コード内を検索する場所と頻度によって異なります。コード内の1つのポイントでのみ検索する場合は、ツリー内のすべての要素を1つずつ検索するのではなく、1回のショットで収集するのが理にかなっています。そのソリューションを選択する場合は、リストなどの他のデータ構造を使用することができます。

複数の属性をチェックする必要がある場合は、「id」を、考えられるすべての異なる識別子（id、color、...）を含むタプルに置き換えることをお勧めします。次に、タプルを解凍して、必要なIDを比較できます。

于 2012-07-13T18:29:51.283 に答える
1

いいえ。

単一の検索はO（log n）です。4回の検索は（4 log n）です。すべてのアイテムを取得する線形検索はO（n）です。btreeのツリー構造は、複数のデータムを見つけるにはウォークが必要であることを意味します（これは実際にはリストウォークよりも悪いです）。

于 2012-07-13T18:35:16.593 に答える