如何平衡 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

Output tree in Elixir iex:

Answer 1

如果你真正想要的是堆，你可以使用一种稍微不同的数据结构，称为左树——它是一棵树这总是以某种特定的方式不平衡，这允许您进行 O(log(N)) 堆操作。你可以看到一个 in this blog post about leftist trees.

的描述

一种易于理解的平衡树的策略称为 AVL 树。 AVL树是二叉树任何节点的两个 children 之间的高度差不能大于一的树。这棵树差不多平衡在于它的高度在任何时候最多可以是 2log(N)。这里实现的方法是：

在节点中存储树的高度：

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

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

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

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

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

有一个 set_height 函数可以根据 children:

的高度设置 parent 的高度

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

在 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

有一个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

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

您可以阅读有关此方法的更多信息 in this geeksforgeeks post about AVL trees。

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

How to balance a Max Heap Tree in Elixir?

functional-programming

tree

elixir

heap

balance