Noto'g'li ma'lumotlar daraxtida qidiruv samaradorligi qanday aniqlanadi?

Noto'g'ri balanslangan daraxtda qidiruv samaradorligi qidirilayotgan element joylashgan tugunning chuqurligi bilan belgilanadi. Eng yomon holatda, agar daraxt ro'yxatga aylansa, qidiruv vaqti chiziqli bo'lib, — O(n). O'rtacha holatda, samaradorlik daraxt tuzilishi va ma'lumotlarning taqsimlanishiga bog'liq. Baholash uchun odatda daraxtning balandligi ishlatiladi: balandroq daraxt, qidiruv uzoqroq davom etadi. Go tilida, ikkilamchi daraxtda qidiruvni quyidagicha amalga oshirish mumkin:

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

Agar daraxt muvozanatli bo'lmasa, chuqurlik katta bo'lishi mumkin, bu esa samaradorlikni pasaytiradi.