Дървовидни структури съществуват две дефиниции на дървовидна структура или дърво. Нерекурсивна

Изтегляне 1.39 Mb.

страница	3/4
Дата	04.06.2022
Размер	1.39 Mb.
	#114535

1 2 3 4

Дървета
Свързани:
топологично сортиране на граф, пропускливост на мрежа, МПТПротоколПлан

О(Log 2 N). Ако h(N)

void add(int n, elem* &t)
{
if (t==NULL)
{
t=new elem;
t->key=n;
t->left=t->right=NULL;
}
else
{
if (t->keyadd(n,t->right);
else
add(n,t->left);
}
}
Търсене на елемент в двоично дърво

Двете примерни функции връщат като резултат указател към търсения елемент. Ако елементът не принадлежи на дървото, върнатата стойност е NULL

Итеративно търсене на елемент в подредено двоично дърво

elem *search_iter(elem *t, int k)
{
while ((t!=NULL)&&(t->key!=k))
if (t->keyt=t->right;
else
t=t->left;
return t;
}

Рекурсивно търсене на елемент в подредено двоично дърво:

elem *search_rec(elem *t, int k)
{
if (t!=NULL)
if (t->key t=search_rec(t->right, k);
else
if(t->key>k)
t=search_rec(t->left, k);
return t;
}
Премахване на възел от двоично дърво

Операцията премахване на възел от двоично дърво за търсене не трябва да нарушава подредбата на структурата. Възможни са следните варианти:

- Ако премахваният елемент е листо, неговото отстраняване не нарушава структурата;
- Ако премахваният елемент има само един наследник, той замества изтривания възел;
- Ако премахваният елемент има два наследника, то изтриваният възел се замества или с най-десния (най-големия) елемент от лявото му поддърво или с най-левия (най-малкия) елемент от дясното му поддърво.
Изтриване на възел:
struct tree {
int key;
tree *left,*right;
};
tree *root=NULL,*z;
...
int del(int k)
{
tree * &p=search(k), *p0=p, **qq, *q;
// search(k)- функция, която търси в дървото възел
// с ключова стойност k и връща адреса на указател към него
if (p==NULL) return 0; //Възелът не е намерен
if ((p->right==NULL))
{
p=p->left; delete p0;
}
else
if(p->left==NULL)
{
p=p->right; delete p0;
}
else //Възелът е с два наследника
{
qq=&p->left;
while ((*qq)->right)
qq=&(*qq)->right;
p->key=(*qq)->key;
q=*qq;
*qq=q->left;
delete q;
}
return 1;
}

Балансирани двоични дървета

Всяко двоично дърво може да бъде балансирано. Двоично дърво се нарича балансирано или балансирано по височина, ако разликата във височините на поддърветата на всеки негов възел е най-много 1:

Лявото дърво не е балансирано. Дясното е балансирано.
Едно двоично дърво се нарича идеално балансирано или с балансирано тегло, ако всеки негов възел има ляво и дясно поддърво, в които броят на възлите се различава най-много с 1:

Очевидно е, че всяко идеално балансирано дърво (с балансирано тегло) също така е дърво с балансирана височина. Обратното твърдение не е вярно.
Идеално балансираното дърво може да бъде пълно, ако за всеки възел разликата в броя на възлите в неговите поддървета е нула. Лявото дърво на горната фигура е пълно.
За да бъде двоичното дървото пълно, броят на възлите му трябва да е нечетен. Ако К е броя на нивата в дървото (коренът се брои за 0-во ниво), то броят на вътрешните възлите в пълното двоично дърво N е равен на 2^К+1-1.
Балансът обикновено е важен фактор при работа с двоични дървета за търсене, където е от значение времето за търсене и не трябва да има отделни дълги клони. Балансираните дървета често наричат AVL-дървета в чест на Adelson-Velski и Landis - двамата учени, създали най-много алгоритми за този клас дървовидни структури.
Основните операции с балансираните дървета - добавяне, премахване и търсене на елемент с зададена ключова стойност - имат сложност О(Log₂N).
Ако h(N) е височината на балансирано двоично дърво с N вътрешни възела, то
Log₂(N+1) <= h(N)<= 1.4404Log₂(N+2) - 0.328
В-дървета или дървета на Байер и МакКрейт (Bayer&McCreight)

Това са дървета с много разклонения. В-дърво може да се разглежда като обобщение на 2-3 и 2-3-4-дървета.

В-дърво от ред m се нарича дърво за претърсване със следните свойства:

- За всички възли, освен корена, брой наследници i е

Изтегляне 1.39 Mb.

Сподели с приятели:

1 2 3 4