Hogyan határozzuk meg a keresés hatékonyságát egy kiegyensúlyozatlan adatfában?

A kiegyensúlyozatlan fa keresési hatékonyságát a keresett elem helyén lévő csomópont mélysége határozza meg. A legrosszabb esetben, ha a fa listává degenerálódik, a keresési idő lineáris lesz — O(n). Átlagosan a hatékonyság a fa szerkezetétől és az adatok eloszlásától függ. Általában a fa magasságát használják értékelésre: minél magasabb a fa, annál hosszabb a keresés. Go-ban a bináris fa keresése így valósítható meg:

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

Ha a fa nincs kiegyensúlyozva, a mélység nagy lehet, ami csökkenti a hatékonyságot.