Или какой другой способ или подход пока не думал. Каждый узел имеет вычисленное значение хешкода.
Как сделать быстрый поиск ключа по значению, как переопределить Equals? Без рекурсии?
// код тут написал примерный
class A{
A nodeChild1;
A nodeChild2;
int data; // только на самом вверху дерева , 2^(n-1)-1 узлов
// int casheHashCode;
private bool _equalrecursion(A? x, A? y)
{
if(x.GetHashCode()==y.GetHashCode(){
if(x.Child1.GetHashCode()==y.Child1.GetHashCode())
if(x.Child2.GetHashCode()==y.Child2.GetHashCode()){
if(_equalrecursion(x.Child1,y.Child1)
if(x.Child1!=null...)
return _equalrecursion(x.Child2,y.Child2)
else return x.Value==y.value;
}
}
return false;
} public bool Equals(А? x, А? y)=>_equalrecursion(A,Б);
}
В таком решении для того что бы проверить 2 равных узла будет 2^n сравнений выдающих true
Как можно сократить число вычислений допутсим до 3, можно составить такую хеш функцию, что бы гарантировано(или с какой-то высокой вероятностью), не было коллизий между узлами на соседней высоте. Типа что бы хеш дочерних узлов влиял на хеш узла?
Что бы допустим для узла с хешом S на высоте- 10 если бы нашелся бы узел с хешом S, то он мог быть либо искомым значением, либо узлом на какой-то другой высоте, допустим 20, и легко не выдерживал проверку lдочерних узлов.
Типа что бы максимум проверить сам узел, и 2 его потомков? А п коллизии хешей могут быть только у узлов на 2 порядка выше меньше.
Может как-то можно хеш-функцию составить хитро, сдвинуть байты( Какие есть статьи по написанию хеш функций, как там подбираются параметры типа обычно что-то такое. a*434334^b*1122121... как эти числа подбираются)
Из задачи, Ключ в Dictionary сравнивается по
значению, полей. Так как каждый раз перед поиском создается объект из комбинации узлов. Задача проверить, если такая комбинация узлов в хештаблице? Избежав коллизий.
Поиск должен быть быстрым, а все остальное неважно. Пока у мен решение(не решение), рекурсивное сравнение всех узлов. Но хотелось бы ограничиться так что бы проверки детей было достаточно.( Из условия видно, что число вариантов узлов на каждой высоте дерева известен 2^n, вот можно составить так функцию что бы все комбинации давали достоверно разный результат, допустим на высоте дерева 10, может быть 1024 вариантов узлов, и 1024^2 их вариантов. (тут возможно я сам ответил на вопрос, для 2^16 комбинаций, которые укладываются в 32 бита) Может там как-то индексировать, и хранить индексы.
Да и дерево только растет, все значения уникальны, а каждый верхний узел на высоте N может иметь только узлы высотой N-1
И вопрос, к примеру для каждой высоты дерева придумать уникальную хеш функцию. вычисления ее родителя, таким образом надо 32 функции придумать,
К примеру для дерева высотой 4
Для 2 высоты (2^2) узла будет искаться f1(x1,x2)
Для 3 высоты (2^3) узла будет искаться f2(x1',x2')=f2( f1(x11,x21),f1(x21,x22);
И так далее.
И можно ли подобрать так, что бы гарантировать что какая-нибудь f4(x1,x2) != f7(x1,x2)?
