Деревья выражения как бинарные деревья

У меня простой вопрос.

Почему все деревья выражений смоделированы как "двоичные деревья", а не как "N-деревья"?

Есть ли причина, по которой выражение не может быть смоделировано с использованием N-арного дерева?

2 ответа

Есть несколько веских причин, по которым деревья выражений часто бывают двоичными:

  1. Наиболее распространенные деревья выражений представляют арифметические операции (+, -, *, /) или логические предикаты (AND, OR, NOT, XOR). Есть все двоичные (и унарные) операции, поэтому двоичные деревья имеют смысл. Вы можете иметь, например, н-ар +, но это только усложняет вещи без уважительной причины.
  2. С более теоретической точки зрения, если у вас есть n-арное дерево, вы можете представить его, используя эквивалентное двоичное дерево, не теряя ничего. Используя n-ary + Например, следующие деревья (один n-арный и один двоичный) можно считать одинаковыми:

      +       +
     /|\     / \
    a b c   +   c
           / \
          a   b
    

С другой стороны, есть библиотеки, которые используют n-арные деревья выражений, где они имеют смысл. Например, деревья выражений C# (из System.Linq.Expressions namespace) использовать n-арные деревья для выражения вызова. Итак, выражение f(a, b, c) будет представлен как InvocationExpression это выглядит так:

  f
 /|\
a b c

Почему все деревья выражений смоделированы как "двоичные деревья", а не как "N-деревья"?

Это не так. Внутренние узлы дерева выражений являются операторами, и операторы могут быть, по крайней мере, двоичными или троичными, может быть больше.

Есть ли причина, по которой выражение не может быть смоделировано с использованием N-арного дерева?

Они есть.

Другие вопросы по тегам