平衡二叉樹的索引函數

Question

我有問題，我不知道如何決定我的函數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功能，它必須返回從第i個元素我的JoinList樹，i = [0..n]

我的功能indexJ working wrong =） 如果我有空樹 - 它是（大小0） 如果我有單一（大小1）「數據」 - 它的（大小1） 但如果我有附加（大小2）（單（大小1）'k '）（單（1）''''）我必須選擇哪個分支？ i-1 = 1，我有兩個分支，每個分支有1個數據元素。

UPDATE：如果有人需要採取抗摔功能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 

Answer 1

我想在

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較小，我們期待在第一子列表，否則在第二。

Answer 2

通常你會用數字的序列，而不僅僅是一個單一的編碼在樹形結構中的位置數。例如（假設索引從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 

這會使索引函數的實現更加簡單。