Jak określić efektywność wyszukiwania w niezbalansowanym drzewie danych?

Wydajność wyszukiwania w niezbalansowanym drzewie jest określana przez głębokość węzła, w którym znajduje się poszukiwany element. W najgorszym przypadku, gdy drzewo przekształca się w listę, czas wyszukiwania staje się liniowy — O(n). Średnio wydajność zależy od struktury drzewa i rozkładu danych. Do oceny zwykle używa się wysokości drzewa: im wyższe drzewo, tym dłużej trwa wyszukiwanie. W Go można zaimplementować wyszukiwanie w drzewie binarnym tak:

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

Jeśli drzewo jest niezbalansowane, głębokość może być duża, co obniża wydajność.