45-rasm. "Yangi" ildizning oʻng pastki daraxtini aniqlash
Muvonazatlash
algortmidan
soʻng,
AVL
boʻyicha
muvozanatlashgan quyidagi daraxt hosil boʻldi:
126
a)
Dastlabki daraxt
b) Muvozanatlashgan daraxt
9.2. AVL daraxtlarining samaradorligini tahlil qilish
N elementni oʻz ichiga olgan AVL daraxtining balandligini
yuqoridan baholaylik.
h balandlikdagi AVL daraxtini hosil qilish uchun zarur boʻlgan
minimal tugunlarni N (h) bilan belgilaymiz.
N(-1)=0, N(0)=1, N(1)=2, N(2)=4, N(3)=7, …
0,1, 2, 4, 7, 12, 20, 33, 54, …
127
Fibonachchi ketma-ketligining h –hadi uchun Binet formulasidan
AVL daraxtining h (n) balandligi uchun yuqori chegara:
AVL daraxtidan tugunlarni olib tashlash
#include
using namespace std;
struct avltree
{
int key;
char *value;
int height;
struct avltree *left;
struct avltree *rigth;
};
AVL daraxtidan barcha tugunlarni olib tashlash funksiyasi
void avltree_free (struct avltree *tree)
{
if (tree == NULL)
return;
avltree_free(tree->left);
avltree_free(tree->rigth);
free(tree);
}
|
