Πώς καθορίζεται η αποδοτικότητα της αναζήτησης σε ένα μη ισορροπημένο δέντρο δεδομένων;

Η αποτελεσματικότητα της αναζήτησης σε ένα μη ισορροπημένο δέντρο καθορίζεται από το βάθος του κόμβου όπου βρίσκεται το ζητούμενο στοιχείο. Στην χειρότερη περίπτωση, αν το δέντρο εξελιχθεί σε λίστα, ο χρόνος αναζήτησης γίνεται γραμμικός — 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)
}

Αν το δέντρο δεν είναι ισορροπημένο, το βάθος μπορεί να είναι μεγάλο, κάτι που μειώνει την αποτελεσματικότητα.