Árvores binárias e Java TreeMap
Threads que viraram posts
Árvores binárias são estruturas usadas para organizar dados, onde cada nodo pode ser conectado com até outros dois nodos.
“O que isso quer dizer?”
Em árvores binárias de busca (binary search tree), quando adicionados nodos na árvore, eles já são colocados na posição correta, de forma a manter a árvore ordenada.
Por causa disso, na prática as buscas nesse tipo de árvore levam menos tempo para serem executadas.
Para fazer uma analogia: imagine que você está numa cidade batendo de porta em porta pra encontrar um endereço. A cada porta que você bate, alguém lhe diz qual é o próximo ponto de referência mais próximo do seu destino. Cada porta tem uma dica que fará chegar mais rápido.
“Isso serve pra alguma coisa além de me fazer se reprovade em entrevistas de FAANG?”
Um caso de uso simplificado poderia ser um sistema recebendo dados em batch (de arquivo de texto, chamadas REST, etc) onde informações precisam ser agrupadas e transformadas para no final serem exibidas de forma ordenada. Como não há garantia da ordem em que os eventos chegam, ir guardando os dados em árvore otimizaria a solução.
“E eu preciso implementar algo na mão pra usar árvores?”
Não necessariamente. TreeMap por exemplo é uma estrutura de dados em Java que implementa árvores binárias (mais especificamente red black trees) por trás.
Também é possível definir um comparator para sinalizar quais atributos de um objeto serão considerados na ordenação.
Big-O Notation
Comparação de performance entre árvores binárias de busca e arrays normais:
Referência para interpretação de Big-O Notation:
Fonte: https://bigocheatsheet.com
