Красивое дерево PATRICIA (Реализация на C++)

[kstarkh_o151w]

Доброго времени суток! Сейчас я попробую окунуть вас в интересное, всеми забытое, где-то немного сложное дерево PATRICIA, также реализую ее на языке С++, будет очень больно, приготовьтесь.

---

Немного теории и сразу начнем с реализации​

Патриция представляет собой смешение trie и DST дерева, на ней можно написать свой собственный ассоциативный контейнер, используется чаще всего для сравнения строк, а переход между вершинами происходит по сравнению соответствующего бита.
Каждая вершина имеет:

1. Ключ(string key)
2. Значение(int value)
3. Индекс бита, который нужно проверять для поиска(size_t index)
4. Указатели на правую и левую вершину(Node *right, *left)

struct Patricia::Node{
std::string key;
int value;
size_t index;
Node *right, *left;

Node(const std::string& key, const int& value, const int& index)
: key(key), value(value), index(index), left(nullptr), right(nullptr) { }

~Node(){}
};

Теперь самое время поговорить о самой патриции, а точнее о ее свойствах, их немного. Во-первых, правый указатель корня - nullptr всегда. Во-вторых, каждая вершина патриции, кроме корня имеет ненулевой индекс, и все указатели всегда направлены на другие вершины, поэтому каждый метод дерева в самом начале проверяет существование корня, а поиск начинается с левой вершины от корня. В-третьих, листом считается вершина, один из указателей которого направлен на самого себя. На данный момент интерфейс патриции выглядит так:

typedef class Patricia{
private:
struct Node;
Node *root = nullptr;
public:
} patr;

Пример визуализированной патриции (для упрощения я не стал рисовать value вершин):

Пример патриции 1
Немного разберемся в примере, справа сверху нарисован шаблон, в котором указано, что обозначается. В нашем случае, в центре пишется индекс бита, который мы должны проверять, находясь в этой вершине. Внизу пишется сам ключ. Теперь попробуем реализовать функцию поиска вершины в нашем примере дерева(1).
Сделаем ограничение на алфавит в нашем ключе, использовать можно только латинские буквы в нижнем регистре. Теперь можно вывести на экран битовое представление каждой латинской буквы, нам это понадобится(советую продублировать вкладку).

Конечно же каждый байт(символ) кодируется 8 битами, но символы нижнего регистра отличаются только лишь последними 5-ю битами

Поиск​

