Haskell 2-3-4 树

Question

我们被要求在 Haskell 中创建一个 2-3-4 树，如写入数据类型、插入函数和显示函数。

我发现很难获得有关这种树的信息，即使使用我熟悉的语言（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)

这可以编译，但我不确定它是否正确，但不确定如何开始将插入写入三节点或四节点。

该作业还指出，显示功能的“导出显示”是不够的，它应该以图表中通常看到的格式打印出树。再次不确定如何处理这个问题。

任何帮助或指导表示赞赏。

Answer 1

我对 2-3-4 树一无所知，但对于三节点，您将从以下内容开始：

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

What 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)

Answer 2

我们被要求创建一棵 2-3-4 树

我表示哀悼。我自己曾经不得不实施一项作业。 2-3-4 树是一种 B 树，它具有 B 树的所有缺点，但没有任何优点，因为像您一样为每个子级数单独编写案例与仅包含 2 个列表一样麻烦-4个元素。

要点是：B 树插入算法应该可以工作，只需固定大小即可。科门等人。他们的书中有一本的伪代码 算法简介（严重命令性警告！）。

使用数据元素和子元素的列表而不是四情况代数数据类型可能仍然更好，即使该类型不会强制节点的大小。至少它可以更容易地扩展节点大小。