Как вычислить std :: ha sh <> для структуры данных бинарного дерева? - PullRequest
Новая
       71

Как вычислить std :: ha sh <> для структуры данных бинарного дерева?

0 голосов
/ 16 апреля 2020

Я думал хранить деревья в std::unordered_set, чтобы выбрать уникальные деревья из коллекции деревьев. Если мой узел дерева имеет представление, как описано ниже, как найти для этого функцию ha sh? 

struct node {
      int val;
      node *left;
      node *right; 
};

Редактировать: Под аналогичным деревом я имею в виду, что они имеют одинаковые значения во всех соответствующих узлах. Таким образом, функция сравнения будет использовать фактические деревья для сравнения, а не адрес памяти root.

1 Ответ

0 голосов
/ 16 апреля 2020

Если вы можете использовать повышение, вы можете использовать его функцию boost::hash_combine, чтобы смешать значения га sh. В противном случае вы можете написать простую функцию для этого. Вы можете увидеть простую рекурсивную функцию для вычисления га sh дерева. 

struct node 
{
   int val;
   node *left;
   node *right;
};

template <typename T>
size_t hash_combine(std::size_t s, const T & n)
{
   s ^= std::hash<T>()(n) + 0x9e3779b9 + (s << 6) + (s >> 2);

   return s;
}

size_t get_hash(const node & n)
{
   if ((n.left == nullptr) && (n.right == nullptr))
   {
      return std::hash<int>()(n.val);
   }
   else if (n.left == nullptr)
   {
      return hash_combine(get_hash(*n.right), std::hash<int>()(n.val));
   }
   else if (n.right == nullptr)
   {
      return hash_combine(get_hash(*n.left), std::hash<int>()(n.val));
   }
   else
   {
      size_t s = std::hash<int>()(n.val);
      s = hash_combine(s, get_hash(*n.right));
      s = hash_combine(s, get_hash(*n.left));

     return s;
   }
}


namespace std
{
   template <>
   struct hash<node>
   {
      std::size_t operator()(const node & n) const
      {
         return ::get_hash(n);
      }
   };
} // std
...