Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores Balanceadas de Busca - Coggle Diagram
Árvores Balanceadas de Busca
Red Black Tree
Tolera a altura de uma subárvore sendo duas vezes maior que a outra subárvore do mesmo nó
Se a inserção ou exclusão de um nó resulta em uma árvore com o requisito de balanceamento violado
Reestrutura-se a árvore por transformações chamadas rotações que restauram o balanceamento necessário
Árvore AVL
O fator de equilíbrio de cada nó é a diferença entre as alturas das subárvores da esquerda e direita de cada nó, podende ele ser 0,+1 ou -1
Rotações
Transformações locais da subárvore com raiz em um nó cujo saldo se tornou +2 ou -2
Se houver vários desses nós, gira-se a árvore enraizada no nó desbalanceado que é o mais próximo da folha recém- inserida
Rotações simples
Rotação R (Rotação única à direita)
Realizada após uma nova chave ser inserida na subárvore esquerda do filho esquerdo cuja raiz tinha o saldo de +1 antes da inserção
Rotação L (Rotação Simples Simétrica à esquerda)
Imagens espelhadas da rotação R
Realizada após uma nova chave ser inserida na subárvore direita do filho direito cuja raiz tinha o saldo de -1 antes da inserção
Rotações Duplas
Rotação LR (Dupla rotação esquerda-direita)
Combinação de 2 rotações
Rotação L na subárvore da esquerda seguida pela rotação R
Realizada após uma nova chave ser inserida na subárvore direita do filho esquerdo cuja raiz tinha o saldo de +1 antes da inserção
Rotação RL (Dupla rotação direita-esquerda)
Imagem espelhada da Rotação RL
Realizada após uma nova chave ser inserida na subárvore esquerda do filho direito cuja raiz tinha o saldo de -1 antes da inserção
Não triviais
Tempo constante
Devem preservar requisitos básicos de uma árvore de balanceamento e de uma árvore de busca binária
Eficiência
Característica analisada
Altura das árvores
Limitada por funções logarítimicas
Operações de busca e inserção Θ(log n) no pior caso
Operação de exclusão de chaves é mais difiícil que a inserção, porém está na mesma classe logarítimica de eficiência da inserção
Pesquisa em uma árvore binária AVL
Requer quase o mesmo número de comparações que fazer busca binária em uma matriz ordenada
Desvantagens
Rotações frequentes
Necessidade de manter o balanceamento entre nós