Please enable JavaScript.

Coggle requires JavaScript to display documents.

Balanced Search Trees - Coggle Diagram

- - - - Uma busca binária de árvore desbalanceada é transfoma a árvore em balanceada, por conta disso, essas tree são chamadas de auto-balanceadas.
        
        Diferentes implementações dessas ideia diferem no que é a definição de ponto de equilíbrio.
        
        Caso uma inserção / deletação de um nó acabe com o equilíbrio da tree, uma família de requerimentos especiais faz uma estruturação da tree a fim de trazer de volta o equilíbrio, essa família de transformações especiais é chamada de rotações.
        
        Estudaremos no caso das AVL tree
        
        Uma AVL tree requer que nunca a diferença de altura das subtree(left and right) supere 1.
        
        Uma red-black tree tolera que a altura de uma subtree seja duas vezes maior que a outra subtree de mesmo nó.
    - - Basicamente é permitir mais de um elemento em um nó.
- - - - É uma transformação local de uma subtree que transforma o nó em um saldo de +2 ou -2.
        
        Se houver diversos desses nós, giramos a árvore com a raiz no nó desequilibrado mais próximo da folha recém criada.
        
        Há apenas 4 tipos de rotações
        
        Single right rotation / R-rotation
        
        É uma rotação feita pela aresta que conecta a raiz no seu filho esquerdona árvore binária
        
        Essa rotação é feita após a inserção de uma nova key em uma subtree esquerda no filho esquerdo de uma raiz que tinha um balanço de +1 antes da inserção.
        
        Single left rotation / L-rotation
        
        É uma espelho da rotação R-rotation.
        
        Essa rotação é feita após a inserção de uma nova key em uma subtree direita no filho direito de uma raiz que tinha um balanço de -1 antes da inserção
        
        Double left-right rotation / LR-rotation
        
        É uma combinação das duas rotações
        
        Fazemos a L-rotatiom na left subtree de raiz r e em seguida fazemos a R-rotation na nova árvore de raiz r.
        
        1 more item...
        
        Double right-left rotation / RL-rotation
        
        É o espelho da LR-rotation
        
        As rotações não são transformações triviais e elas podem serem feitas contiuamente.
        
        Elas apenas não garante que a tree resultante seja uma árvore equilíbrada, mas também preserva os requisitos básicos de uma busca binária.
  - - - A eficiênda é de grandeza Big Theta(logN) no pior caso.