- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
data TTree k v =
TNode {
_key :: !k
, _val :: !(Maybe v)
, _eq :: !(TTree k v)
, _left :: !(TTree k v)
, _right :: !(TTree k v)
, _height :: !Int
}
| TTNil
deriving (Show, Generic)
instance (Binary k, Binary v) => Binary (TTree k v)
insertWith' :: (Ord k)
=> (v -> v -> v) -- ^ Conflict resolution function
-> [k] -- ^ Key
-> Int -- ^ Length of the key
-> v -- ^ Value
-> TTree k v -- ^ Tree
-> TTree k v
insertWith' f [email protected](k:kt) h v t =
case t of
TTNil ->
insertWith' f k1 h v $ TNode {
_key = k
, _eq = TTNil
, _left = TTNil
, _right = TTNil
, _val = Nothing
, _height = h
}
[email protected]{_key=k0, _height=h0, _val=v0, _eq=eq0, _left=left0, _right=right0} ->
case compare k0 k of
EQ | null kt ->
node {
_val = Just $ maybe v (flip f $ v) v0
}
| True ->
node {
_eq = insertWith' f kt (h-1) v eq0
, _height = max h h0
}
GT ->
node {
_left = insertWith' f k1 h v left0
, _height = max h h0
}
LT ->
node {
_right = insertWith' f k1 h v right0
, _height = max h h0
}
{-# SPECIALIZE insertWith' :: (v -> v -> v)
-> [Char]
-> Int
-> v
-> TTree Char v
-> TTree Char v
#-}
а почему бы не использовать несбалансированное тернанрое дерево для индекса
вроде ничего стра
Out of memory: Kill process 2987 (govno) score 265 or sacrifice child