[Перевод] Структуры данных на практике. Глава 9: Двоичные деревья поиска
Катастрофа с красно-чёрным деревом
Компилятор тратил 60% времени на поиск символов. Не на парсинг, не на генерацию кода, просто на поиск в таблице символов.
Для типичной программы на встраиваемой системе с 10 тысячами символов это было неприемлемо. В таблице символов хранились имена переменных, имена функций и определения типов. В реализации использовалось красно-чёрное дерево — самобалансирующееся дерево двоичного поиска.
«У него O(log n); судя по учебникам, оно идеально подходит для этой цели», — сказал мой коллега.
Но профилировщик показывал иное...
Читать далее