Алгоритмы и структуры данных. Извлечение информации на языке Java

172

Глава 13. Бинарное дерево поиска

Самобалансирующиеся деревья

Существует два решения описанной проблемы:



избежать добавления ключей в Map по порядку (но это

не всегда возможно);



создать дерево, которое будет лучше обрабатывать ключи,

заданные по порядку.

Второе решение лучше, и есть несколько способов его реали-

зации. Наиболее распространенным является такое изменение

метода put, чтобы он обнаруживал, когда дерево становится

несбалансированным, и в этом случае перестраивал вершины.

Деревья с такой возможностью называются самобалансиру-

ющимися. Обычно используются такие деревья с самобаланси-

ровкой, как дерево АВЛ (АВЛ — это инициалы изобретателей),

и красно-черное дерево, на основе которого реализован класс

TreeMap в Java.

В нашем примере ...