Вставка отдельных элементов в двоичную кучу - PullRequest
Новая
       8

Вставка отдельных элементов в двоичную кучу

0 голосов
/ 24 июня 2018

Количество способов, которыми числа 1,2,3,4,5 могут быть вставлены в двоичную кучу, так что результирующая двоичная куча равна минимальной куче?

Ответ = 8

=============================================== ===========================

Мой дубль - поскольку это куча Min, минимальное значение будет в корне.

Это будет минимальная куча как 

                             o   -------> root will be chosen in 1 way
                            / \
                           o   o 
                          / \ 
                         o  o

-> Левое поддерево будет иметь путь 4C3 * 1 * 2 , так как снова root получит минимальное значение, а левый и правый дочерние элементы могут получить любое значение.

-> Наконец, правильное поддерево => 1C1 = 1

Всего - 1 * 4C3 * 1 * 2 * 1 = 8. Правильный ли этот подход?

1 Ответ

0 голосов
/ 24 июня 2018

Да, ваш правильный ответ - 8. Давайте рассмотрим все соглашения.

Пусть LST = left subtree и RST = right subtree

first -1 исправлено в корне (так как 1является самым низким элементом).

1-й способ: мы можем иметь (2,3,4) в LST и только 5 в RST: здесь (2,3,4) можно расположить двумя способами, сохраняя4 в качестве корня в LST

2-й способ: (2,3,5) в LST, что само по себе можно сделать двумя способами и сохранить 4 в RST

3-й способ: (2,4,5) в LST и 3 в RST

4-й способ: (3,4,5) в LST и 2 в RST

всего путей = 2 * 2 * 2 * 2 = 8 путей

...