Haskell 2-3-4 Tree - PullRequest
Новая
       12

Haskell 2-3-4 Tree

2 голосов
/ 18 декабря 2011

Нас попросили создать 2-3-4 дерева в Haskell, как при записи типа данных, функции вставки и функции отображения.

Мне очень трудно получить информацию о таком дереве, даже на языке, который мне удобен (Java, C ++).

Что у меня до сих пор - 

data Tree t = Empty 
    | Two t (Tree t)(Tree t) 
    | Three t t (Tree t)(Tree t)(Tree t) 
    | Four t t t (Tree t)(Tree t)(Tree t)(Tree t) deriving (Eq, Ord, Show)


leaf2 a = Two a Empty Empty
leaf3 a b = Three a b Empty Empty Empty
leaf4 a b c = Four a b c Empty Empty Empty Empty

addNode::(Ord t) => t ->  Tree t -> Tree t
addNode t Empty = leaf2 t
addNode x (Two t left right)
    | x < t = Two t (addNode x left) right
    | otherwise = Two t left (addNode x right)

Это компилируется, но я не уверен, правильно ли это, но не уверен, как начать запись вставки в три или четыре узла.

Присвоение также говорит, что «создания шоу» для функции отображения недостаточно, что оно должно распечатать дерево в формате, обычно видимом на диаграммах. Снова, неуверенный на пути пойти с этим.

Любая помощь или направление приветствуется.

Ответы [ 2 ]

2 голосов
/ 20 декабря 2011

Я ничего не знаю о 2-3-4 деревьях, но для узла Три вы бы начали что-то вроде этого: 

addNode t (Three x y left mid right)
  | cond1 = expr1
  | cond2 = expr2
  (etc)

Что такое cond1, cond2, expr1 и expr2, точно зависит от определения того, что такое дерево 2-3-4.

Что касается show метода, общая схема будет такой: 

instance (Show t) => Show (Tree t) where
  show Empty = ...
  show (Two x l r) = ...show x...show l...show r...
  show (Three x y l m r) = ...
  show (Four x y z l m n r) = ...

Реализация зависит от того, как вы хотите, чтобы она выглядела, но для непустых случаев вы, вероятно, вызовете show для всех компонентов отображаемого дерева. Если вы хотите сделать отступ для вложенных частей дерева, возможно, вам следует создать отдельный метод: 

instance (Show t) => Show (Tree t) where
  show = showTree 0

showTree :: Show t => Int -> Tree t -> String
showTree n = indent . go
  where indent = (replicate n ' ' ++)
        go Empty = "Empty"
        go (Two x l r) = (...show x...showTree (n+1) l...showTree (n+1) r...)
        (etc)
1 голос
/ 29 января 2012

Нас попросили создать дерево 2-3-4

Мои соболезнования. Я сам когда-то должен был выполнить один для домашнего задания. Дерево 2-3-4 - это B-дерево со всеми недостатками B-дерева и безо всяких преимуществ, потому что написание падежей отдельно для каждого числа детей, как вы делаете, так же громоздко, как и список только из 2 -4 элемента.

Дело в том, что алгоритмы вставки B-дерева должны работать, просто исправьте размер. Cormen et al. иметь псевдокод для одного в своей книге Введение в алгоритмы (предупреждение о серьезной необходимости!).

Возможно, было бы лучше иметь списки элементов данных и дочерних элементов вместо алгебраического типа данных с четырьмя случаями, даже если этот тип тогда не будет обеспечивать размер узлов. По крайней мере, было бы легче расширить размер узла.

...