Please enable JavaScript.
Coggle requires JavaScript to display documents.
218-223 Balanced Search Trees - Coggle Diagram
218-223 Balanced Search Trees
Esforços para encontrar uma estrutura que mantenha as boas propriedades de uma clássica binary search tree resultarem em duas abordagens
Instance-simplification variety
É definida como uma desbalanceada binary search tree que passa a ser balanceada, por isso são chamadas de
self-balancing
Numa
red-black tree
é tolerado que altura de uma subtree seja o dobro de outra subtree em um mesmo nodo
Se a inserção ou remoção de um novo nodo cria uma tree com um balanço diferente do requisitado a tree é reestruturada por uma familia de especiais transformações chamada
rotations
que restauram o balanço requisitado
AVL tree
Numa
AVL tree
a diferença nas alturas das subtrees direta e esquerda em cada nodo nunca devem ultrapassar 1
É uma binary search tree na qual o fator de balanço de cada nodo é a diferença entre as alturas das subtrees da esquerda e da direita do nodo. Os valores do fator de balanço podem ser 0 ou 1 ou -1
A rotation(rotação) de uma AVL acontece quando o balanço de um nodo chega em 2 ou -2, a subtree é transformada faz-se uma rotação da arvore enraizada no nodo desbalanceado
Single right rotation
É realizada após uma nova chave ser inserida no subárvore esquerda do filho esquerdo de uma árvore cuja raiz tinha o saldo de +1 antes do inserção.
Single left rotation
É executado após uma nova chave ser inserida na subárvore direita do filho certo de uma árvore cuja raiz tinha o saldo de -1 antes da inserção.
Double left-right rotation
Uma combinação de duas rotações: realizamos a rotation L da subárvore esquerda da raiz r seguida pela rotation R da nova árvore enraizada em r. É executado após uma nova chave ser inserida na subárvore direita de o filho esquerdo de uma árvore cuja raiz tinha o saldo de +1 antes da inserção.
As rotações não são transformações triviais, embora felizmente podem ser feitas em tempo constante. Eles não devem apenas garantir que uma árvore resultante seja
balanceada, mas também devem preservar os requisitos básicos de uma binary search tree.
Representation-change variety
Permite-se mais de um elemento em um nodo de uma search tree
Casos específicos
2-3 trees
2-3-4
trees
B-trees
Se diferenciam entre si pelo numero de elementos admissíveis em um singular nodo de uma search tree, mas todos perfeitamente balanceados