Dengesiz bir veri ağacında arama verimliliği nasıl belirlenir?

Dengeli olmayan bir ağaçta arama verimliliği, aranan öğenin bulunduğu düğümün derinliği ile belirlenir. En kötü durumda, ağaç bir listeye dönüşürse, arama süresi doğrusal hale gelir — O(n). Ortalama olarak, verimlilik ağaç yapısına ve veri dağılımına bağlıdır. Değerlendirme için genellikle ağacın yüksekliği kullanılır: ne kadar yüksekse, arama o kadar uzun sürer. Go'da, ikili ağaçta aramayı şu şekilde uygulayabilirsiniz:

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

Ağaç dengeli değilse, derinlik büyük olabilir ve bu da verimliliği azaltır.