如何平衡 Elixir 中的最大堆树？

Question

我已经实现了最大堆树，但是当创建新节点时，树变得不平衡。例如，如果插入的大部分值都小于根值，则它成为左重树。这是因为 if-else 比较，但是还有其他方法来平衡树吗？提前致谢。

defmodule MaxHeap do

  defstruct value: nil, right: nil, left: nil

  def new(value), do: %MaxHeap{value: value}

  def insert(newValue=%MaxHeap{value: rootValue}, nextValue) do
    if nextValue <= rootValue do
      %MaxHeap{newValue | left: insert(newValue.left, nextValue)}
    else
      temp=rootValue #save old rootValue in temp, before editing it
      rootValue=nextValue
      nextValue=temp
      %MaxHeap{newValue | right: insert(newValue.right, nextValue), value: rootValue}
    end
  end

  def insert(nil, value) do
    %MaxHeap{value: value}
  end
end

Elixir iex 中的输出树：

Answer 1

如果您真正想要的是堆，则可以使用稍微不同的数据结构，称为左树 - 它是一棵总是以特定方式不平衡的树，允许您进行O(log(N))堆操作。您可以在这篇关于左派树的博客文章中看到对此的描述。

一种易于理解的平衡树的策略是所谓的 AVL 树。AVL 树是一棵二叉树，其中任何节点的两个子节点之间的高度差不能大于 1。这棵树几乎是平衡的，因为它的高度2log(N)在任何时候都可以达到最大。这里实现它的方法是：

1. 将树的高度存储在节点中：

   defstruct value: nil, right: nil, left: nil, height: 1
   

2. 插入后更新树高，然后平衡：

   def insert(newValue = %MaxHeap{value: rootValue}, nextValue) do
     if nextValue <= rootValue do
       %MaxHeap{newValue | left: insert(newValue.left, nextValue)}
     else
       %MaxHeap{newValue | right: insert(newValue.right, nextValue)}
     end
     |> set_height()
     |> balance()
   end
   

3. 有一个height处理空树的函数：

   def height(nil), do: 0
   def height(tree), do: tree.height
   

4. 有一个set_height根据孩子的身高设置父母的高度的函数：

   defp set_height(tree) do
     %{tree | height: max(height(tree.left), height(tree.right)) + 1}
   end
   

5. 在balance函数中，如果子树的高度变化超过 1，则向左或向右应用旋转：

   defp balance(tree) do
     cond do
       height(tree.left) > height(tree.right) + 1 -> rotate_right(tree)
       height(tree.right) > height(tree.left) + 1 -> rotate_left(tree)
       true -> tree
     end
   end
   

6. 有一个rotate_left函数（和类似的rotate_right函数）：

   defp rotate_right(tree) do
     %{tree.left | right: set_height(%{tree | left: tree.left.right})}
     |> set_height()
   end
   
   defp rotate_left(tree) do
     %{tree.right | left: set_height(%{tree | right: tree.right.left})}
     |> set_height()
   end
   

关于这些旋转需要注意的重要一点是它们保留了二叉树不变性。

您可以在 geeksforgeeks 关于 AVL 树的帖子中阅读有关此方法的更多信息。