Altura em árvores
Toda árvore possui uma altura (tree height), definida pelo caminho mais longo do nó raiz até uma das folhas.
Note
Uma machete para saber a altura da árvore, basta contar o número de arestas no caminho mais longo da raiz até uma das folhas.
Se uma árvore tem apenas um nó, a raiz, então sua altura é 0.
Se uma árvore é vazia, sua altura é -1.
Note
Quanto menor a altura da árvore, mais eficiente é a operação de busca na mesma.
Exemplo de implementação em Java:
class TreeNode {
int value;
TreeNode left, right;
TreeNode(int item) {
value = item;
left = right = null;
}
}
class BinaryTree {
TreeNode root;
int getHeight(TreeNode node) {
if (node == null) {
return -1;
}
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
int getHeight() {
return getHeight(root);
}
}