Please enable JavaScript.
Coggle requires JavaScript to display documents.
Search Trees - Coggle Diagram
Search Trees
Rotação
Transformação local da raiz da subárvore para um node desbalanceado (+2 ou -2)
Transfere a raiz para o node desbalanceado mais próximo do local de inserção da nova folha
Single right (R-rotation)
Rotaciona o nó conectando a raiz e o ramo, deixando-o como a nova raiz com dois ramos.
Single left (L-rotation)
Oposto do R-rotation
Double left-right (LR-rotation)
Faz um L-rotation e depois uma R-rotation
Double right-left (RL-rotation)
Oposto do LR-rotation
Cuidado para manter a propriedades de uma árvore binária
AVL tree
O fator de balanceamento é a diferença de altura das subárvores da direita e da esquerda
Deve ser 0, 1 ou -1
Uma árvore vazia tem altura -1
Pior caso: θ(log n)
Difícil implementação
Deletar é mais difícil que inserir
Mesma eficiência
Eficiente, mas rotações constantes
Por isso não é usada para implementar Dicionários
Simplificar
Melhorar o pior caso
Manter a eficiência e a ordenação
Balancear a árvore
AVL tree
Diferença de altura dos nodes da direita e da esquerda não seja maior que 1.
Red-black tree
A altura de uma subárvore pode ser o dobro da outra
Mudar a representação
Mais de um elemento por Node
Maior eficiência temporal
Inserir e deletar
Caso médio: θ(log n)
Pior caso: θ(n)