Сжатые префиксные деревья17.09.2012 10:31

Тема префиксных деревьев поиска уже неколько раз поднималась на хабре.
Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В
этом недавнем посте рассматривается «питонья библиотека
datrie», являющаяся Cython-оберткой библиотеки
libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (
АВЛ-дерево) и сжатого префиксного дерева.
Читать дальше →
© Habrahabr.ru