Java-s TreeMap on rakendatud punase-musta puu alusel, mis on tasakaalustatud binaarne otsingupuu. Elementi asukoha määramiseks (näiteks sisestamisel või otsimisel) kasutatakse binaarset otsingut võtmete järgi, võrreldes võtmeid puu praeguste sõlmedega.

TreeMap operatsioonide otsingu, sisestamise ja kustutamise ajakompleksus on O(log n), kus n on kaardi elementide arv. Seda saavutatakse puu tasakaalustamisega, mis tagab, et puu kõrgus on proportsionaalne elementide arvuga logaritmiliselt.

Eelmine Edasi