Jak se určuje efektivita hledání v nerovnovážném stromu dat?

Efektivita vyhledávání v nevyváženém stromu je určena hloubkou uzlu, ve kterém se nachází hledaný prvek. V nejhorším případě, pokud se strom zvrhne v seznam, se doba hledání stává lineární — O(n). Průměrně závisí efektivita na struktuře stromu a rozložení dat. Pro odhad se obvykle používá výška stromu: čím vyšší je strom, tím déle trvá hledání. V Go lze vyhledávání v binárním stromu implementovat 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)
}

Pokud strom není vyvážený, může být hloubka velká, což snižuje efektivitu.