Деревья выражения как бинарные деревья
У меня простой вопрос.
Почему все деревья выражений смоделированы как "двоичные деревья", а не как "N-деревья"?
Есть ли причина, по которой выражение не может быть смоделировано с использованием N-арного дерева?
2 ответа
Есть несколько веских причин, по которым деревья выражений часто бывают двоичными:
- Наиболее распространенные деревья выражений представляют арифметические операции (
+
,-
,*
,/
) или логические предикаты (AND
,OR
,NOT
,XOR
). Есть все двоичные (и унарные) операции, поэтому двоичные деревья имеют смысл. Вы можете иметь, например, н-ар+
, но это только усложняет вещи без уважительной причины. С более теоретической точки зрения, если у вас есть 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-арного дерева?
Они есть.