Vyv\u00e1\u017een\u00e9 bin\u00e1rn\u00ed vyhled\u00e1vac\u00ed stromy jsou z\u00e1kladn\u00ed datov\u00e9 struktury v po\u010d\u00edta\u010dov\u00e9 v\u011bd\u011b, kter\u00e9 zaji\u0161\u0165uj\u00ed efektivn\u00ed operace, jako je vyhled\u00e1v\u00e1n\u00ed, vkl\u00e1d\u00e1n\u00ed a maz\u00e1n\u00ed. Mezi nimi jsou AVL stromy, kter\u00e9 p\u0159edstavili Adelson-Velsky a Landis v roce 1962, klasick\u00fdm p\u0159\u00edkladem samovyva\u017eov\u00e1n\u00ed bin\u00e1rn\u00edch vyhled\u00e1vac\u00edch strom\u016f. Tento \u010dl\u00e1nek zkoum\u00e1 mechaniku, implementaci a aplikace strom\u016f AVL a poskytuje pohled na jejich d\u016fle\u017eitost p\u0159i udr\u017eov\u00e1n\u00ed vyv\u00e1\u017een\u00fdch datov\u00fdch struktur.<\/p>\n\n
Strom AVL je samovyva\u017euj\u00edc\u00ed bin\u00e1rn\u00ed vyhled\u00e1vac\u00ed strom, kde rozd\u00edl ve v\u00fd\u0161ce mezi lev\u00fdm a prav\u00fdm podstromem (zn\u00e1m\u00fdm jako faktor vyv\u00e1\u017een\u00ed) libovoln\u00e9ho uzlu je maxim\u00e1ln\u011b 1.<\/p>\n
Kl\u00ed\u010dov\u00e9 vlastnosti strom\u016f AVL:<\/strong><\/p>\n Faktor rovnov\u00e1hy uzlu je definov\u00e1n jako:<\/p>\n Faktor rovnov\u00e1hy = V\u00fd\u0161ka lev\u00e9ho podstromu \u2212 V\u00fd\u0161ka prav\u00e9ho podstromu<\/em><\/p>\n Pokud je faktor rovnov\u00e1hy mimo rozsah [-1, 1], strom pot\u0159ebuje znovu vyv\u00e1\u017eit prost\u0159ednictv\u00edm rotac\u00ed.<\/p>\n\n Rotace se pou\u017e\u00edvaj\u00ed k udr\u017een\u00ed rovnov\u00e1hy stromu. Existuj\u00ed \u010dty\u0159i typy:<\/p>\n P\u0159\u00edklad:<\/p>\n\n Vkl\u00e1d\u00e1n\u00ed zahrnuje:<\/p>\n Podobn\u011b jako u vkl\u00e1d\u00e1n\u00ed se maz\u00e1n\u00ed \u0159\u00edd\u00ed t\u011bmito kroky:<\/p>\n\n
Pro\u010d AVL stromy?<\/h3>\n
\n
Jak funguj\u00ed stromy AVL<\/h2>\n
1. Vyva\u017eovac\u00ed faktor<\/h3>\n
2. Rotace v AVL stromech<\/h3>\n
\n
\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. Vlo\u017een\u00ed do strom\u016f AVL<\/h3>\n
\n
4. Vymaz\u00e1n\u00ed ve stromech AVL<\/h3>\n
\n
Re\u00e1ln\u00e9 aplikace strom\u016f AVL<\/h2>\n