Я пытаюсь реализовать двоичное дерево поиска (или набор), используя фиксированные точки функторов. Я определил свою фиксированную точку следующим образом:
newtype Fix f = In (f (Fix f))
out :: Fix f -> f (Fix f)
out (In f) = f
-- Catamorphism
type Algebra f a = f a -> a
cata :: (Functor f) => Algebra f a -> Fix f -> a
cata f = f . fmap (cata f) . out
Чтобы сделать бинарное дерево, я использую красно-черное дерево вот так:
data NodeColor = Red | Black deriving (Eq, Show)
data RedBlackTreeF a r = EmptyRedBlackTreeF | RedBlackTreeNodeF NodeColor r a r deriving (Eq, Show)
instance Functor (RedBlackTreeF a) where
fmap _ EmptyRedBlackTreeF = EmptyRedBlackTreeF
fmap f (RedBlackTreeNodeF color r1 a r2) =
RedBlackTreeNodeF color (f r1) a (f r2)
type RedBlackTreeF' a = Fix (RedBlackTreeF a)
Традиционным преимуществом бинарного дерева является возможность сократить время поиска, выбрав, следует ли искать дальше в левом или правом поддереве, например так (в псевдокоде):
fun member (x, E) = false
| member (x, T (_, a, y, b)) =
if x < y then member (x, a)
else if x > y then member (x, b)
else true
Функция member
пойдет влево, если искомый элемент меньше текущего элемента, и вправо, если верно обратное. Таким образом, время поиска сокращается до O(logn)
.
Однако в рекурсивной схеме алгебра рекурсивно применяется ко всей структуре данных. Я написал member
алгебру здесь:
memberPAlg :: Ord a => a -> RedBlackTreeF a Bool -> Bool
memberPAlg _ EmptyRedBlackTreeF = False
memberPAlg elem (RedBlackTreeNodeF _ left cur right) =
(elem == cur) || (left || right)
Но, похоже, это O(nlogn)
, а не O(logn)
. Есть ли способ выборочно рекурсивно использовать схему рекурсии для экономии времени? Я думаю об этом неправильно?
Из-за лени left
и right
оцениваются, только если вы их попросите. Итак, просто сравните текущий узел с искомым значением, чтобы решить, в какое поддерево идти:
memberPAlg :: Ord a => a -> RedBlackTreeF a Bool -> Bool
memberPAlg _ EmptyRedBlackTreeF = False
memberPAlg elem (RedBlackTreeNodeF _ left cur right) =
case compare elem cur of
EQ -> True
LT -> left
GT -> right
Возможно ли что-то подобное для вставки? Кажется, что решение должно быть O (n), потому что катаморфизм или анаморфизм должны полностью рекурсивно?
@cocorudeboy Для вставки вам понадобится параморфизм, чтобы вы могли просматривать ветки в их непреобразованном состоянии, а также преобразованный результат.
FWIW, ваша версия просто O (n) без логарифмического фактора. Он касается каждого узла в дереве ровно один раз, каждый раз выполняя постоянный объем работы.