Antes de saber sobre as diferenças entre a árvore de pesquisa binária e a árvore AVL, devemos saber sobre a árvore de pesquisa binária e a árvore AVL separadamente.
O que é uma árvore de pesquisa binária?
O árvore de pesquisa binária é um árvore árvore binária. Como sabemos, essa árvore pode ter 'n' número de filhos, enquanto; a árvore binária pode conter no máximo dois filhos. Portanto, a restrição de uma árvore binária também é seguida pela árvore binária de busca. Cada nó em uma árvore de pesquisa binária deve ter no máximo dois filhos; em outras palavras, podemos dizer que a árvore binária de busca é uma variante da árvore binária.
A árvore de pesquisa binária também segue as propriedades da pesquisa binária. Na pesquisa binária, todos os elementos de um array devem estar em ordem de classificação. Calculamos o elemento do meio na pesquisa binária em que a parte esquerda do elemento do meio contém o valor menor que o valor do meio, e a parte direita do elemento do meio contém os valores maiores que o valor do meio.
Na árvore de pesquisa binária, o elemento do meio se torna o nó raiz, a parte direita se torna a subárvore direita e a parte esquerda se torna a subárvore esquerda. Portanto, podemos dizer que a árvore binária de busca é uma combinação de um árvore binária e pesquisa binária .
Nota: A árvore de pesquisa binária pode ser definida como a árvore binária em que todos os elementos da subárvore esquerda são menores que o nó raiz e todos os elementos da subárvore direita são maiores que o nó raiz.
Complexidade de tempo na árvore de pesquisa binária
Se a árvore de busca binária for quase uma árvore balanceada então todas as operações terão uma complexidade de tempo de O(logn) porque a pesquisa é dividida na subárvore esquerda ou direita.
transmissão de mídia
Se a árvore de pesquisa binária estiver inclinada para a esquerda ou para a direita, então todas as operações terão a complexidade de tempo de Sobre) porque precisamos percorrer até os n elementos.
O que é a árvore AVL?
Um Árvore AVL é uma árvore de pesquisa binária com autoequilíbrio onde a diferença entre as alturas das subárvores esquerda e direita não pode ser maior que um. Essa diferença é conhecida como fator de equilíbrio. Na árvore AVL, os valores do fator de equilíbrio podem ser -1, 0 ou 1.
Como acontece o autoequilíbrio da árvore de busca binária?
Como sabemos, a árvore AVL é uma árvore de pesquisa binária com autoequilíbrio. Se a árvore de pesquisa binária não estiver balanceada, ela poderá ser autobalanceada com alguns rearranjos. Esses rearranjos podem ser feitos usando algumas rotações.
Vamos entender o autoequilíbrio por meio de um exemplo.
Suponha que queremos inserir 10, 20, 30 em uma árvore AVL.
A seguir estão as maneiras de inserir 10, 20, 30 em uma árvore AVL:
árvore avl
Passo 1: Primeiro, criamos uma árvore de pesquisa binária, conforme mostrado abaixo:
Passo 2: Na figura acima, podemos observar que a árvore está desequilibrada porque o fator de equilíbrio do nó 30 é 2. Para torná-la uma árvore AVL, precisamos realizar algumas rotações. Se realizarmos a rotação para a direita no nó 20, o nó 30 se moverá para baixo, enquanto o nó 20 se moverá para cima, conforme mostrado abaixo:
Como podemos observar, a árvore final segue a propriedade da árvore de Pesquisa Binária e de uma árvore balanceada; portanto, é uma árvore AVL.
No caso, a árvore estava deixou a árvore desequilibrada, então realizamos a rotação correta no nó.
Passo 1: Primeiro criamos uma árvore de pesquisa binária conforme mostrado abaixo:
Passo 2: Na figura acima, podemos observar que a árvore está desequilibrada porque o fator de equilíbrio do nó 10 é -2. Para torná-la uma árvore AVL, precisamos realizar algumas rotações. É uma árvore desequilibrada para a direita, então realizaremos rotação para a esquerda. Se realizarmos rotação para a esquerda no nó 20, então o nó 20 se moverá para cima e o nó 10 se moverá para baixo, conforme mostrado abaixo:
teclas modificadoras
Como podemos observar, a árvore final segue a propriedade do Árvore de pesquisa binária e um árvore equilibrada ; portanto, é uma árvore AVL.
Passo 1: Primeiro criamos a árvore de pesquisa binária conforme mostrado abaixo:
Passo 2: Na figura acima, podemos observar que a árvore está desequilibrada porque o fator de equilíbrio do nó raiz é 2. Para torná-la uma árvore AVL, precisamos realizar algumas rotações. O cenário acima é desequilibrado esquerda-direita, pois um nó está à esquerda de seu nó pai e outro está à direita de seu nó pai. Primeiro, realizaremos a rotação para a esquerda, e a rotação acontecerá entre os nós 10 e 20. Após a rotação para a esquerda, 20 se moverá para cima e 10 se moverá para baixo, conforme mostrado abaixo:
Ainda assim, a árvore está desequilibrada, então realizamos a rotação correta na árvore. Depois que a rotação correta for realizada na árvore, a árvore ficará como mostrado abaixo:
Como podemos observar na árvore acima, a árvore segue a propriedade da árvore de Pesquisa Binária e de uma árvore balanceada; portanto, é uma árvore AVL.
Passo 1: Primeiro, criamos a árvore de Pesquisa Binária, conforme mostrado abaixo:
Passo 2: Na figura acima, podemos observar que a árvore está desequilibrada porque o fator de equilíbrio do nó raiz é 2. Para torná-la uma árvore AVL, precisamos realizar algumas rotações. O cenário acima é desequilibrado direita-esquerda, pois um nó está à direita de seu nó pai e outro nó está à esquerda de seu nó pai. Primeiro, realizaremos a rotação para a direita que acontece entre os nós 30 e 20. Após a rotação para a direita, 20 se moverá para cima e 30 se moverá para baixo, conforme mostrado abaixo:
Ainda assim, a árvore acima está desequilibrada, então precisamos realizar a rotação para a esquerda no nó. Assim que a rotação para a esquerda for executada, o nó 20 se moverá para cima e o nó 10 se moverá para baixo, conforme mostrado abaixo:
Como podemos observar na árvore acima, a árvore segue a propriedade da árvore de Pesquisa Binária e de uma árvore balanceada; portanto, é uma árvore AVL.
Diferenças entre a árvore de pesquisa binária e a árvore AVL
| Árvore de pesquisa binária | Árvore AVL |
|---|---|
| Toda árvore de pesquisa binária é uma árvore binária porque ambas as árvores contêm no máximo dois filhos. | Cada árvore AVL também é uma árvore binária porque a árvore AVL também tem no máximo dois filhos. |
| No BST não existe termo, como fator de equilíbrio. | Na árvore AVL, cada nó contém um fator de equilíbrio e o valor do fator de equilíbrio deve ser -1, 0 ou 1. |
| Toda árvore de pesquisa binária não é uma árvore AVL porque o BST pode ser uma árvore balanceada ou não balanceada. | Cada árvore AVL é uma árvore de pesquisa binária porque a árvore AVL segue a propriedade do BST. |
| Cada nó na árvore de pesquisa binária consiste em três campos, ou seja, subárvore esquerda, valor do nó e subárvore direita. | Cada nó na árvore AVL consiste em quatro campos, ou seja, subárvore esquerda, valor do nó, subárvore direita e fator de equilíbrio. |
| No caso da árvore de Pesquisa Binária, se quisermos inserir algum nó na árvore então comparamos o valor do nó com o valor da raiz; se o valor do nó for maior que o valor do nó raiz, então o nó será inserido na subárvore direita, caso contrário, o nó será inserido na subárvore esquerda. Uma vez inserido o nó, não há necessidade de verificação do fator de equilíbrio de altura para que a inserção seja concluída. | No caso da árvore AVL, primeiro encontraremos o local adequado para inserir o nó. Uma vez inserido o nó, calcularemos o fator de equilíbrio de cada nó. Se o fator de equilíbrio de cada nó for satisfeito, a inserção será concluída. Se o fator de equilíbrio for maior que 1, precisaremos realizar algumas rotações para equilibrar a árvore. |
| Na árvore de pesquisa binária, a altura ou profundidade da árvore é O(n), onde n é o número de nós na árvore de pesquisa binária. | Na árvore AVL, a altura ou profundidade da árvore é O(logn). |
| É simples de implementar pois temos que seguir as propriedades da Pesquisa Binária para inserir o nó. | É complexo de implementar porque na árvore AVL, temos que primeiro construir a árvore AVL e depois verificar o equilíbrio de altura. Se a altura estiver desequilibrada, precisamos realizar algumas rotações para equilibrar a árvore. |
| A BST não é uma árvore balanceada porque não segue o conceito de fator de equilíbrio. | A árvore AVL é uma árvore balanceada em altura porque segue o conceito do fator de equilíbrio. |
| A pesquisa é ineficiente no BST quando há um grande número de nós disponíveis na árvore porque a altura não está balanceada. | A pesquisa é eficiente na árvore AVL mesmo quando há um grande número de nós na árvore porque a altura é balanceada. |