Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores AVL, 2 (1, 3), 3 (4, 2), 5 (4, 6), 3 (2), 3 (2), 3 (2), 4 (2), 4…
Árvores AVL
Árvores AVL são árvores em que se pretende manter sempre seu balanceamento, a fim de evitar que o pior caso de uma BST ocorra
Queremos evitar o caso em que a BST se torna uma lista, e operações se tornem tempo n
Para isso, foi desenvolvido o conceito de árvores que se balanceiam à medida em que novos nós são adicionados
Para conseguirmos manter o bom tempo de inserção e remoção na BST, utilizamos a ideia de "fator de balanceamento", o qual cada nó possui um
O fator de balanceamento é definido como a diferença entre a altura da subárvore esquerda e da subárvore direita de um determinado nó
Para manter as boas propriedades de uma BST, foi definido que esse fator deve ser de -1, 0 ou +1
Ao inserir um novo nó, deveremos, ao voltar da recursão, verificar os fatores de balanceamento de cada nó. Se for -2 ou +2, precisamos consertar
Para consertar o balanceamento de uma árvore AVL, utilizamos os conceitos de rotação
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-