Wie wird die Effizienz der Suche in einem unausgeglichenen Datensatzbaum bestimmt?

Die Effizienz der Suche in einem unausgeglichenen Baum wird durch die Tiefe des Knotens bestimmt, an dem sich das gesuchte Element befindet. Im schlimmsten Fall, wenn der Baum sich in eine Liste verwandelt, wird die Suchzeit linear — O(n). Im Durchschnitt hängt die Effizienz von der Struktur des Baumes und der Datenverteilung ab. Zur Bewertung wird üblicherweise die Höhe des Baumes verwendet: Je höher der Baum, desto länger dauert die Suche. In Go kann die Suche in einem binären Baum folgendermaßen implementiert werden:

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

Wenn der Baum unausgeglichen ist, kann die Tiefe groß sein, was die Effizienz verringert.