Aula 12: Árvores e árvores de busca binária
Pense em uma árvore genealógica, ou pastas dentro de pastas: algo 'no topo' se ramifica em itens 'abaixo'. Isso é uma 'árvore' — cada ponto é um 'nó'. Em uma 'árvore de busca binária' (BST), todo nó tem valores menores à esquerda e maiores à direita — exatamente como procurar uma palavra no dicionár
Uma BST é como procurar uma palavra no dicionário: você abre no meio, e se a palavra vem 'antes' você pula a metade direita inteira de uma vez. Cada comparação economiza metade do trabalho — mas só se as páginas forem divididas igualmente.
- classe
- Um molde para uma caixinha com campos. class TreeNode define uma caixa com três campos: val (o valor) e left/right (os filhos). TreeNode(5) cria uma caixa dessas, e self simplesmente significa "esta caixa" (a mesma ideia da aula de listas encadeadas).
- árvore de busca binária
- Uma árvore binária em que, para cada nó, todos os valores na subárvore esquerda são menores e todos os valores na subárvore direita são maiores.
- percurso em árvore
- Visitar todos os nós de uma árvore em uma ordem definida. Inorder (esquerda, nó, direita) em uma BST produz os valores ordenados.
- árvore balanceada
- Uma árvore cuja altura é cerca de log n, de modo que a busca leva O(log n). Uma árvore distorcida (skewed) perde essa vantagem e chega a O(n).
