2

我有问题，我无法弄清楚我必须如何决定我的函数indexJ在每一步遍历我的平衡二叉树时必须选择的子树 - JoinList。

这个想法是缓存每个子树的大小（数据元素的数量）。然后可以在每个步骤中使用它来确定所需的索引是在左分支还是右分支。

我有这个代码：

data JoinList m a = Empty
                  | Single m a
                  | Append m (JoinList m a) (JoinList m a)
                  deriving (Eq, Show)

newtype Size = Size Int
  deriving (Eq, Ord, Show, Num)

getSize :: Size -> Int
getSize (Size i) = i

class Sized a where
  size :: a -> Size

instance Sized Size where
  size = id

instance Monoid Size where
  mempty  = Size 0
  mappend = (+)

我写函数：

tag :: Monoid m => JoinList m a -> m
tag Empty = mempty
tag (Single x dt) = x
tag (Append x l_list r_list) = x

(+++) :: Monoid m => JoinList m a -> JoinList m a -> JoinList m a
(+++) jl1 jl2 = Append (mappend (tag jl1) (tag jl2)) jl1 jl2

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty = Nothing
indexJ i jl | i < 0 || (i+1) > (sizeJl jl) = Nothing 

  where sizeJl = getSize . size . tag

indexJ 0 (Single m d) = Just d
indexJ 0 (Append m (Single sz1 dt1) jl2) = Just dt1
indexJ i (Append m jl1 jl2) = if (sizeJl jl1) >= (sizeJl jl2) 
                              then indexJ (i-1) jl1  
                              else indexJ (i-1) jl2 

  where sizeJl = getSize . size . tag

功能tag和(+++)工作良好，但我需要完成indexJ功能，它必须从我的 JoinList 树中返回第 i 个元素，i = [0..n]

我的函数indexJ工作错误=）如果我有空树 - 它是（大小 0）如果我有单个（大小 1）“数据” - 它是（大小 1）但是如果我有追加（大小 2）（单（大小 1 ) 'k') (Single (Size 1) 'l') 我必须选择哪个分支？i-1 = 1 并且我有两个分支，每个分支都有 1 个数据元素。

更新：如果有人需要 JoinList 的树的获取和删除功能，我会这样做：

dropJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
dropJ _ Empty = Empty 
dropJ n jl | n <= 0 = jl
dropJ n jl | n >= (getSize . size $ tag jl) = Empty
dropJ n (Append m jL1 jL2)
  | n == s1 = jL2
  | n < s1 = (dropJ n jL1) +++ jL2
  | otherwise = dropJ (n - s1) jL2
                where s1 = getSize . size $ tag jL1

takeJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
takeJ _ Empty = Empty 
takeJ n jl | n <= 0 = Empty
takeJ n jl | n >= (getSize . size $ tag jl) = jl
takeJ n (Append m jL1 jL2)
  | n == s1 = jL1
  | n < s1 = (takeJ n jL1)
  | otherwise = jL1 +++ takeJ (n - s1) jL2
                where s1 = getSize . size $ tag jL1
4

2 回答 2

6

我想在

Append m joinList1 joinList2

的元素joinList1用于占用第一个索引，然后是 的元素joinList2。

然后，当索引

indexJ i (Append m jL1 jL2)

你必须比较i的大小jL1- 让我们称之为s1。那么 的元素jL1占据索引 0 到s1 - 1， 的元素jL2占据索引从s1到s1 + s2 - 1，因此

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty  = Nothing
indexJ i (Single m d)
    | i == 0    = Just d
    | otherwise = Nothing
indexJ i (Append m jL1 jL2)
    | i < 0     = Nothing
    | i >= getSize (size m) = Nothing     -- optional, more efficient to have it
    | i < s1    = indexJ i jL1
    | otherwise = indexJ (i - s1) jL2
      where
        s1 = getSize . size $ tag jL1

如果索引小于s1，我们在第一个子列表中查找，否则在第二个子列表中查找。

于 2013-05-10T13:32:54.683 回答
1

通常，您会通过数字序列来编码树结构中的位置，而不仅仅是单个数字。例如（假设索引从 0 开始）：

[] -- empty sequence = root of tree
[0,1] -- first follow the first child, then the second child
[0,0,0] -- go 3 levels down in the leftmost branch

这将使索引函数的实现更加简单。

于 2013-05-10T11:51:20.083 回答