\u00c1rvores de busca bin\u00e1ria balanceada s\u00e3o estruturas de dados fundamentais na ci\u00eancia da computa\u00e7\u00e3o, garantindo opera\u00e7\u00f5es eficientes como pesquisa, inser\u00e7\u00e3o e exclus\u00e3o. Entre elas, as \u00e1rvores AVL, introduzidas por Adelson-Velsky e Landis em 1962, s\u00e3o um exemplo cl\u00e1ssico de auto-equil\u00edbrio em \u00e1rvores de busca bin\u00e1ria. Este artigo explora a mec\u00e2nica, a implementa\u00e7\u00e3o e as aplica\u00e7\u00f5es das \u00e1rvores AVL, fornecendo insights sobre sua import\u00e2ncia na manuten\u00e7\u00e3o de estruturas de dados equilibradas.<\/p>\n\n
Uma \u00e1rvore AVL \u00e9 uma \u00e1rvore de busca bin\u00e1ria de equil\u00edbrio, onde a diferen\u00e7a de altura entre as sub\u00e1rvores esquerda e direita (conhecido como fator de equil\u00edbrio) de qualquer n\u00f3 \u00e9 no m\u00e1ximo 1.<\/p>\n
Propriedades-chave das \u00e1rvores AVL:<\/strong><\/p>\n O fator de equil\u00edbrio de um n\u00f3 \u00e9 definido como:<\/p>\n Fator de equil\u00edbrio = altura da sub\u00e1rvore esquerda \u2212 altura da sub\u00e1rvore direita<\/em><\/p>\n Se o fator de equil\u00edbrio estiver fora do intervalo [-1, 1], a \u00e1rvore precisa ser reequilibrada por meio de rota\u00e7\u00f5es.<\/p>\n\n As rota\u00e7\u00f5es s\u00e3o usadas para manter o equil\u00edbrio da \u00e1rvore. Existem quatro tipos:<\/p>\n Exemplo:<\/p>\n\n As inser\u00e7\u00f5es envolvem:<\/p>\n Semelhante \u00e0 inser\u00e7\u00e3o, as dele\u00e7\u00f5es seguem estas etapas:<\/p>\n\n
Por que \u00e1rvores AVL?<\/h3>\n
\n
Como funcionam as \u00e1rvores AVL<\/h2>\n
1. Fator de equil\u00edbrio<\/h3>\n
2. Rota\u00e7\u00f5es em \u00e1rvores AVL<\/h3>\n
\n
<code lang=\"cpp\" class=\"language-cpp\">\nstruct Node {\n int key;\n Node* left;\n Node* right;\n int height;\n};\n\nint height(Node* n) {\n return n ? n->height : 0;\n}\n\nNode* rotateRight(Node* y) {\n Node* x = y->left;\n Node* T2 = x->right;\n\n x->right = y;\n y->left = T2;\n\n y->height = std::max(height(y->left), height(y->right)) + 1;\n x->height = std::max(height(x->left), height(x->right)) + 1;\n\n return x;\n}\n\nNode* rotateLeft(Node* x) {\n Node* y = x->right;\n Node* T2 = y->left;\n\n y->left = x;\n x->right = T2;\n\n x->height = std::max(height(x->left), height(x->right)) + 1;\n y->height = std::max(height(y->left), height(y->right)) + 1;\n\n return y;\n}\n<\/code><\/pre>\n\n\n3. Inser\u00e7\u00e3o em \u00e1rvores AVL<\/h3>\n
\n
4. Exclus\u00e3o em \u00e1rvores AVL<\/h3>\n
\n
Aplica\u00e7\u00f5es do mundo real de \u00e1rvores AVL<\/h2>\n