Antes de entender o Árvore Rubro-Negra e árvore AVL diferenças, devemos saber sobre a árvore Vermelho-Preta e a árvore AVL separadamente.
O que é uma árvore rubro-negra?
A árvore rubro-negra é auto-equilibrada árvore de pesquisa binária em que cada nó contém um bit extra de informação que denota a cor do nó. A cor do nó pode ser vermelha ou preta, dependendo da informação de bit armazenada pelo nó.
Propriedades
A seguir estão as propriedades associadas a uma árvore Vermelho-Preta:
- O nó raiz da árvore deve ser preto.
- Um nó vermelho só pode ter filhos negros. Ou podemos dizer que dois nós adjacentes não podem ser da cor vermelha.
- Se o nó não tiver um filho esquerdo ou direito, então esse nó é considerado um nó folha. Então, colocamos os filhos esquerdo e direito abaixo do nó folha conhecido como nada
A profundidade ou altura do preto de um nó folha pode ser definida como o número de preto que encontramos quando passamos do nó folha para o nó raiz. Uma das principais propriedades da árvore Vermelho-Preto é que cada nó folha deve ter a mesma profundidade de preto.
Vamos entender essa propriedade através de um exemplo.
Na árvore acima, existem cinco nós, em que um é vermelho e os outros quatro nós são pretos. Existem três nós folha na árvore acima. Agora calculamos a profundidade preta de cada nó folha. Como podemos observar que a profundidade preta de todos os três nós folhas é 2; portanto, é uma árvore rubro-negra.
0,2 como uma fração
Se a árvore não obedecer a nenhuma das três propriedades acima, então não é uma árvore Rubro-Negra.
Altura de uma árvore rubro-negra
Considere h como a altura da árvore com n nós. Qual seria o menor valor de n?. O valor de n é o menor quando todos os nós são pretos. Se a árvore contiver todos os nós pretos, então a árvore será uma árvore binária completa. Se a altura de uma árvore binária completa for h, então o número de nós em uma árvore será:
n = 2h -1
Qual seria o maior valor de n?
O valor de n é maior quando cada nó preto tem dois filhos vermelhos, mas o nó vermelho não pode ter filhos vermelhos, portanto terá filhos pretos. Desta forma, existem camadas alternadas de crianças pretas e vermelhas. Portanto, se o número de camadas pretas for h, então o número de camadas vermelhas também será h; portanto, a altura total da árvore passa a ser 2h. O número total de nós é:
n = 2*2h-1
Qual é a árvore AVL?
Um Árvore AVL é uma árvore de pesquisa binária com autoequilíbrio se observarmos o caso abaixo, que é uma árvore de pesquisa binária e uma árvore balanceada.
Na árvore acima, a complexidade de tempo do pior caso para pesquisar um elemento é O(h), ou seja, a altura da árvore. No caso acima, o número de comparações feitas para pesquisar o elemento 17 é 4, e a altura da árvore também é 4.
Se considerarmos a árvore binária distorcida, conforme mostrado abaixo:
Na árvore distorcida à direita acima, o número de comparações feitas para pesquisar 17 elementos é 5, e o número de elementos presentes na árvore também é 5. Portanto, podemos dizer que se a árvore for uma árvore binária distorcida então a complexidade do tempo seria O (n).
Agora, temos que equilibrar essas árvores distorcidas para que tenham complexidade de tempo O(h). Existe um termo conhecido como fator de equilíbrio , que é usado para autoequilibrar a árvore de pesquisa binária. O fator de equilíbrio pode ser calculado como:
Fator de equilíbrio = altura da subárvore esquerda-altura da subárvore direitaO valor do fator de equilíbrio pode ser 1, 0 ou -1. Se cada nó na árvore binária tiver um valor de 1, 0 ou -1, então essa árvore é considerada balanceada. árvore binária ou árvore AVL.
A árvore é conhecida como uma árvore perfeitamente balanceada se o fator de equilíbrio de cada nó for 0. A árvore AVL é uma árvore quase balanceada porque cada nó da árvore tem o valor do fator de equilíbrio 1, 0 ou -1.
Diferenças entre a árvore Rubro-Negra e a árvore AVL.
A seguir estão as diferenças entre a árvore Vermelho-Preta e a árvore AVL:
A árvore Vermelho-Preta é uma árvore de pesquisa binária e a árvore AVL também é uma árvore de pesquisa binária.
As seguintes regras são aplicadas em uma Árvore Rubro-Negra:
- O nó em uma árvore Vermelho-Preto é vermelho ou preto.
- A cor do nó raiz deve ser preta.
- Os nós adjacentes não devem ser vermelhos. Em outras palavras, podemos dizer que o nó vermelho não pode ter filhos vermelhos, mas o nó preto pode ter filhos pretos.
- Deve haver o mesmo número de nós pretos em cada caminho; então, apenas uma árvore pode ser considerada uma árvore rubro-negra.
- Os nós externos são os nós nulos, que são sempre de cor preta.
Regra da árvore AVL:
Cada nó deve ter o fator de equilíbrio como -1, 0 ou 1.
Na figura acima, precisamos verificar se a árvore é rubro-negra ou não. Para verificar isso, primeiro precisamos verificar se a árvore é uma árvore de pesquisa binária ou não. Como podemos observar na figura acima que ela satisfaz todas as propriedades da árvore binária de busca; portanto, é uma árvore de pesquisa binária. Em segundo lugar, temos de verificar se cumpre ou não as regras acima referidas. A árvore acima satisfaz todas as cinco regras acima; portanto, conclui que a árvore acima é uma árvore Rubro-Negra.
Na figura acima, precisamos verificar se a árvore é AVL ou não. Como cada nó tem um valor de fator de equilíbrio como -1, 0 ou 1, então é uma árvore AVL.
No caso de uma árvore Rubro-Negra, se todas as regras acima forem satisfeitas, desde que a árvore seja uma árvore de busca binária, então a árvore é considerada uma árvore Rubro-Negra.
No caso da árvore AVL, se o fator de equilíbrio for -1, 0 ou 1, então a árvore acima é considerada uma árvore AVL.
Se a árvore não estiver balanceada, duas ferramentas serão usadas para balancear a árvore em uma árvore Rubro-Preta:
Se a árvore não estiver balanceada, uma ferramenta será usada para balancear a árvore na árvore AVL:
No caso da árvore Rubro-Negra, as operações de inserção e exclusão são eficientes. Se a árvore ficar balanceada por meio da recoloração, as operações de inserção e exclusão serão eficientes na árvore Vermelho-Preta.
No caso da árvore AVL, a operação de busca é eficiente, pois requer apenas uma ferramenta para equilibrar a árvore.
No caso da árvore Vermelho-Preta, a complexidade de tempo para todas as operações, ou seja, inserção, exclusão e pesquisa é O(logn).
No caso da árvore AVL, a complexidade de tempo para todas as operações, ou seja, inserção, exclusão e pesquisa é O(logn).
Vamos entender as diferenças na forma tabular.
| Parâmetro | Árvore Vermelha Negra | Árvore AVL |
|---|---|---|
| Procurando | A árvore Red Black não fornece uma pesquisa eficiente, pois as Red Black Trees são aproximadamente equilibradas. | As árvores AVL fornecem uma pesquisa eficiente, pois são árvores estritamente balanceadas. |
| Inserção e exclusão | A inserção e exclusão são mais fáceis na árvore Red Black, pois requer menos rotações para equilibrar a árvore. | A inserção e a exclusão são complexas na árvore AVL, pois requerem múltiplas rotações para equilibrar a árvore. |
| Cor do nó | Na árvore Vermelho-Preto, a cor do nó é Vermelho ou Preto. | No caso das árvores AVL, não existe cor do nó. |
| Fator de equilíbrio | Não contém nenhum fator de equilíbrio. Ele armazena apenas um bit de informação que denota a cor vermelha ou preta do nó. | Cada nó possui um fator de equilíbrio na árvore AVL cujo valor pode ser 1, 0 ou -1. Requer espaço extra para armazenar o fator de equilíbrio por nó. |
| Estritamente equilibrado | As árvores rubro-negras não são estritamente equilibradas. | As árvores AVL são estritamente balanceadas, ou seja, a altura da subárvore esquerda e a altura da subárvore direita diferem em no máximo 1. |