Cum se determină eficiența căutării într-un copac de date dezechilibrat?

Eficiența căutării într-un copac dezechilibrat este determinată de adâncimea nodului în care se află elementul căutat. În cel mai rău caz, dacă copacul se degenera într-o listă, timpul de căutare devine liniar — O(n). În medie, eficiența depinde de structura copacului și de distribuția datelor. Pentru evaluare, de obicei se folosește înălțimea copacului: cu cât copacul este mai înalt, cu atât căutarea durează mai mult. În Go, se poate implementa căutarea într-un copac binar astfel:

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

Dacă copacul nu este echilibrat, adâncimea poate fi mare, ceea ce reduce eficiența.