Сколько способов построить идеально сбалансированное дерево?

Question

Вопрос в том, сколько существует способов построить идеально сбалансированное бинарное дерево из 15 элементов?

Одна из возможностей будет 8-4-12-2-6-10-14-1-3-5-7-9-11-13-15 ..

Моя идея состояла в том, чтобы написать некоторый код, который генерирует каждую возможную перестановку (которая была бы похожа на .. 15!), А затем удалить те, которые являются неправильными.

Правильные имеют 8 как первый элемент, 4 всегда предшествует 2 и 6, 2 всегда предшествует 1 и 3, 6 всегда предшествует 5 и 7 и т. Д.

Но что-то вроде perms2 = list(itertools.permutations([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])) вызывает ошибку памяти.

Есть ли способ генерировать перестановки с правилами, описанными выше?

Или есть даже более простой способ решения моей проблемы?

Кстати ..

• если количество элементов равно 1, есть 1 способ
• с 3 элементами есть 2 способа (2-1-3 или 2-3-1)
• с 7 элементами есть 80 способов (согласно моему коду и делать это вручную)

, но это не помогло мне получить этомне вид формулы ..

Редактировать: это дерево, о котором я говорю: http://666kb.com/i/bz9znnpdj7etw0fo9.gif

Answer 1

Правильное число - 21964800. Это соответствующая целочисленная последовательность:

http://oeis.org/A076615

В основном вы рекурсивно умножаете возможности: на самом низком уровне вы можете выбрать одну из двух возможностей, например: 2-1-3 и 2-3-1.На уровне выше вы можете запутать выбранный порядок обоих нижних уровней (6 на 3) способами и т. Д.

Answer 2

Я не уверен, что вы подразумеваете под идеально сбалансированным.Но если вы имеете в виду, что количество левых и правых узлов равно для каждого узла , и у вас есть 15 элементов [1-15], из которых 2 ^ 4 -1 элементов, вы можете иметь такое дерево.Поскольку полное двоичное дерево из четырех уровней в точности содержит 15 элементов.

Также из вашего вопроса кажется, что вы имеете в виду полное двоичное дерево поиска.С 15 элементами (1-15) возможно только одно такое дерево.

Рассмотрим, что может идти в корневом узле.Какое число является точной медианой 1-15.Это только 8 и 8.поэтому только 8 могут быть в корне.И если вы будете использовать индукцию, вы придете к выводу, что все узлы имеют только одно возможное значение

Answer 3

С вашим определением идеально сбалансированного, все изменения в структуре происходят на самом глубоком уровне дерева, поэтому вам нужно беспокоиться только об этом одном уровне.

Максимально сбалансированное дерево с высотой h будет иметь2 ^ (h-1) листьев - например, для высоты 1, единственный лист - корень.Все они находятся на самом глубоком уровне.

Минимальное сбалансированное дерево с высотой h имеет только один узел на самом глубоком уровне.

Таким образом, число способов построения идеально сбалансированного бинарного деревастолько же, сколько вы можете иметь от 1 до 2 ^ (h-1) узлов на самом глубоком уровне.

Есть 2 ^ (h-1) узла, которые могут присутствовать или не присутствовать вэтот уровень (проблема комбинаций, а не перестановок), так что вы получаете 2 ^ (2 ^ (h-1)) возможностей, из которых только одна (случай «нет») является недействительной.

Так что я думаюВаш ответ (2 ^ (2 ^ (ч-1))) - 1.Поэтому, если вы можете определить правильное значение h ...

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

Позаботьтесь с моим определением h - дерево нулевой высоты вообще не будет иметь узлов и даст бессмысленный результат - sqrt (2) -1 - иррациональный ответ по крайней мере в двух смыслах.

РЕДАКТИРОВАТЬ

Комментарий Марка заставил меня задуматься еще немного.Для определенного роста я думаю, что мой ответ правильный.Проблема состоит в том, что конкретная высота допускает различное количество узлов в общем количестве, поскольку она позволяет различное количество узлов в этом самом глубоком слое.Таким образом, я не могу получить правильный ответ для определенного количества узлов таким образом.Итак ... давайте попробуем еще раз ...

Если наше дерево имеет высоту h, оно может иметь максимум (2 ^ h) -1 узлов.За исключением самого глубокого уровня, он имеет (2 ^ (h-1)) - 1 узел - все из которых должны присутствовать.

У нас есть c - ((2 ^ (h-1)) - 1)узлы на самом глубоком уровне, и мы можем выбрать, куда поместить эти узлы из 2 ^ (h-1) возможных положений на самом глубоком уровне.Я использую c для подсчета, потому что я хочу определить ...

n = 2^(h-1)
k = c-((2^(h-1))-1)

answer = n выберите k

Я до сих пор не получил h от c -это должен быть пол логарифма с основанием 2, но у меня такое чувство, что где-то рядом.

Answer 4

Вероятно, есть формула, которую нужно найти.Посмотрите маленьким деревом, сколько существует возможностей.

Например, для 3 различных элементов есть только 1 возможное дерево.

Для 4 существует 2

Для 5 есть 3

Для 6 есть только 2 (3 и 4 как root, подразумевается все остальное)

Для 7 только 1.

Для15, с учетом корня, нужно разместить 14 элементов, что составляет 7 + 7, который представлен только в одной форме, поэтому я думаю, что ваша проблема состоит в том, что существует только одно решение, а 8 является корнем.