Как сбалансировать Max Heap Tree в эликсире? - PullRequest
Новая
       50

Как сбалансировать Max Heap Tree в эликсире?

0 голосов
/ 03 марта 2019

Я реализовал Max Heap Tree, но при создании новых узлов дерево становится несбалансированным.Например, если большинство введенных значений меньше корневого значения, оно становится левым тяжелым деревом.Это из-за сравнения 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:

1 Ответ

0 голосов
/ 04 марта 2019

Если вам действительно нужна куча, вы можете использовать немного другую структуру данных, называемую левым деревом - это дерево, которое всегда не сбалансировано определенным образом, что позволяет вам выполнять операции O(log(N)) кучи.Вы можете увидеть описание этого в этом посте блога о левых деревьях .

Одна из стратегий сбалансировать ваше дерево, которая проста для понимания, - это то, что называется деревом AVL.Дерево AVL - это двоичное дерево, в котором разница в высоте между двумя дочерними элементами любого узла не может быть больше единицы.Это дерево почти сбалансировано тем, что его высота может быть не более 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 .

...