Как реализовать высоту бинарного дерева поиска рекурсивно, используя эликсир?

Question

Я использую Elixir для написания некоторых программ для деревьев двоичного поиска и наткнулся на контрольно-пропускной пункт с функцией рекурсивного вычисления высоты.

Основная рекурсивная формула для высоты дерева выглядит следующим образом.

1. Если дерево пусто, вернуть 0

2. прочее

   1. Получить максимальную глубину левого поддерева рекурсивно, т.е. Звоните maxDepth( tree->left-subtree)

   2. Получить максимальную глубину правого поддерева рекурсивно, т.е. Звоните maxDepth( tree->right-subtree)

   3. Получите максимальную максимальную глубину слева и справа поддеревья и добавить 1 к нему для текущего узла. max_depth = max(max dept of left subtree,max depth of right subtree) + 1

   4. Return max_depth

Со своей стороны, я получаю следующую ошибку, когда пытаюсь протестировать функцию с общей структурой узлов.

** (ArithmeticError) неверный аргумент в арифметическом выражении

Я попытался убрать добавление 1 к left_depth и right_depth. Это устранило арифметическую ошибку, но я также не получаю никакого числового результата (высоты) для отображения.

Вот моя функция роста. Как вы можете видеть, он соответствует буквально рекурсивному формату.

# calculate the height
@spec height(bst_node) :: number
def height(node) do
  if is_nil(node) do
    IO.puts "No tree exists. The height is 0"
  else
    left_depth =  height(node.left)
    right_depth = height(node.right)
    if left_depth >= right_depth do
        left_depth + 1
        IO.puts "The height of the tree is #{left_depth + 1}"
    else
      right_depth + 1
      IO.puts "The height of the tree is #{right_depth + 1}"
    end
  end
end

Я бы предпочел иметь возможность выполнять эту функцию высоты в эликсире рекурсивно, но это, конечно, не конец света, если мне придется прибегнуть к нерекурсивным средствам, чтобы выполнить это. Это должно просто отобразить высоту общего дерева.

Answer 1

Ваше исключение

** (ArithmeticError) неверный аргумент в арифметическом выражении

не имеет никакого отношения к правильности вашего кода или нет.Значение блока кода по умолчанию является последним выражением, вычисленным внутри этого блока.Когда вы говорите:

  right_depth + 1
  IO.puts "The height of the tree is #{right_depth + 1}"

Ваше последнее выражение равно IO.puts, так что это то, что возвращается из вызова функции.

IO.puts - ваше последнее выражение, и оно возвращает атом.Убедитесь, что с помощью помощника i / 1 в IEx :

iex(3)> i(IO.puts "Puts returns an atom")      
Puts returns an atom
Term
  :ok
Data type
  Atom
Reference modules
  Atom
:ok

Попытка добавить два атома приводит к недопустимой операции.Точное сообщение и ошибка могут быть воспроизведены в IEx.

iex(4)> :atom + :atom
** (ArithmeticError) bad argument in arithmetic expression: :atom + :atom
    :erlang.+(:atom, :atom)

Answer 2

Существует три функции эликсира, которые очень полезны при реализации рекурсивных решений:

1. Соответствие шаблону параметра
2. Несколько функциональных предложений
3. Оптимизация Tail-Call

Вот пример решения, в котором используются первые две функции:

defmodule Tree do
  defstruct [:left, :right]

  def height(%Tree{left: nil,  right: nil}),   do: 0
  def height(%Tree{left: nil,  right: right}), do: 1 + height(right)
  def height(%Tree{left: left, right: nil}),   do: 1 + height(left)
  def height(%Tree{left: left, right: right}), do: 1 + max(height(left), height(right))
end

Сначала определите структуру с именем Tree, используя left и right для представления нашего дерева.

Затем мы определяем 4 предложения функции height, которая использует сопоставление с образцом для проверки значений Tree left и right.

1. Если left и right равны nil, то мы лист и можем вернуть высоту 0
2. Если один из дочерних элементов равен nil, то мы можем вернуть высоту дерева, отличного от нуля, плюс 1 для себя (текущий узел).
3. То же, что и выше.
4. В последнем пункте рассматривается случай, когда оба ребенка не равны нулю. В этом случае верните максимум роста двух детей плюс 1 для себя.

Обратите внимание, что стиль 1 + recursive_call() приведет к стеку рекурсивных вызовов, потому что он должен отслеживать высоту дочерних узлов в стеке вызовов, чтобы наконец выполнить операцию 1 +. Мы можем минимизировать это, передав высоту в качестве параметра-накопителя acc в функцию и воспользовавшись преимуществом оптимизации хвостового вызова, которая позволяет компилятору уменьшить количество кадров стека, необходимых, когда функция является последним. делает, это называть себя. В этом случае нам все еще нужно вычислить max из двух поддеревьев в последнем предложении, что означает, что мы не используем хвостовой вызов в большинстве случаев, но я включил его для полноты .:

def height_tailcall(%Tree{left: nil, right: nil}, acc), do: acc

def height_tailcall(%Tree{left: nil, right: right}, acc) do
  height_tailcall(right, acc + 1)
end

def height_tailcall(%Tree{left: left, right: nil}, acc) do
  height_tailcall(left, acc + 1)
end

def height_tailcall(%Tree{left: left, right: right}, acc) do
  max(height_tailcall(left, acc + 1), height_tailcall(right, acc + 1))
end

Пример:

def example do
  leaf = %Tree{}
  height1 = %Tree{left: leaf,    right: leaf}
  height2 = %Tree{left: height1, right: height1}
  height3 = %Tree{left: height2, right: height1}
  height4 = %Tree{left: nil,     right: height3}

  IO.inspect(height(leaf),    label: "leaf")
  IO.inspect(height(height1), label: "height1")
  IO.inspect(height(height2), label: "height2")
  IO.inspect(height(height3), label: "height3")
  IO.inspect(height(height4), label: "height4")

  IO.inspect(height_tailcall(leaf, 0), label: "leaf (tail recursion)")
  IO.inspect(height_tailcall(height1, 0), label: "height1 (tail recursion)")
  IO.inspect(height_tailcall(height2, 0), label: "height2 (tail recursion)")
  IO.inspect(height_tailcall(height3, 0), label: "height3 (tail recursion)")
  IO.inspect(height_tailcall(height4, 0), label: "height4 (tail recursion)")

  height4
end

Выход:

leaf: 0
height1: 1
height2: 2
height3: 3
height4: 4
leaf (tail recursion): 0
height1 (tail recursion): 1
height2 (tail recursion): 2
height3 (tail recursion): 3
height4 (tail recursion): 4
%Tree{
  left: nil,
  right: %Tree{
    left: %Tree{
      left: %Tree{
        left: %Tree{left: nil, right: nil},
        right: %Tree{left: nil, right: nil}
      },
      right: %Tree{
        left: %Tree{left: nil, right: nil},
        right: %Tree{left: nil, right: nil}
      }
    },
    right: %Tree{
      left: %Tree{left: nil, right: nil},
      right: %Tree{left: nil, right: nil}
    }
  }
}