Количество возможных путей поиска при поиске в BST

У меня есть следующий вопрос, но у меня нет ответа на этот вопрос. Буду признателен, если мой метод правильный:

Q. При поиске значения ключа 60 в двоичном дереве поиска узлы, содержащие значения ключа 10, 20, 40, 50, 70, 80, 90, пересекаются, необязательно в указанном порядке. Сколько возможных порядков, в которых эти значения ключа могут встречаться в пути поиска от корневого узла, содержащего значение 60?

(A) 35 (B) 64 (C) 128 (D) 5040

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

10, 20, 40, 50, 90, 80, 70, 60.

Так как мы должны пройти все узлы, указанные выше, мы должны начать с 10 или 90. Если мы начнем с 20, мы не достигнем 10 (так как 60> 20, и мы пройдем правое поддерево 20)

Точно так же мы не можем начать с 80, потому что мы не сможем достичь 90, так как 80> 60, мы пройдем левое поддерево 80 и, таким образом, не достигнем 90.

Давайте возьмем 10. Остальные узлы - это 20, 40, 50, 70, 80, 90. Следующим узлом может быть 20 или 90. Мы не можем взять другие узлы по той же ранее упомянутой причине.

Если мы рассмотрим аналогично, на каждом уровне у нас есть два варианта. Поскольку есть 7 узлов, два варианта для первых 6 и нет выбора для последнего. Так что есть полностью

$2*2*2*2*2*2*1$ $2^6$ $64$

Это правильный ответ?
Если нет, то какой подход лучше?
$n$ $2^{n-1}$

data-structures combinatorics binary-trees search-trees graph-traversal AVI
источник

Ответы:

$K$ $K$

Затем последовательности 10, 20, ~~30,~~ 40, 50 и 90, 80, 70 могут быть перемешаны вместе, пока их подпоследовательности остаются нетронутыми. Таким образом, мы можем иметь 10, 20, 40, 50, 90, 80, 70, но также и 10, 20, 90, 30, 40, 80, 70, 50.

Теперь мы можем вычислить число, выбирая положение больших и малых чисел. Смотрите комментарий Арьябхаты. У нас есть две последовательности из 4 и 3 чисел. Сколько способов я могу их перетасовать? В последних 7 позициях мне нужно выбрать 3 позиции для больших чисел (а оставшиеся 4 для меньших). Я могу выбрать их в способа. После исправления этих позиций мы знаем полную последовательность. Например, мой первый пример имеет позиции SSSSLLL, а второй - SSLSLL S. $7 \choose 3$

Вы просите обобщения. Всегда числа меньше найденного числа, а числа большего размера фиксируются в их относительном порядке. Меньшие числа должны увеличиваться, а числовые значения должны уменьшаться. Число тогда . $x$ $y$ $x+y \choose y$

PS (отредактировано). Спасибо Жилю, который отметил, что 30 не в вопросе.

Хендрик Ян
источник

Я бы конечно хотел попробовать. Поскольку № 90,80,70 должны быть вместе, давайте рассмотрим их как одно нет. и он может быть размещен среди 6 мест: _ 10 _ 20 _ 30 _ 40 _ 50 _ Так что это Если по той же аналогии, no.s [10,20,30,40,50] можно поместить в 4 места, это Но это должно быть разделено на встречающиеся общие комбинации (которые я не могу выяснить)

2^{6}

$2^6$

2^{4}

$2^4$

avi

@avi Нет, они не должны быть вместе, только в таком порядке: 10, 20, 90, 30, 40, 80, 70, 50 - это нормально.

Хендрик янв

@avi: Попробуй думать так: большой и маленький. Теперь у вас есть 8 мест: 5 маленьких и 3 больших. Как вы их заполняете? 8 выберите 3. Что до 56, и я предполагаю, что Хендрик тоже получил.

Арьябхата

@HendrikJan В исходном вопросе не было 30, было только 7 значений. И 7 выберите 3 является (A).

Жиль "ТАК - перестань быть злым"

@HendrikJan - можете ли вы объяснить это мне: всегда числа меньше найденного числа, а числа большего размера фиксируются в их относительном порядке

x

$x$

y

$y$

avi

Мы преобразуем ходы в текст. Дано, что во время поиска мы прошли эти узлы

как видно, что красные больше 60, а синие меньше 60.

Путь к узлу 60 включил эти узлы. Таким образом, один из возможных решений этой проблемы является любой другой будет решение содержит только эти шаги. Поскольку за один раз на узле мы можем получить направления в виде S или L при сравнении, и, учитывая, что эти узлы были обнаружены, это означает, что направления были выбраны из этого набора.

{S, S, S, S, L, L, L}

$\{S,S,S,S,L,L,L\}$

Следовательно, общее число возможных решений = все Перестановки этого набора, который задается ответа = вариант А

\frac{7!}{4! \times 3!} = 35

$\frac{7!}{4! \times 3!} = 35$

amarVashishth
источник