Чӣ тавр муайян кардани самаранокии ҷустуҷӯ дар дарахти маълумоти номутавозин?

Самаранокии ҷустуҷӯ дар дарахти номувозанат бо дарозии ҳуҷайрае, ки унсури ҷустуҷӯӣ дар он ҷойгир аст, муайян карда мешавад. Дар ҳолати бадтарин, агар дарахт ба рӯйхат табдил ёбад, вақти ҷустуҷӯ ба сатҳи хаттӣ — 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)
}

Агар дарахт номувозанат бошад, метавонад дароз бошад, ки самаранокиро кам мекунад.