2-3-4树haskell

Question

我被指派在haskell中实现2-3-4树的功能，问题是，我不确定如何定义2-3-4树。我一直在四处寻找，试图找到正确方向的指针，但进展不是很顺利。

你能建议一个解决方案吗？

Answer 1

1. 为树定义数据类型
2. 在树上实现操作(插入、删除和查找)

http://en.wikipedia.org/wiki/2-3-4_tree是一个很好的起点。在http://en.wikipedia.org/wiki/B-tree上也有一些线索

要定义二叉树，您可以先用简单的英语编写它的递归定义：

具有类型'x‘的值的二叉树是具有类型'x’的值的内部节点和具有类型'x‘的值的两个子树，或者是一个空的叶节点。

然后很容易将其转换为Haskell：

data BinaryTree x = InternalNode x (BinaryTree x) (BinaryTree x) | LeafNode 

2-3-4树与二叉树的不同之处在于它有3种而不是1种内部节点，所以你需要更多的选择。

Answer 2

您的问题有点模糊，因为您不清楚是要定义树结构本身还是定义作用于树的函数。由于2-3-4树只是一个B-Tree，您可以直接使用Data.Tree并编写处理它的函数，并执行您喜欢的约束。

如果您必须自己定义树数据类型，我建议为包含节点和数据的(2|3|4)-tuples的节点定义一个数据类型。