Kaip nustatyti nesubalansuoto duomenų medžio paieškos efektyvumą?

Nepasvertas medžio paieškos efektyvumas yra nustatomas pagal mazgo, kuriame yra ieškomas elementas, gylį. Blogiausiu atveju, jei medis virsta sąrašu, paieškos laikas tampa linijinis — O(n). Vidutiniškai efektyvumas priklauso nuo medžio struktūros ir duomenų pasiskirstymo. Vertinimui dažnai naudojama medžio aukštis: kuo aukštesnis medis, tuo ilgiau trunka paieška. Go kalboje paieška dvejetainiame medyje gali būti įgyvendinta taip:

func search(node *Node, key int) *Node {
    if node == nil || node.key == key {
        return node
    }
    if key < node.key {
        return search(node.left, key)
    }
    return search(node.right, key)
}

Jei medis nėra subalansuotas, gylis gali būti didelis, kas mažina efektyvumą.