Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 9, c
(), g
(), g
(), ....., ....., ....., ....., ....., ...…
Mapa Mental 9
-
Árvores AVL
-
Rotações
Tipos
Rotação L
Quando a raiz (r) de uma (sub-) árvore fica desbalanceada por um elemento inserido na sub-árvore direita (Td) de seu filho direito (c)
-
Rotação LR
Quando uma raiz (r), que tinha um balanço de +1, fica desbalanceada por um elemento inserido na sub-árvore direita (Td) de seu filho esquerdo (c)
Será basicamente uma Rotação L na Te da raiz r, e depois uma Rotação R na nova árvore com a mesma raiz r (Obs.: O elemento inserido pode ser na Te ou na Td do nó g, mas não importa, pois o processo será o mesmo)
-
Rotação RL
Quando uma raiz (r), que tinha um balanço de -1, fica desbalanceada por um elemento inserido na sub-árvore direita (Td) de seu filho esquerdo (c)
(É a versão espelhada da Rotação LR, você faz a R primeiro e depois a L)
Rotação R
A sub-árvore direita (Td) de c agora será a Te da raiz r, a nova Td de c então será a sub-árvore r, ou seja, o filho esquerdo será agora o pai de r (que não é mais a raiz, e sim c)
-
Quando a raíz (r) de uma (sub-) árvore fica desbalanceada por um elemento inserido na sub-árvore esquerda (Te) de seu filho esquerdo (c)
Quando uma árvore AVL se torna desbalanceada durante a inserção de um novo elemento, é feito uma rotação para se rebalancear, o seu tipo irá depender de onde o novo nó foi inserido
Essas rotações, além de balancear a árvore, ela também preserva a ordenação requerida dos nós, para que ela continue sendo considerada uma BST
-
O balanceamento das árvores faz com que as operações de busca e inserção tenham uma eficiência de Θ(log n) no pior caso. Enquanto a de remoção tem a eficiência de caso médio Θ(log n)
Porém sua eficiência geral é prejudicada por causa dessas mesmas rotações, já que precisam ser realizadas constantemente, repetidas vezes
-
-
-
-
-
-
-
-
-
-
-