Есть zero-suppressed binary decision diagram с модификацией для возможности мультитерминальности (см. вложение). Путь от терминала к корню обозначается булевым вектором, направление перехода определяется наложением маски (смещение меток верхнего уровня зависит от количества возможных переходов на нижних; метка перехода фиксируется к номеру узла на уровне, удаление/добавление одного узла вынуждает изменять вектора всех переходов). Компрессия максимальная, операция чтения занимает O(1), но вот модификация занимает O(n), что не позволительно на больших наборах данных. Как можно оптимизировать эту структуру?
08.11.2015, 20:16 