Могу ли я представить красно-черное дерево как бинарное листовое дерево? - PullRequest
Новая
       15

Могу ли я представить красно-черное дерево как бинарное листовое дерево?

5 голосов
/ 04 июня 2011

Я поиграл с реализацией дерева RB в Haskell, но с трудом изменил его так, чтобы данные помещались только в листья, как в бинарном дереве листьев: 

    /+\
   /   \
 /+\    \
/   \    c
a   b

Внутренние узлы будут содержать другую информацию, например, размер дерева, в дополнение к цвету узла (как в обычном дереве RB, но данные хранятся только в листьях). Мне также не нужно сортировать вставляемые данные. Я использую RB только для получения сбалансированного дерева при вставке данных, но я хочу сохранить порядок, в котором вставляются данные.

Оригинальный код (из книги Окасаки): 

data Color = R | B
data Tree a = E | T Color (Tree a ) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x s = makeBlack (ins s)
    where ins E = T R E x E
        ins (T color a y b) 
            | x < y = balance color (ins a) y b
            | x == y = T color a y b
            | x > y = balance color a y (ins b)
        makeBlack (T _ a y b) = T B a y b

Я изменил его на: (вызывая исключение: неисчерпывающие шаблоны в функциональных модулях) 

data Color = R | B deriving Show
data Tree a = E | Leaf a | T Color Int (Tree a) (Tree a)

insert :: Ord a => a -> Set a -> Set a
insert x s = makeBlack (ins s)
    where 
        ins E = T R 1 (Leaf x) E
        ins (T _ 1 a E) = T R 2 (Leaf x) a
        ins (T color y a b)
            | 0 < y = balance color y (ins a) b
            | 0 == y = T color y a b
            | 0 > y = balance color y a (ins b)
        makeBlack (T _ y a b) = T B y a b

Исходная функция баланса: 

balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance color a x b = T color a x b

который я немного изменил, как видно из моего кода выше.

Заранее спасибо за помощь:)

РЕДАКТИРОВАТЬ: для вида представления, который я ищу, Крис Окасаки предложил использовать двоичный список произвольного доступа, как описано в его книге. Альтернативой было бы просто адаптировать код в Data.Set, который реализован в виде деревьев с балансировкой веса.

1 Ответ

1 голос
/ 10 июня 2011

Если вы имели в виду insert :: a -> Tree a -> Tree a, то ваша ошибка, вероятно, связана с отсутствием предложения для ins (Leaf a).

...