Hoe wordt de efficiëntie van zoeken in een ongebalanceerde gegevensboom bepaald?

De efficiëntie van zoeken in een niet-gebalanceerde boom wordt bepaald door de diepte van de knoop waar het gezochte element zich bevindt. In het ergste geval, als de boom uitgroeit tot een lijst, wordt de zoektijd lineair — O(n). Gemiddeld hangt de efficiëntie af van de structuur van de boom en de verdeling van de gegevens. Voor beoordeling wordt meestal de hoogte van de boom gebruikt: hoe hoger de boom, hoe langer de zoektocht duurt. In Go kan de zoekfunctie in een binaire boom als volgt worden geïmplementeerd:

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

Als de boom niet gebalanceerd is, kan de diepte groot zijn, wat de efficiëntie vermindert.