Ako sa určuje efektívnosť vyhľadávania v nerovnovážnom strome dát?

Efektivita vyhľadávania v nevyváženom strome je určená hĺbkou uzla, v ktorom sa nachádza hľadaný prvok. V najhoršom prípade, ak sa strom zvrhne na zoznam, sa čas vyhľadávania stáva lineárnym — O(n). Priemerná efektivita závisí od štruktúry stromu a rozdelenia dát. Na odhad sa zvyčajne používa výška stromu: čím vyšší je strom, tým dlhšie trvá vyhľadávanie. V Go sa vyhľadávanie v binárnom strome dá implementovať takto:

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)
}

Ak strom nie je vyvážený, môže byť hlboký, čo znižuje efektívnosť.