Kuidas hinnata andmete otsingu tõhusust binaarses puu struktuuris?

Tõhusus otsingus binokadest puudest sõltub nende struktuurist. Tasakaalustatud binokadest otsingupuu (BST) keskmine otsinguaeg on O(log n), kus n on sõlmede arv, kuna igal sammul välistame järelejäänud elementide poole.

Kui puu ei ole tasakaalustatud (näiteks, muutub see nimekirjaks), võib otsinguaeg halveneda kuni O(n).

Hinnang näide:

• Parim ja keskmine juhtum: O(log n)
• Halvim juhtum: O(n)

Garantii efektiivsuse parandamiseks kasutatakse tasakaalustatud puid, näiteks AVL või punane-must puid.