在Haskell中找到一种更习惯、更简短的平衡二叉树插入方法

我在Haskell中编写了一个二叉树（不是搜索树）数据类型，并编写了插入函数，使二叉树在每次插入后始终保持平衡。即使它工作正常，它看起来也不是很漂亮，我无法找到一种方法使它更像Haskell。有没有一种方法可以使插入更漂亮，或者是这样？代码：

data Tree a = Leaf
  | Node Integer (Tree a) a (Tree a)
    deriving (Show, Eq)

getHeight :: Tree a -> Integer
getHeight Leaf = -1
getHeight (Node height _ _ _) = height

insert :: a -> Tree a -> Tree a
insert val Leaf = Node 0 Leaf val Leaf
insert val (Node height lTree curVal rTree)
  | getHeight lTree <= getHeight rTree = let newLTree = insert val lTree in Node (1 + max (getHeight newLTree) (getHeight rTree)) newLTree curVal rTree
  | otherwise = let newRTree = insert val rTree in Node (1 + max (getHeight lTree) (getHeight newRTree)) lTree curVal newRTree

foldTree :: [a] -> Tree a
foldTree = foldr insert Leaf

首先，在第二个分支中，你可以知道max将返回哪个参数，因为你已经比较了两个高度。所以：

insert val (Node height lTree curVal rTree)
  | getHeight lTree <= getHeight rTree = let newLTree = insert val lTree in Node (1 + max (getHeight newLTree) (getHeight rTree)) newLTree curVal rTree
  | otherwise = let newRTree = insert val rTree in Node (1 + getHeight lTree) lTree curVal newRTree

实际上，如果将<=拆分为<和==，您 * 总是 * 可以知道max将返回哪一个。您可以使用compare来获得区分这三种情况的ADT：

insert val (Node height lTree curVal rTree) = case compare (getHeight lTree) (getHeight rTree) of
    LT -> Node (1 + getHeight rTree ) lTree' curVal rTree
    EQ -> Node (1 + getHeight lTree') lTree' curVal rTree
    GT -> Node (1 + getHeight lTree ) lTree  curVal rTree'
    where
    lTree' = insert val lTree
    rTree' = insert val rTree

在这个变化中，我还把let拆分成了一个where块。在本例中，是为了让案例之间的对应关系在视觉上变得明显。懒惰将确保只有两个新树中合适的一个得到计算。实际上，我甚至会更进一步：在LT和GT的情况下，您知道外部节点的高度不会改变，因此可以重用现有的高度。

insert val (Node height lTree curVal rTree) = case compare (getHeight lTree) (getHeight rTree) of
    LT -> Node height                 lTree' curVal rTree
    EQ -> Node (1 + getHeight lTree') lTree' curVal rTree
    GT -> Node height                 lTree  curVal rTree'
    where
    lTree' = insert val lTree
    rTree' = insert val rTree

如果走insert/foldTree路线，我想我会在这里停下来。这在我看来相当符合习惯。
但我想我也会考虑是否值得直接构建感兴趣的树，而不需要迭代插入。一种方法可能是构建一堆深度逐渐增加的树，每一步都合并高度相同的树：

push :: a -> [Tree a] -> [Tree a]
push a (t:t':ts) | h == h' = Node (h+1) t a t' : ts
    where [h, h'] = map getHeight [t, t']
push a ts = Node 0 Leaf a Leaf : ts

我们可以把这个栈中的两棵树合并起来，把较小的树作为左分支，把较大的树的两个孩子合并起来作为右分支。

collapse :: [Tree a] -> Tree a
collapse [] = Leaf
collapse [t] = t
collapse (t:t':ts) = collapse $ case t' of
    Leaf -> ts
    Node _ l a r -> Node (1 + getHeight r') t a r' : ts
        where r' = collapse [l, r]

(It实际上，这是正确的，这一点有点微妙！这应该产生最小高度的树，或者当t'是Leaf时丢弃t是可以的，这一点一点也不明显，但两者都是正确的。）
现在，我们可以将这两种算法结合起来，得到foldTree：

foldTree :: [a] -> Tree a
foldTree = collapse . foldr push []

这种方法肯定需要更多的代码，更多的思考和洞察力。然而，这种方法的优点是你得到的是线性运行时间，而不是重复的-insert版本的线性运行时间。

在Haskell中找到一种更习惯、更简短的平衡二叉树插入方法

1条答案

相关问题

热门标签

最新问答