haskell - 平衡AVL树haskell

Question

我正在Haskell中创建AVL树，但不确定如何平衡树。我可以添加元素，但它们不平衡。就像使用我在[4,2,1,3,6,8]中添加的addList方法一样，将其添加为:

以下内容的布局:根4(根2(根1空为空)(根2为空))(根6为空(根8为空)

应打印为:

         4
     2       6
 1       3       8

我想平衡一棵树，但是不知道如何正确实现它，到目前为止，这是我的代码，对此的任何帮助都将是惊人的。

data AVLTree a = Empty | Root a (AVLTree a) (AVLTree a)
    deriving (Eq, Ord, Show)
leaf a = Root a Empty Empty

addNode :: Integral a => a -> AVLTree a -> AVLTree a
addNode a Empty = leaf a
addNode x (Root a left right)
  | x > a = Root a left (addNode x right)
  | x < a = Root a (addNode x left) right
  | otherwise = (Root a left right)
addList :: (Integral a) => [a] -> AVLTree a
addList [] = Empty
addList [n] = leaf n
addList (x:xs) = addNode x (addList xs)



search :: Integral a => AVLTree a -> a -> Bool
search Empty _ = False
search (Root a left right) x
  | x == a = True
  | x < a = search left x
  | x > a = search right x

-- balance :: AVLTree a -> AVLTree a
-- balance Empty = Empty
-- balance tree
-- |(Root r (Root left (Root left1 Empty Empty) Empty) Empty) = (Root left left1 r) -- left left case
-- |(Root r Empty (Root right Empty Empty) (Root right Empty Empty)) = (Root right r right1) -- right right case
-- |(Root r (Root left Empty (Root right Empty Empty)) Empty) = (Root r (Root right (Root left Empty Empty) Empty) Empty) -- left right case
-- |(Root r Empty (Root right (Root left Empty Empty) Empty)) = (Root r Empty (Root left Empty (Root right Empty Empty))) -- right left case

Answer 1

该实现仍然缺少很多内容，您应该多读一些有关需要的内容(即使Wikipedia也有很好的描述，但是如果您进行搜索，则会显示许多其他页面。)

编写任何(自平衡)树的最棘手的部分是在平衡代码中。...如上所述，仅在Haskell中创建树是非常容易的，但是保持搜索log(N)则有点困难。对于AVL，您将不得不添加更多代码来执行以下操作:

向每个节点添加一个int以测量该节点的高度。高度测量为到最远的叶子的距离。 AVL的工作原理是验证左右子节点之间的高度差不会超过1。重要的是要注意，此高度需要直接添加到节点上，而不需要在需要时进行计算(如上的一些演示代码所示)互联网)，否则即使是简单的插入也需要遍历整棵树，而不再是日志N。

添加代码以在插入后在节点树上向上移动(执行此操作的最佳位置可能是在插入本身中，因为您已经向下移动到了插入点，因此只需在递归之后进行检查即可)。计算高度(只需将以下两个高度中的最大值加1，即可在递归调用中计算得出)，然后检查平衡系数(height of right - height of left)。如果事情不平衡(即|balance factor| > 1)，则必须....

调用旋转函数。旋转是一种类型为AVLTree->AVLTree的操作。直观地，它将树中的最高值推到左侧(或根据不平衡的方向向右)，从而恢复了平衡。右节点成为新的顶部节点，然后将其左节点移到旧的顶部，然后旧的顶部成为新的左节点。这是视觉效果-

   a                            c
  / \                          / \
 b   c             ->         a   e
    / \                      / \
   d   e                    b   d

请注意，对于每个不平衡，您将需要旋转一次或两次，具体取决于您将要进行的简单检查...。如果顶部是不平衡的(例如，向右)，则在向左旋转顶部之前，您需要如果右节点向左有任何不平衡，则可能需要将右节点向右旋转(即使与顶部不同，也可以除以1，顶部可以有-1、0或1且不需要旋转)。旋转代码是相同的，因此您应该对上下旋转使用相同的功能(尽管您可能需要使用单独的版本来左右旋转)。

如果您为每个插入片段运行此平衡代码，就足够了...。如果您曾经添加节点而不执行此操作，则可能必须在所有节点上对该树重复几次此过程，然后再平衡树，并且这将不仅仅需要log(N)计算。

当我写这篇文章时，我注意到我几乎没有写任何Haskell特定的信息...。此信息适用于任何语言。我想这是应该的，没有理由仅仅因为我们在Haskell就应该实现不同。如果您在映射到Haskell时遇到任何麻烦，只需在评论中提出即可，我也可以填写。

还要注意，如果只想插入/删除带有Log(N)的对象，则Haskell已经具有Data.Sequence类型。如果这对您有用，则您无需自己编写任何此类内容。

编辑以解决评论-

您提到的height函数有我上面提到的问题-您正在遍历整个树以查找任何节点的高度。插入将不再具有log N复杂度，这消除了首先拥有一棵树的整个要点。 (据我所知，Haskell不会记住这些值中的任何一个……。如果其他人知道，随意输入，它将简化此代码)。

为了进一步详细说明，您将需要像这样扩展AVLTree的定义-

data AVLTree a = Empty | Node a (AVLTree a) (AVLTree a) Int

现在，高度是这样获得的-

height (AVLTree _ _ _ height) = height

然后您的balanceFactor可以工作-

balanceFactor :: AVLTree a -> Int 
balanceFactor Empty = 0 
balanceFactor (Root a left right) = (height right) - (height left)

缺点是您必须添加代码以重新计算更改后整个链到根的高度。

然后，您将需要编写另一个函数来检查是否需要旋转，并在需要时应用它-

rotateIfNeeded::AVLTree->AVLTree
rotateIfNeeded tree 
    | b > 1 = fullRotateLeft tree
    | b < -1 = fullRotateRight tree
    | otherwise = tree
       where b = balanceFactor tree

函数fullRotateLeft/fullRotateRight是rotateLeft/rotateRight的包装，它们首先检查右/左树是否首先需要反向旋转，然后应用所有需要的旋转。

您的rotateRight/rotateLeft函数将不起作用。...左侧的太多变量用Empty填充，因此缺少许多情况。您将要用变量填充大多数变量，然后将它们移到右侧的适当位置。