Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Trees - Coggle Diagram
Balanced Search Trees
AVL trees
left - right = -1, +1, ou 0
OBS: árvore vazia = -1
insertion
usamos "rotation"(rotação) para rebalancear a árvore
tipos de rotção
single right rotation / R-rotation
rodamos o nó mais próximo ao nó desbalanceado(no lado correspondente ao que foi inserido) para direita
single left rotation / L-rotation
rodamos o nó mais próximo ao nó desbalanceado(no lado correspondente ao que foi inserido) para esquerda
double left-right rotation / LR - rotation
fazemos um L-rotation na subárvore da esquerda e R-rotation na nova árvore
double right-left rotation / RL - rotation
fazemos um R-rotation na subárvore da direita e L-rotation na nova árvore
worst case degeneration
1.self balancing
balancear a árvore novamente por meio de rotações
2.allow more elements
permitir mais de um elemento no nó
eficiência
searching and insertion
worst case = O(logn)
OBS: +- a mesma eficiência da busca binária