[Перевод] Структуры данных на практике. Глава 9: Двоичные деревья поиска

Катастрофа с красно-чёрным деревом

Компилятор тратил 60% времени на поиск символов. Не на парсинг, не на генерацию кода, просто на поиск в таблице символов.

Для типичной программы на встраиваемой системе с 10 тысячами символов это было неприемлемо. В таблице символов хранились имена переменных, имена функций и определения типов. В реализации использовалось красно-чёрное дерево — самобалансирующееся дерево двоичного поиска.

«У него O(log n); судя по учебникам, оно идеально подходит для этой цели», — сказал мой коллега.

Но профилировщик показывал иное...

Читать далее