Uma árvore binária balanceada também é conhecida como árvore balanceada em altura. É definida como árvore binária quando a diferença entre a altura da subárvore esquerda e da subárvore direita não é maior que m, onde m é geralmente igual a 1. A altura de uma árvore é o número de arestas no caminho mais longo entre o nó raiz e o nó folha.
A árvore acima é uma árvore de pesquisa binária . Uma árvore de pesquisa binária é uma árvore na qual cada nó do lado esquerdo tem um valor menor que seu nó pai, e o nó do lado direito tem um valor maior que seu nó pai. Na árvore acima, n1 é um nó raiz e n4, n6, n7 são os nós folha. O nó n7 é o nó mais distante do nó raiz. O n4 e o n6 contêm 2 arestas e existem três arestas entre o nó raiz e o nó n7. Como n7 é o mais distante do nó raiz; portanto, a altura da árvore acima é 3.
Agora veremos se a árvore acima está balanceada ou não. A subárvore esquerda contém os nós n2, n4, n5 e n7, enquanto a subárvore direita contém os nós n3 e n6. A subárvore esquerda possui dois nós folha, ou seja, n4 e n7. Existe apenas uma aresta entre os nós n2 e n4 e duas arestas entre os nós n7 e n2; portanto, o nó n7 é o mais distante do nó raiz. A altura da subárvore esquerda é 2. A subárvore direita contém apenas um nó folha, ou seja, n6, e possui apenas uma aresta; portanto, a altura da subárvore direita é 1. A diferença entre as alturas da subárvore esquerda e da subárvore direita é 1. Como obtivemos o valor 1, podemos dizer que a árvore acima é uma árvore com equilíbrio de altura. Este processo de cálculo da diferença entre as alturas deve ser realizado para cada nó como n2, n3, n4, n5, n6 e n7. Quando processarmos cada nó, descobriremos que o valor de k não é superior a 1, então podemos dizer que a árvore acima é balanceada árvore binária .
Na árvore acima, n6, n4 e n3 são os nós folha, onde n6 é o nó mais distante do nó raiz. Existem três arestas entre o nó raiz e o nó folha; portanto, a altura da árvore acima é 3. Quando consideramos n1 como o nó raiz, então a subárvore esquerda contém os nós n2, n4, n5 e n6, enquanto a subárvore contém o nó n3. Na subárvore esquerda, n2 é um nó raiz e n4 e n6 são nós folha. Entre os nós n4 e n6, n6 é o nó mais distante de seu nó raiz e n6 tem duas arestas; portanto, a altura da subárvore esquerda é 2. A subárvore direita tem qualquer filho à sua esquerda e à direita; portanto, a altura da subárvore direita é 0. Como a altura da subárvore esquerda é 2 e a subárvore direita é 0, a diferença entre a altura da subárvore esquerda e da subárvore direita é 2. De acordo com a definição, a diferença entre a altura da subárvore esquerda e a subárvore direita não deve ser maior que 1. Nesse caso, a diferença passa a ser 2, que é maior que 1; portanto, a árvore binária acima é uma árvore de pesquisa binária desequilibrada.
Por que precisamos de uma árvore binária balanceada?
Vamos entender a necessidade de uma árvore binária balanceada através de um exemplo.
A árvore acima é uma árvore de pesquisa binária porque todos os nós da subárvore esquerda são menores que seu nó pai e todos os nós da subárvore direita são maiores que seu nó pai. Suponha que queremos encontrar o valor 79 na árvore acima. Primeiro, comparamos o valor do nó n1 com 79; como o valor de 79 não é igual a 35 e é maior que 35, passamos para o nó n3, ou seja, 48. Como o valor 79 não é igual a 48 e 79 é maior que 48, movemos para a direita filho de 48. O valor do filho direito do nó 48 é 79 que é igual ao valor a ser pesquisado. O número de saltos necessários para pesquisar um elemento 79 é 2 e o número máximo de saltos necessários para pesquisar qualquer elemento é 2. O caso médio para pesquisar um elemento é O (logn).
A árvore acima também é uma árvore de pesquisa binária porque todos os nós da subárvore esquerda são menores que seu nó pai e todos os nós da subárvore direita são maiores que seu nó pai. Suponha que queremos encontrar o valor 79 na árvore acima. Primeiro, comparamos o valor 79 com um nó n4, ou seja, 13. Como o valor 79 é maior que 13, passamos para o filho direito do nó 13, ou seja, n2 (21). O valor do nó n2 é 21, que é menor que 79, então movemos novamente para a direita do nó 21. O valor do filho direito do nó 21 é 29. Como o valor 79 é maior que 29, movemos para a direita filho do nó 29. O valor do filho direito do nó 29 é 35, que é menor que 79, então passamos para o filho direito do nó 35, ou seja, 48. O valor 79 é maior que 48, então passamos para o filho direito do nó 48. O valor do nó filho direito de 48 é 79, que é igual ao valor a ser pesquisado. Neste caso, o número de saltos necessários para pesquisar um elemento é 5. Neste caso, o pior caso é O(n).
Se o número de nós aumentar, a fórmula usada no diagrama de árvore1 é mais eficiente do que a fórmula usada no diagrama de árvore2. Suponha que o número de nós disponíveis em ambas as árvores acima seja 100.000. Para pesquisar qualquer elemento em um diagrama de árvore2, o tempo necessário é de 100.000 µs, enquanto o tempo necessário para pesquisar um elemento no diagrama de árvore é log(100.000), que é igual a 16,6 µs. Podemos observar a enorme diferença de tempo entre as duas árvores acima. Portanto, concluímos que a árvore binária de equilíbrio proporciona uma busca mais rápida do que a estrutura de dados em árvore linear.