Kuidas määrata ebavõrdses andmepuu otsingu tõhusust?

The efficiency of search in an unbalanced tree is determined by the depth of the node where the sought element is located. In the worst case, if the tree degenerates into a list, the search time becomes linear — O(n). On average, efficiency depends on the structure of the tree and data distribution. Usually, the height of the tree is used for assessment: the higher the tree, the longer the search. In Go, search in a binary tree can be implemented as follows:

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

If the tree is unbalanced, the depth can be large, which reduces efficiency.