1 Uma árvore é uma estrutura tipicamente recursiva. Nós vimos um algoritmo iterativo para realizar busca. Porque não utilizar um algoritmo recursivo para a busca em uma árvore binária de busca?
Para algoritmos de busca, é mais eficiente utilizar soluçoes iterativas pois a complexidade de espaço (memória total ocupada) será menor.
2 Elabore um algoritmo recursivo para efetuar uma busca em uma árvore binária de busca pressupondo as estruturas de dados do exemplo anterior.
Verificar métodos "search" e "searchRecursively" no arquivo "binarcy_search_tree.py".
3 Existe alguma razão para evitarmos algoritmos de busca em árvore recursivos (memória, complexidade, etc)? Justifique.
Sim, pois como já foi dito na primeira questao, a total de memória consumida nos algoritmo recursivos é maior do que nos algoritmos iterativos, fazendo com que esses sejam mais eficientes.
4 O algoritmo recursivo de inserção em árvore binária de busca apresentado é bastante simples e reflete bem a estrutura da própria árvore. Não será possível também realizar a função deste algoritmo com um algoritmo iterativo? Crie um algoritmo iterativo para a inserção simples em uma árvore binária de busca.
Sim, é possivel utilizar um algoritmo iterativo. Verificar método "insertIteratively" no arquivo "binary_search_tree.py".
https://docs.google.com/document/d/1V2LnDodQZ3oWeqx-oGcu1-kFg8CVzwYsLorh9FRVLUo/edit?usp=sharing