Тема: Деревья

Статья

Сбалансированные деревья: AVL, красно-чёрные, B-деревья

Как заставить дерево поиска не вырождаться: повороты как базовый примитив, строгий баланс AVL, слабый баланс красно-чёрных деревьев, многопутевые B и B+ деревья для …

#структуры данных#деревья#балансировка

Статья

Префиксные деревья, суффиксные массивы и строковые структуры

Что делать, когда ключ — не число, а последовательность: боры и их сжатые формы, автомат Ахо-Корасик для поиска тысячи шаблонов за один проход, суффиксные массивы с LCP …

#структуры данных#строки#деревья

Статья

Деревья и бинарные деревья поиска

От определения дерева до продакшн-BST: обходы, инвариант порядка, поиск/вставка/удаление, порядковые запросы, вырождение и почему в реальных библиотеках лежит не BST.

#структуры данных#деревья#бинарные деревья поиска

Статья

Дерево отрезков и дерево Фенвика

Как отвечать на запросы к произвольным отрезкам массива за O(log n), когда массив всё время меняется: биты дерева Фенвика, каноническое разбиение дерева отрезков, …

#структуры данных#деревья#массивы

Статья

Абстрактное синтаксическое дерево: представление, обход, паттерн Visitor

Как спроектировать узлы AST, обходить дерево в трёх порядках и не уронить стек, зачем нужен Visitor и почему в языках с алгебраическими типами он не нужен — с работающим …

#компиляторы#ast#деревья