Haskell 中的二叉搜索树实现

Question

我正在 Haskell 中完成一项作业，并且对我得到的二叉搜索树的实现有疑问。我用来学习的书 Haskell 使用了二叉树的以下实现：

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

这个定义对我来说很有意义，因为它表明树要么是空树，要么是包含一个值和两棵树的元素。然而，我在作业中给出的二叉搜索树的实现如下：

data BT a b
  = Leaf
  | Branch (BT a b) a b (BT a b)
  deriving (Eq, Show)

在此实现中，每个分支是否代表一对由更多分支或叶子组成的节点？另外 advantages/disadvantages 这个实现比传统的有什么优势？任何帮助将不胜感激！

Answer 1

我认为@chepner 已经搞定了。这是一个包含键（a 类型）和值（b 类型）的二叉树。

这样想。如果您从定义开始：

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

并且想在每个节点存储一个 key/value 对，你可以将类型 a 变成一对。以下不是合法的 Haskell data 类型，因为您不能在左侧使用 (k,v)，但它说明了有效类型 Tree (k,v) 的外观喜欢：

data Tree (k,v) = EmptyTree | Node (k,v) (Tree (k,v)) (Tree (k,v))

您可以通过为类型构造函数 Tree 提供 k 和 v 适当的参数来使其成为有效的 Haskell 类型定义，即替换 Tree (k,v) 到处都是 Tree k v：

data Tree k v = EmptyTree | Node (k,v) (Tree k v) (Tree k v)

现在，作为一般规则，如果您的数据类型的构造函数包含一对：

data SomeType a b = Pair1 (a,b)

它或多或少等同于：

data SomeOtherType a b = Pair2 a b

毕竟，你可以写Pair1 (2,"hello")或Pair2 2 "hello"，它们都存储相同的数据。

鉴于此，我们可以将 Tree k v 的定义重写为：

data Tree k v = EmptyTree | Node k v (Tree k v) (Tree k v)

现在，Node 构造函数中的四个字段没有的顺序；我们可以重新排序它们并仍然存储完全相同的信息，所以让我们将 "left branch" 字段移到前面：

data Tree k v = EmptyTree | Node (Tree k v) k v (Tree k v)

现在这与您的 BT 类型的结构完全匹配：

data BT a b = Leaf | Branch (BT a b) a b (BT a b)

Binary Search Tree Implementation in Haskell