Cтраница 4
На рис. 15.5 показано большое DST-дерево, образованное случайными 7-разрядными ключами. Это дерево почти идеально сбалансировано. Использование DST-де-ревьев заманчиво во многих реальных приложениях, поскольку эти деревья обеспечивают практически оптимальную производительность даже при решении очень сложных задач, требуя лишь минимальных усилий на реализацию. Например, DST-дерево, построенное из 32-разрядных ключей ( или четырех 8-разрядных символов), гарантировано требует менее 32 сравнений, а DST-дерево, построенное из 64-разрядных ключей ( или восьми 8-разрядных символов), гарантировано требует менее 64 сравнений, даже при наличии миллионов ключей. Это свойство делает DST-деревья привлекательной альтернативой использованию сбалансированных деревьев для практической реализации функций search и insert в таблице символов, при условии наличия эффективного доступа к разрядам ключей. [46]