Рубрики

Перечисление бинарных деревьев

Двоичное дерево помечается, если каждому узлу назначена метка, а двоичное дерево не помечено, если узлам не назначена какая-либо метка.

Below two are considered same unlabeled trees
    o                 o
  /   \             /   \ 
 o     o           o     o 

Below two are considered different labeled trees
    A                C
  /   \             /  \ 
 B     C           A    B 

Сколько разных немаркированных двоичных деревьев может быть с n узлами?

For n  = 1, there is only one tree
   o

For n  = 2, there are two trees
   o      o
  /        \  
 o          o

For n  = 3, there are five trees
    o      o           o         o      o
   /        \         /  \      /         \
  o          o       o    o     o          o
 /            \                  \        /
o              o                  o      o

Идея состоит в том, чтобы рассмотреть все возможные пары отсчетов для узлов в левом и правом поддеревьях и умножить подсчеты для конкретной пары. Наконец добавьте результаты всех пар.

For example, let T(n) be count for n nodes.
T(0) = 1  [There is only 1 empty tree]
T(1) = 1
T(2) = 2

T(3) =  T(0)*T(2) + T(1)*T(1) + T(2)*T(0) = 1*2 + 1*1 + 2*1 = 5

T(4) =  T(0)*T(3) + T(1)*T(2) + T(2)*T(1) + T(3)*T(0)
     =  1*5 + 1*2 + 2*1 + 5*1 
     =  14 

Приведенный выше шаблон в основном представляет собой каталонские номера . Первые несколько каталонских номеров: 1 1 2 5 14 42 132 429 1430 4862,…

Вот,
T (i-1) представляет количество узлов в левом поддереве
T (n-i-1) представляет количество узлов в правом поддереве

Число каталонцев также можно оценить по прямой формуле.

   T(n) = (2n)! / (n+1)!n!

Количество деревьев двоичного поиска (BST) с n узлами также равно количеству немеченых деревьев. Причина этого проста: в BST мы также можем сделать любой ключ корневым. Если root — это i-й ключ в отсортированном порядке, то ключи i-1 могут идти с одной стороны, а (ni) — с другой.

Сколько помеченных двоичных деревьев может быть там с n узлами?
Чтобы подсчитать помеченные деревья, мы можем использовать вышеуказанное количество для немеченых деревьев. Идея проста, каждое немеченое дерево с n узлами может создать n! различные помеченные деревья путем назначения разных перестановок меток для всех узлов.

Следовательно,

Number of Labeled Tees = (Number of unlabeled trees) * n!
                       = [(2n)! / (n+1)!n!]  × n!

Например, для n = 3, есть 5 * 3! = 5 * 6 = 30 различных помеченных деревьев

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Перечисление бинарных деревьев

0.00 (0%) 0 votes