Please enable JavaScript.
Coggle requires JavaScript to display documents.
Binary Tree - Coggle Diagram
Binary Tree
-
Balanced Search tree
É uma binary tree que o elemento filho mais a esquerda de um nó é sempre menor que seu pai, ao mesmo tempo, o nó da direita é sempre maior
Usada ao inves de uma implementação de dicionario em array por que a sua eficiencia temporal no caso médio é melhor na função de inserção, remover e procurar
Contudo, é extremamente ineficiente caso seja uma arvore muito desbalanceada, fazendo a eficiencia temporal ser O(n²). Para evitar o desbalanceamento e se aproximar das arvores ideais, foram criados dois novos tipos
AVL tree
É uma binary tree com um fator de balanceamento em cada um dos nós da arvore. Caso o fator esteja fora do padrão, a arvore estará desbalanceada e sofrerá um processo chamado Rotation para ser rebalanceada
Fator de Balanceamento é a diferença entre a altura da arvore do filho da esquerda e do filho da direita. Esse fator só pode estar entre -1, 0 e 1
Rotation é uma transformação que uma AVL tree sofre quando um de seus nós chega ao valor de -2 ou +2. Quando isso acontece, criamos uma nova árvore com o nó desbalanceado como raiz. OBS: Se houver mais de um nó desbalanceado, o nó escolhido será o mais proximo da folha recem inserida
4 tipos de rotation
Single left rotation
Quando um novo elemento é adicionado a arvore da direita e torna um fator de um elemento em -2. Basicamente, escolhe o nó com -2, ele sofrerá uma puxada para direita
LR rotation
Quando um novo elemento é adicionado a arvore da esquerda e torna um fator de um elemento em +2. Basicamente, faz uma L-rotation na subarvore da esquerda e depois uma R-rotation nessa nova árvore.
RL rotation
Quando um novo elemento é adicionado a arvore da direita e torna um fator de um elemento em -2. Basicamente, faz uma R-rotation na subarvore da esquerda e depois uma L-rotation nessa nova árvore.
Single right rotation
Quando um novo elemento é adicionado a arvore da direita e torna um fator de um elemento em +2. Basicamente, escolhe o nó com +2, ele sofrerá uma puxada para esquerda
-
É uma ordered tree, mas nenhum nó tem mais do que dois filhos. Normalmente, à esquerda tem numeros menores que o pai e à direita, numeros maiores
Inserção e busca: Consiste em verificar no nó pai se o valor buscado (ou que se quer inserir) é maior ou menor que o nó atual. Esse processo se repete até se chegar a uma folha ou até o valor buscado
Altura: Consiste em verificar a maior altura do nó filho da esquerda e o da direita e o maior é a aultua da árvore