Как использовать структуру данных splay tree в кодировке huffman для сжатия данных?

Question

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

В любом случае, я хочу реализовать кодировку Хаффмана в java, используя какую-то структуру данных. Но, однако, я думал об использовании splay tree, поскольку это то, что не будет описано в учебном плане курса, а также, поскольку я хочу изучить новую структуру данных. Теперь главный вопрос заключается в том, что если алгоритм кодирования Хаффмана потребовал бы структуру данных Splay tree во-первых?

Что я могу использовать в дереве splay в моем проекте сжатия данных на основе Хаффмана? Или вы предпочтете лучше (для его эффективности и, возможно, для творчества в контексте, что это уникальная и не очень-то известная) структура данных для этого проекта?

Благодаря

Answer 1

Любой код Хаффмана может быть представлен структурой двоичного дерева, листья которого являются символы, которые должны быть закодированы. При переходе от корня к символу, который должен быть закодирован, левая и правая ветви могут быть представлены как 0 или 1 бит; результатом является правильный префиксный код с длиной кода, заданной глубиной символов.

В идеале вы должны использовать структуру дерева splay непосредственно, чтобы определить код Хаффмана для каждого символа. Однако деревья splay сохраняют свои данные в узлах, а не в листьях. Вам нужно будет либо найти способ использования дерева splay на основе данных в листах, либо создать трансформацию, которая вместо этого вычисляет действительный (и эффективный) набор префиксных кодов из узлов узла.

Одна из возможностей состоит в том, чтобы поддерживать левый и правый край каждого поддерева в корневом узле (для обновления, поскольку дерево разворачивается, конечно). Это должно позволить вам искать листья, даже если вы действительно не заботитесь о своих данных узла как таковых. При этом обычные операции разворота должны, естественно, генерировать динамический код Хаффмана, предвзятый относительно недавно встречающихся символов.