Operação de busca em BST


As operações de busca na Árvore binária de busca - BST tende a ser mais eficiente, por exemplo em comparação na Árvore binária, porém isso só acontece quando a árvore esteja “bem montada”.

Abaixo um exemplo de uma árvore em “boa formação” (“bem montada”):

Na árvore acima, a busca da chave 10, por exemplo, são feitas apenas 2 comparações. Dessa forma, a complexidade da operação de busca nesse tipo de árvore é de , onde é a altura da BST.

Referências


Aula 2 - TAD Árvores Binárias e BST