Как се определя ефективността на търсенето в неравновесено дърво с данни?

Ефективността на търсенето в небалансирано дърво се определя от дълбочината на възела, в който се намира търсеният елемент. В най-лошия случай, ако дървото се превърне в списък, времето за търсене става линейно — O(n). Средно ефективността зависи от структурата на дървото и разпределението на данните. За оценка обикновено се използва височината на дървото: колкото по-високо е, толкова по-дълго е търсенето. В Go, търсенето в двоично дърво може да се реализира по следния начин:

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

Ако дървото не е балансирано, дълбочината може да бъде голяма, което намалява ефективността.