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

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

Answer 1

我认为@chepner 已经成功了。这是一个包含键(a 类型)和值(b 类型)的二叉树。

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

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

并且想要在每个节点存储一个键/值对，您可以将 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 构造函数中的四个字段不必按该顺序排列；我们可以对它们重新排序并仍然存储完全相同的信息，所以让我们将“左分支”字段移到前面:

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)