Arvore_AVL_-_(Estrutura_de_dados)

Prévia do material em texto

<p>Árvore AVL  Estrutura de dados) 1</p><p>Árvore AVL - (Estrutura de</p><p>dados)</p><p>INTRODUÇÃO:</p><p>Árvore binária com o conceito de balanceamento.</p><p>No pior caso, o número de comparações para se localizar um elemento em</p><p>uma AVL é aproximadamente 1,44 * log(n) = 𝚯(log(n)).</p><p>BALANCEAMENTO:</p><p>Uma árvore balanceada em que para TODOS os nós a diferença entre a altura</p><p>de suas árvores da esquerda e da direita será 0 ou  1.</p><p>Motivos para uma árvore com balanceamento:</p><p>Temos mais eficiência em pesquisa, inserção e remoção.</p><p>Cálculo fator de balanceamento:</p><p>fator(i) = alturaDir(i) - alturaEsq(i);</p><p>Operações de balanceamento:</p><p>Árvores desbalanceadas para a ESQUERDA:</p><p>Devem ser rotacionadas para a</p><p>DIREITA.</p><p>Árvores desbalanceadas para a DIREITA</p><p>Devem ser rotacionadas para a ESQUERDA.</p><p>TIPOS DE ROTAÇÃO:</p><p>Árvore AVL  Estrutura de dados) 2</p><p>Rotação simples à esquerda:</p><p>Usada em subárvores desbalanceadas para a direita.</p><p> Pegamos o nó com fator de balanceamento 2 e fazemos</p><p>este virar filho a esquerda do filho dele.</p><p>https://prod-files-secure.s3.us-west-2.amazonaws.co</p><p>m/2276effd-3bab-4b629d02488a77fb9015/a720b8</p><p>b54a2b-4789-a8916f7fa26c6541/Untitled.mp4</p><p>Rotação simples à direita:</p><p>Usada em subárvores desbalanceadas para a esquerda.</p><p> Pegamos o nó com fator de balanceamento 2 e fazemos</p><p>este virar filho a direita do filho dele.</p><p>https://prod-files-secure.s3.us-west-2.amazonaws.co</p><p>m/2276effd-3bab-4b629d02488a77fb9015/37a43fa</p><p>a-728c-4ce3-acaa-aec7d2e4d79e/Untitled.mp4</p><p>Rotação dupla → direita - esquerda:</p><p>Usada em subárvores em que um nó está desbalanceado</p><p>para a direita e seu filho para a esquerda.</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2Fa720b8b5-4a2b-4789-a891-6f7fa26c6541%2FUntitled.mp4?table=block&id=a513202e-34d1-4dbf-bcd1-2be36e7b2ca6&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2Fa720b8b5-4a2b-4789-a891-6f7fa26c6541%2FUntitled.mp4?table=block&id=a513202e-34d1-4dbf-bcd1-2be36e7b2ca6&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2Fa720b8b5-4a2b-4789-a891-6f7fa26c6541%2FUntitled.mp4?table=block&id=a513202e-34d1-4dbf-bcd1-2be36e7b2ca6&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F37a43faa-728c-4ce3-acaa-aec7d2e4d79e%2FUntitled.mp4?table=block&id=b487ff97-5707-4e3c-97ee-044abbeb39c0&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F37a43faa-728c-4ce3-acaa-aec7d2e4d79e%2FUntitled.mp4?table=block&id=b487ff97-5707-4e3c-97ee-044abbeb39c0&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F37a43faa-728c-4ce3-acaa-aec7d2e4d79e%2FUntitled.mp4?table=block&id=b487ff97-5707-4e3c-97ee-044abbeb39c0&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>Árvore AVL  Estrutura de dados) 3</p><p> Pegamos o nó com fator de balanceamento 2. O filho a</p><p>esquerda do filho dele vira filho a direita do nó com fator 2. O</p><p>nó desbalanceado vira filho a esquerda do filho dele</p><p>https://prod-files-secure.s3.us-west-2.amazonaws.co</p><p>m/2276effd-3bab-4b629d02488a77fb9015/188152f</p><p>33437417b-8a9e-f72e8ae400be/Untitled.mp4</p><p>Rotação dupla → esquerda-direita</p><p>Usada em subárvores em que um nó está desbalanceado</p><p>para a esquerda e seu filho para a direita.</p><p> Pegamos o nó com fator de balanceamento 2. O filho a</p><p>direita do filho dele vira filho a esquerda do nó com fator 2.</p><p>O nó desbalanceado vira filho a direita do filho dele</p><p>https://prod-files-secure.s3.us-west-2.amazonaws.co</p><p>m/2276effd-3bab-4b629d02488a77fb9015/891d017</p><p>4203b-4e7c-a3ef-d3a00659f8bc/Untitled.mp4</p><p>TABELA TIPOS DE ROTAÇÃO:</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F188152f3-3437-417b-8a9e-f72e8ae400be%2FUntitled.mp4?table=block&id=1c23c41c-34b3-4fa9-8b97-6b1f67f51c2e&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F188152f3-3437-417b-8a9e-f72e8ae400be%2FUntitled.mp4?table=block&id=1c23c41c-34b3-4fa9-8b97-6b1f67f51c2e&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F188152f3-3437-417b-8a9e-f72e8ae400be%2FUntitled.mp4?table=block&id=1c23c41c-34b3-4fa9-8b97-6b1f67f51c2e&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F891d0174-203b-4e7c-a3ef-d3a00659f8bc%2FUntitled.mp4?table=block&id=cdbdbcc0-fe7b-4d78-988b-d5f1b1579004&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F891d0174-203b-4e7c-a3ef-d3a00659f8bc%2FUntitled.mp4?table=block&id=cdbdbcc0-fe7b-4d78-988b-d5f1b1579004&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2F891d0174-203b-4e7c-a3ef-d3a00659f8bc%2FUntitled.mp4?table=block&id=cdbdbcc0-fe7b-4d78-988b-d5f1b1579004&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>Árvore AVL  Estrutura de dados) 4</p><p>ALGORITMO AVL:</p><p>https://prod-files-secure.s3.us-west-2.amazonaws.com/2276effd-3bab-</p><p>4b629d02488a77fb9015/ee153d927d9248e78d2a-8ae892097fa4/</p><p>CodigoAVL.pdf</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2Fee153d92-7d92-48e7-8d2a-8ae892097fa4%2FCodigoAVL.pdf?table=block&id=d371d3aa-606e-4ebe-807e-4334cfa478cb&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2Fee153d92-7d92-48e7-8d2a-8ae892097fa4%2FCodigoAVL.pdf?table=block&id=d371d3aa-606e-4ebe-807e-4334cfa478cb&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p><p>https://www.notion.so/signed/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F2276effd-3bab-4b62-9d02-488a77fb9015%2Fee153d92-7d92-48e7-8d2a-8ae892097fa4%2FCodigoAVL.pdf?table=block&id=d371d3aa-606e-4ebe-807e-4334cfa478cb&spaceId=2276effd-3bab-4b62-9d02-488a77fb9015&userId=a2d70603-f8de-491b-b2ad-74a0fa84fb85&cache=v2</p>