Количество бинарных деревьев поиска по n элементам

Мне нужно найти несколько различных бинарных деревьев поиска по n элементам. Я знаю, что количество деревьев бинарного поиска по n отчетливый элементы каталонского числа. Но что, если числа могут повторяться? В бинарном дереве поиска элементы левого поддерева меньше корневого, а элементы правого поддерева равны или больше корневого.

Это мой код для расчета количества различных деревьев двоичного поиска по n элементам. Я вычисляю это число по модулю 123456789, так как оно может быть очень большим. Могу ли я просто изменить его, чтобы решить мою проблему?

#include <algorithm>
#include <vector>
#include <iostream>
#include <limits>

using std::vector;
using std::cin;
using std::cout;
using std::endl;long long countTreeDP(int nodeNumber)
{
vector <vector<long long> > cNumbers;
for (int i = 0; i < nodeNumber + 2; ++i)
{
vector<long long> cur(nodeNumber + 2, 0);
cNumbers.push_back(cur);
}
for (int i = 0; i < nodeNumber + 2; ++i)
{
cNumbers[i][0] = 1;
}

long long sum = 0;
for (int i = 1; i < nodeNumber + 1; ++i)
{
sum = 0;
for (int j = 1; j <= i; ++j)
{
long long numFirst = cNumbers[nodeNumber + 1][i - j] % 123456789;
long long numSecond = cNumbers[nodeNumber + 1][j - 1] % 123456789;
cNumbers[j][i] = (numFirst * numSecond) % 123456789;
sum += cNumbers[j][i];
sum = sum % 123456789;
}
cNumbers[nodeNumber+1][i] = sum;
}

return cNumbers[nodeNumber+1][nodeNumber];
}

int main()
{
vector<long long> nodesValues;
int size = 0;
cin >> size;

for (int i = 0; i < size; ++i)
{
long long elem;
cin >> elem;
nodesValues.push_back(elem);
}

std::sort(nodesValues.begin(), nodesValues.end());

int uniqueCount = 0;

for (int i = 1; i < nodesValues.size(); ++i)
{
if (nodesValues[i] != nodesValues[i-1])
++uniqueCount;
}
cout << countTreeDP(uniqueCount + 1) << endl;
system("pause");
return 0;
}

2

Решение

Я предполагаю что a[i] за 0 ≤ i < n ваш отсортированный массив значений узлов. Вот что я бы сделал: создать двумерную таблицу T такой, что запись T[x][y] подсчитывает количество деревьев поиска для подпоследовательности x ≤ i < y, Вы бы инициализировали его, установив все T[i][i] за 0 ≤ i ≤ n 1, поскольку пустая последовательность имеет только одно дерево поиска, пустое дерево.

Теперь вы бы написали три вложенных цикла. Самый внешний цикл повторяется по длине последовательности, средний — по возможным начальным позициям, а самый внутренний — по возможным узлам дерева. Что-то вроде

for (int len = 1; len <= n; ++len) {
for (int pos = 0; pos <= n - len; ++pos) {
int left = pos, right = pos + len;
long long cnt = 0;
for (int root = left; root < right; ++root) {
if (root > left && a[root] == a[root - 1])
continue; // duplicate element may not be root
cnt += T[left][root]*T[root + 1][right];
}
}
}

Вышеуказанное будет работать без if для случая отдельных элементов. Если у вас могут быть повторяющиеся элементы, то элемент может считаться корнем поддерева (согласно вашему определению), если предшествующий элемент строго меньше самого элемента или если это первый элемент поддерева. Таким образом, проверка выше пропускает недопустимые корни, поэтому в конце T[0][n] будет держать желаемый счет.

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

3

Другие решения

Других решений пока нет …