Kako se određuje efikasnost pretraživanja u neuravnoteženom stablu podataka?

Efikasnost pretraživanja u nebalansiranom stablu određuje dubina čvora u kojem se nalazi traženi element. U najgorem slučaju, ako se stablo pretvori u listu, vreme pretraživanja postaje linearno — O(n). U proseku, efikasnost zavisi od strukture stabla i rasporeda podataka. Za procenu se obično koristi visina stabla: što je više, to je duže pretraživanje. U Go, pretraživanje u binarnom stablu može se implementirati ovako:

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

Ako stablo nije uravnoteženo, dubina može biti velika, što smanjuje efikasnost.