Попробуем найти узел с ключом "a", его побитовая цепочка 00001. Важно заметить, что индекс идет не с 0, а с 1, таким образом '1' будет иметь индекс 5.
Как было сказано выше, мы проверяем существование корня, если его нет, то выводим nullptr, если есть, то начинаем поиск с левого узла, в примере это узел с индексом 1 и ключом "y". Берем текущий индекс и проверяем бит из искомой побитовой цепочки в позиции текущего индекса. В данном случае бит равен - 0, поэтому мы двигаемся по левому указателю.
Теперь текущий узел равен индексу 2 и ключу "l", проверяем бит из исходного ключа("а") по текущему индексу(2). Бит равен - 0, поэтому снова двигаемся по левому указателю.
Теперь текущий узел равен индексу 4 и ключу "b", проверяем бит из исходного ключа("а") по текущему индексу(4). Бит равен - 0, поэтому снова двигаемся по левому указателю.
Поиск заканчивается тогда, когда индекс текущего узла меньше или равен предыдущему, текущий индекс - 0, предыдущий - 4. Поиск закончен, найденная вершина: "а", индекс 0 - является нужной нам вершиной, которую мы искали.
[IMG alt="Темно оранжевым показаны узлы, по которым проходим
Синим - стрелки, по которым проходим
Красным показан узел, в котором закончился поиск
Сверху в красном обрамлении указан метод, ключ который мы ищем и его битовая цепочка"]Для просмотра ссылки Войди или Зарегистрируйся оранжевым показаны узлы, по которым проходим Синим - стрелки, по которым проходим Красным показан узел, в котором закончился поиск Сверху в красном обрамлении указан метод, ключ который мы ищем и его битовая цепочка
Давайте напишем метод Search. Во-первых, создаем два указателя currentNode и prevNode, они нужны для отслеживания текущей вершины и выхода из функции, осуществляется когда currentNode->index <= prevNode->index.

Первым делом мы должны получить индекс символа, который нам надо проверять из исходной строки. Берем индекс из текущего узла, вычитая 1. Дальше делим на константу BIT_COUNT. Вычитаем 1 потому, что у нас индексы начинаются не с 0, а с 1. Допустим возьмем из патриции 1 вершину "m", у нее индекс 5 - 1 = 4, при делении на BIT_COUNT мы получим 0, поэтому проверяем из исходной строки нулевой символ, если бы мы не вычитали, то получили бы индекс 1, что неправильно.
Дальше стоит проверить, что индекс не выходит за размеры исходной строки:

Если индекс выходит за размеры, то мы "как бы" берем бит из нулевого символа, битовая цепочка которого равна - 00000, то есть мы в любом случае получим бит 0, а это означает, что всегда будем переходить по левому указателю, запоминая текущую вершину в prevNode.

Если индекс все таки не выходит за пределы размера искомого ключа, то мы должны взять текущий символ из строки. Высчитать смещение, т.е. насколько надо сместить битовую цепочку, чтоб нужный нам бит остался в самом крайнем правом положении, допустим нам надо взять первый бит из цепочки 10001, тогда смещение будет равно 4.
Получаем бит, применяя побитовую операцию И и сдвига, проще говоря если в конце битовой цепочки '1', то currentBit = true, если '0', то false.
Запоминаем текущую вершину, потому что сейчас будем передвигать ее. С помощью тернарного оператора делаем перемещение текущей вершины. Из метода Search возвращаем currentNode, когда индекс будет <= индексу предыдущей вершины. Полная функция выглядит так:

Patricia::Node* Patricia::Search(const std::string& findKey) const{
Node *currentNode = root->left, *prevNode = root;

while(currentNode->index > prevNode->index){
// Index of char that we need to check
size_t charIndex = (currentNode->index - 1) / BIT_COUNT;

// findKey is less than need char
if(charIndex >= findKey.size()){
// Remember prevNode
prevNode = currentNode;
// Only '0'
currentNode = currentNode->left;
continue;
}

char currentChar = findKey[charIndex];
// How many times should we shift to the right
int offset = (BIT_COUNT - 1 - ((currentNode->index - 1) % BIT_COUNT));
// Get current bit
bool currentBit = (currentChar >> offset) & 1;

// Remember prevNode
prevNode = currentNode;
// If '1' go right, '0' go left
currentBit ? currentNode = currentNode->right
: currentNode = currentNode->left;
}
return currentNode;
}

Стоит заметить, что я не проверяю наличие корня, все из-за того, что данный метод в приватном доступе, и каждая функция перед вызовом Search проверяет наличие корня. Если вы делаете другую реализацию, то моя реализация может сломать вашу программу :с

Добавление пары в дерево​

Алгоритм добавления пары в дерево:

1. Найти вершину, если она существует, то выдать ошибку, если нет, то (2).
2. Найти битовую разницу между ключами найденной вершины и добавляемой.
3. Пройтись снова от корня, найти вершину с индексом больше добавляемой.
4. Вставить новый узел между найденной вершиной и его родителем.
5. Связать указатели, один из них направлен на добавляемую вершину, другой на найденную(из п. 3).

void Patricia::Add(const std::string& key, int value){
if(!root){
root = new Node(key, value, 0);
root->left = root;
return;
}

Node *foundNode = Search(key);
if(foundNode->key == key)
throw std::runtime_error("\t\"" + key + "\" already exist!\n");

Вставка узла в дерево​

Предположим, что currentNode - вершина, индекс которой выше индекса вставляемого узла, а prevNode - вершина, индекс которой ниже индекса вставляемого узла. Теперь надо связать их:

char getCharFromKey = key[(index - 1) / BIT_COUNT];
bool getBit= getCharFromKey >> (BIT_COUNT - 1 - (index - 1) % BIT_COUNT) & 1;
Node *newNode = new Node(key, value, index);

if(prevNode->left == currentNode)
prevNode->left = newNode;
else
prevNode->right = newNode;

getBit ? (newNode->right = newNode, newNode->left = currentNode)
: (newNode->left = newNode, newNode->right = currentNode);
}

Так как у нас в параметрах уже есть все 3 значения, которые нам нужны, то getCharFromKey равен символу исходного ключа по индексу (index - 1) / BIT_COUNT. Также получаем и бит из символа. Создаем новый узел с тремя параметрами.

[IMG alt="Синим - стрелки перемещения по вершинам
Красным - найденная вершина"]Для просмотра ссылки Войди или Зарегистрируйся - стрелки перемещения по вершинам Красным - найденная вершина
Поиск выдал нам результат - вершину "l" с индексом 2. Ищем различия в найденном и исходном битах. l - 01100, n - 01110, различие в 4 бите. Запускаем функцию Insert.
[IMG alt="Синим - стрелки переходов
Желтый - вершина родитель
Зеленый - вершина ребенок"]Для просмотра ссылки Войди или Зарегистрируйся - стрелки переходов Желтый - вершина родитель Зеленый - вершина ребенок
Функция Insert находит две связанные вершины, между которыми надо вставить новую. Зеленая вершина имеет индекс выше исходного(4), а желтая - ниже.

Фух... Теперь немножко отдохнем, буквально на 5 секунд, реализуем функцию получения значения из дерева.

Функция At​

int& Patricia::At(const std::string& findKey) const{
if(!root)
throw std::runtime_error("\t\"" + findKey + "\" hadn't found!\n");

Node* get = Search(findKey);

if(get->key == findKey)
return get->value;

throw std::runtime_error("\t\"" + findKey + "\" hadn't found!\n");
}

Я думаю добавлять нечего, мы сначала проверяем корень, дальше используем функцию поиска, проверяем найденный узел, в случае правильности - возвращаем значение, иначе ошибку.
Возвращаю по ссылке, так как я уверен в том, что возвращенное значение будет существовать, а не удалится.

В приведенном примере выше удаляем вершину "t", ее же будем называть вершина А, ее владелец вершина "z", она же вершина Б, ее владелец вершина "y", она же вершина В.

Пока что мы просто ищем нужный удаляемый элемент и возвращаем кортеж и удаляемого элемента, его владельца и родителя владельца, их же разыменовываем в указатели. Дальше проверяем, что мы нашли нужный ключ. Дальше проверяет 1 вариант удаление, когда корень один в дереве, его нужно удалить.

Функция Clear​

Одна функция у меня в публичном доступе, другая в приватном, я реализовал все на основе рекурсии.


Приватная функция удаления узла, просто вызывает такое же удаление для детей текущего узла, а потом удаляет саму вершину.

Финальный интерфейс​

Браво, ты дошел до этого момента и почти не выстрелил себе в ногу, давай порадуемся.