Дерево остатков или Radix Tree
Предисловие
Итак для чего нужны данные деревья? Прежде всего их используют для:
а) построения ассоциативных массивов с ключами в виде строк
б) IP — маршрутизации (иерархической организации IP-адреса)
в) инвертированных индексов текстовых документов в информационном поиске
г) в ядре Linux’a, где указатель содержащийся в узлах дерева связан с целочисленным ключом (в данном случае long int)
Поехали
Рассмотрим основную идею на который основывается данное дерево. Проверяем только один бит. В чем же суть? На самом деле все проще некуда, в остаточных деревьях метод проверки узлов во время поиска и других операций заключается только лишь в проверки одного бита содержащегося в данном узле, будь то первый или последний, все зависит от реализации.
Ключи хранятся в узлах самого дерева (Digital search )
Ключи на самом деле не хранятся в узлах дерева, они находятся в так называемых дополнительных (добавочных) узлах. ( Radix search )
Преимущества данного подхода в том, что удобно хранить довольно большие ключи в узлах дерева, быстрота поиска нужного нам соответствия в связи с быстрой проверкой условий прохождения по дереву вниз и наконец экономия памяти — часть информации храним непосредственно в ключе. Наверное после таких высказываний напрашивается вопрос — а в чем же собственно минусы данного подхода. Во-первых, искусственно огромные и сложные строки или другие(тут имеется ввиду очень несбалансированное дерево) данные могут сильно увеличить ресурсопотребление, во-вторых, данный подход на уровне ядра сильно зависит от используемой архитектуры, что приводит к непростой реализации на языках высокого уровня.
Наглядно
Попробуем на примере разобрать как осуществлять вставку в Radix search tree, представленном выше
Выводы
Реализация:
— необходимо реализовать два типа узлов
— необходимо учесть низкоуровневую архитектуру
Сложность: О(~ log n)
Неудобства:
— число узлов может превышать количество ключей
Полезные ссылки и литература
1. Реализация на С
2. Википедия
3. Некоторые пояснения к реализации Radix tree в Linux
4. И наконец, та самая полезная презентация, откуда я брал картинки