Avl daraxti tushunchasi

AVL daraxti tushunchasi
AVL daraxti, avvalambor, ikkilik qidiruv daraxtidir, uning kalitlari standart xususiyatni qondiradi: har qanday daraxt tugunining kaliti ushbu tugunning chap pastki daraxtidagi har qanday tugmachadan kam emas va ushbu tugunning o'ng pastki daraxtidagi biron bir kalitdan ko'p emas. Demak, AVL daraxtidan kerakli kalitni topish uchun standart algoritmdan foydalanish mumkin. Keyinchalik taqdimotning soddaligi uchun biz daraxtdagi barcha tugmachalar va takrorlanmasligini taxmin qilamiz.
AVL daraxtining xususiyati shundaki, u quyidagi ma'noda muvozanatlashgan: daraxtning har qanday tuguni uchun uning o'ng pastki daraxtining balandligi chap daraxtning balandligidan bittadan ko'p bo'lmaganligi bilan farq qiladi. Daraxt balandligi logaritmik ravishda uning tugunlari soniga bog'liq bo'lishi uchun bu xususiyat etarli ekanligi isbotlangan: AV tugmachasining balandligi h tugmachalari log2 (n + 1) dan 1,44 log2 (n + 2) - 0,328 gacha. Va ikkilik qidiruv daraxtlari bo'yicha asosiy operatsiyalar (tugunlarni izlash, qo'shish va o'chirish) uning balandligiga chiziqli ravishda bog'liq bo'lganligi sababli, biz ushbu algoritmlarning ishlash vaqtining daraxtda saqlanadigan tugmalar soniga kafolatlangan logaritmik bog'liqligini olamiz. Eslatib o'tamiz, tasodifiy qidiruv daraxtlari muvozanatni faqat ehtimollik ma'nosida ta'minlaydi: katta n uchun kuchli muvozanatsiz daraxt olish ehtimoli, ammo ahamiyatsiz bo'lsa ham, nolga teng bo'lib qoladi.

Tugun tuzilishi

Biz AVL daraxtining tugunlarini quyidagi tuzilishga ega qilamiz:

Kalit maydonida tugunning kaliti saqlanadi, balandlik maydoni - bu tugunda ildiz otgan daraxt daraxtining balandligi, chap va o'ng maydonlar chap va o'ng pastki daraxtlarga ko'rsatgichlar. Oddiy konstruktor berilgan k tugmachasi bilan yangi tugunni (balandligi 1) yaratadi.
An'anaga ko'ra, AVL-daraxtining tugunlari balandlikni emas, balki o'ng va chap pastki daraxtlarning balandlikdagi farqini (muvozanat koeffitsienti deb ataladi) saqlaydi, ular faqat uchta qiymatni olishi mumkin -1, 0 va 1. Ammo, bu farq hali ham o'zgaruvchida saqlanadi. hajmi kamida bitta bayt (agar siz bunday qiymatlarni "samarali" qadoqlash uchun ba'zi bir aqlli sxemalarni o'ylamasangiz).
Eslatib o'tamiz, h <1.44 log2 (n + 2) balandligi, masalan, n = 109 (bir milliard tugma, tugunlarni saqlash uchun 10 gigabaytdan ortiq xotira) uchun daraxtning balandligi h = 44 qiymatidan oshmaydi, bu muvaffaqiyatli joylashishi mumkin. muvozanat omili bilan bir xil xotirada. Shunday qilib, balandliklarni saqlash, bir tomondan, daraxt tugunlari uchun ajratilgan xotira hajmini ko'paytirmaydi, boshqa tomondan, ba'zi operatsiyalarni bajarilishini ancha soddalashtiradi.
Balandlik bilan bog'liq uchta yordamchi funktsiyani aniqlaymiz. Birinchisi, balandlik maydoni uchun o'ram, u nol ko'rsatkichlar bilan (bo'sh daraxtlar bilan) ishlashi mumkin:


Ikkinchisi berilgan tugunning muvozanat koeffitsientini hisoblab chiqadi (va faqat bo'sh bo'lmagan ko'rsatkichlar bilan ishlaydi):

Uchinchi funktsiya berilgan tugunning balandlik maydonining to'g'ri qiymatini tiklaydi (o'ng va chap bolalar tugunlarida ushbu maydonning qiymatlari to'g'ri bo'lishi sharti bilan):




E'tibor bering, uchta funktsiya ham rekursiv emas, ya'ni. ularning ishlash vaqti O (1) qiymatdir.

Balanslash tugunlari

AVL daraxtidagi tugunlarni qo'shish yoki olib tashlash jarayonida ba'zi tugunlarning muvozanat koeffitsienti 2 yoki -2 ga aylanganda vaziyat yuzaga kelishi mumkin, ya'ni. pastki daraxt muvozanatsiz bo'lib qoladi. Vaziyatni to'g'irlash uchun biz ma'lum daraxt tugunlari atrofida taniqli aylanishlardan foydalanamiz. Shuni eslatib qo'yamanki, o'ngga (chapga) oddiy burilish daraxtning quyidagi o'zgarishini hosil qiladi:

To'g'ri aylanishni amalga oshiradigan kod quyidagicha ko'rinadi (odatdagidek, daraxtni o'zgartiradigan har bir funktsiya hosil bo'lgan daraxtning yangi ildizini qaytaradi):



Chap burilish - o'ng tomonning nosimmetrik nusxasi:

Keling, p tugunning o'ng pastki daraxtining balandligi chap pastki daraxtning balandligidan 2 baravar ko'p bo'lgan muvozanatsizlik holatini ko'rib chiqamiz (qarama-qarshi holat nosimmetrik va shunga o'xshash tarzda amalga oshiriladi). P tugunning o'ng vorisi va q tugunning chap vorisi bo'lsin.

Ushbu vaziyat doirasida yuzaga kelishi mumkin bo'lgan holatlarning tahlili shuni ko'rsatadiki, p tugundagi muvozanatni to'g'rilash uchun yoki p atrofida oddiy chap burilishni yoki xuddi shu p atrofida katta chap deb atalmish harakatni bajarish kifoya. Q tugunning chap pastki daraxtining balandligi uning o'ng pastki daraxtining balandligidan katta bo'lishi sharti bilan oddiy aylanish amalga oshiriladi: h (s) ≤h (D).

Katta aylanish h (s)> h (D) sharti bilan qo'llaniladi va bu holda ikkita oddiyga kamaytiriladi - birinchi navbatda q atrofida o'ng, keyin p atrofida chap aylanish.

Balans kodi tekshirish shartlari va burilishlarni bajarish uchun qisqartiriladi:



Burilish va muvozanatlashning tavsiflangan funktsiyalari, shuningdek, hech qanday tsikl yoki rekursiyani o'z ichiga olmaydi, ya'ni ular AVL daraxti o'lchamiga bog'liq bo'lmagan doimiy vaqt ichida bajarilishini anglatadi.

Kalit qo'shish

AVL daraxtiga yangi tugmachani kiritish, oddiygina qidirish daraxtlaridagi kabi katta hajmda amalga oshiriladi: biz daraxtga tushamiz, joriy tugundagi kalit va kiritilgan kalitni taqqoslash natijasiga qarab harakatning o'ng yoki chap yo'nalishini tanlaymiz. Faqatgina farq shundaki, rekursiyadan qaytayotganda (ya'ni kalit o'ngga yoki chapga o'tqazilgan daraxtga kiritilib, daraxt muvozanatlanganda), joriy tugun muvozanatlashadi. Harakat yo'li bo'ylab har qanday tugunda bunday qo'shilish natijasida yuzaga keladigan nomutanosiblik ikkitadan oshmasligi qat'iyan isbotlangan, bu yuqorida tavsiflangan muvozanatlash funktsiyasidan foydalanish to'g'ri ekanligini anglatadi.

Amalga oshirilgan qo'shish algoritmining AVL daraxtlari balandligi uchun nazariy baholarga muvofiqligini tekshirish uchun oddiy hisoblash tajribasi o'tkazildi. 1 dan 10000 gacha bo'lgan tasodifiy joylashtirilgan raqamlar to'plami hosil bo'ldi, so'ngra bu raqamlar ketma-ket dastlab bo'sh bo'lgan AVL daraxtiga kiritildi va har bir kiritilishdan keyin daraxtning balandligi o'lchandi. Olingan natijalar o'rtacha 1000 dan ortiq hisob-kitoblarga to'g'ri keldi. Quyidagi grafikda o'rtacha balandlik n ga nisbatan (qizil chiziq) ko'rsatilgan; minimal balandlik (yashil chiziq); maksimal balandlik (ko'k chiziq). Bundan tashqari, yuqori va pastki nazariy taxminlar ko'rsatilgan.

Ko'rinib turibdiki, tasodifiy tugmachalar ketma-ketligi uchun eksperimental ravishda topilgan balandliklar nazariy chegaralarga kichik chegaralar bilan ham tushadi. Agar asl tugma ketma-ketligi o'sish tartibida bo'lsa, pastki chegaraga erishish mumkin (hech bo'lmaganda ba'zi nuqtalarda).
AVL daraxtidan tugunlarni olib tashlash bilan, afsuski, narsalar tasodifiy qidirish daraxtlari kabi yaxshi emas. Ikki daraxtni birlashtirishga (qo'shilishga) asoslangan usul na topilgan va na ixtiro qilingan. Shuning uchun asos deyarli hamma joyda tavsiflangan variantga asoslandi (va bu odatda standart ikkilik qidiruv daraxtidan tugunlarni olib tashlashda ishlatiladi). Fikr quyidagicha: biz berilgan k tugmachasi bilan tugunni topamiz (agar topmasak, unda hech narsa qilishimiz shart emas), o'ng pastki daraxtda biz eng kichik tugmachali tugunni topamiz va o'chirilgan tugunni topilgan min bilan almashtiramiz.

Amalga oshirish jarayonida bir nechta nuanslar paydo bo'ladi. Birinchidan, agar topilgan p tugunida o'ng pastki daraxt bo'lmasa, u holda chapdagi AVL daraxti xususiyati bo'yicha ushbu tugunda bitta bitta tuguncha bo'lishi mumkin (balandligi 1 daraxti) yoki umuman p tuguni bargdir. Ikkala holatda ham siz faqat tugunni o'chirib tashlashingiz va natijada p tugunning chap bolasiga ko'rsatgichni qaytarishingiz kerak.

Endi p o'ng pastki daraxtga ega bo'lsin. Ushbu kichik daraxtda minimal kalitni toping. Ikkilik qidiruv daraxti xususiyati bo'yicha ushbu kalit daraxtning ildizidan boshlab chap shoxning oxirida joylashgan. Biz rekursiv funktsiyani qo'llaymiz:

Yana bitta xizmat funktsiyasi ushbu daraxtdan minimal elementni olib tashlash bilan shug'ullanadi. Shunga qaramay, AVL daraxtining xususiyatiga ko'ra, o'ngdagi minimal element bitta tugunni to'xtatib qo'ygan yoki bo'sh. Ikkala holatda ham siz ko'rsatgichni o'ng tugunga qaytarishingiz va orqaga qaytishda muvozanatni bajarishingiz kerak (rekursiyadan qaytayotganda). Minimal tugunning o'zi o'chirilmaydi, chunki bu hali ham biz uchun foydali bo'ladi.

Endi hamma narsa AVL daraxtidan kalitni olib tashlashni amalga oshirishga tayyor. Birinchidan, biz kerakli tugunni topamiz, kalitni kiritishda bir xil amallarni bajaramiz:

K kaliti topilgach, B rejasiga o'ting: p tugunning chap va o'ng pastki daraxtlarining q va r ildizlarini eslang; tugunni o'chirish p; agar o'ng pastki daraxt bo'sh bo'lsa, u holda chap pastki daraxtga ko'rsatgichni qaytaring; agar o'ng pastki daraxt bo'sh bo'lmasa, biz u erda minimal elementni topamiz, keyin biz uni o'sha yerdan chiqaramiz, chapdan mingacha biz q ni to'xtatamiz, o'ngdan - r dan nima chiqdi, biz uni muvozanatlashtirgandan keyin minni qaytaramiz.



Rekursiyadan chiqayotganda balanslashni amalga oshirishni unutmang:

Minimal tugunni qidirish va uni qazib olish, asosan, bitta funktsiyada amalga oshirilishi mumkin va funktsiyadan ko'rsatgich juftligini qaytarish (unchalik qiyin emas) muammosini hal qilishga to'g'ri keladi. Lekin siz to'g'ri subtree orqali bitta o'tishda tejashingiz mumkin.
Shubhasiz, kiritish va o'chirish operatsiyalari (shuningdek, oddiyroq qidirish operatsiyasi) daraxt balandligiga mutanosib ravishda amalga oshiriladi, chunki ushbu operatsiyalarni bajarish jarayonida ildizdan ma'lum tugunga tushish amalga oshiriladi va har bir darajada ma'lum bir belgilangan harakatlar soni amalga oshiriladi. Va AVL daraxti muvozanatlashganligi sababli uning balandligi logaritmik ravishda tugun soniga bog'liq. Shunday qilib, barcha uchta asosiy operatsiyalarning bajarilish vaqti logaritmik ravishda daraxt tugunlari soniga bog'liqligiga kafolat beradi.

Qizil-qora daraxtlar

Qizil-qora daraxtlar muvozanatli ikkilik qidiruv daraxtlariga ishora qiladi.

Ikkilik daraxt sifatida qizil-qora quyidagi xususiyatlarga ega:

1) Ikkala kichik daraxt ham ikkilik qidiruv daraxtlari.

2) Kaliti bo'lgan har bir tugun uchun buyurtma mezonlari qondiriladi:

chapdagi bolalar tugmachalari <=

(boshqa ta'riflarda dublikatlar o'ng tomonda yoki umuman bo'lmasligi kerak).

Ushbu tengsizlik tugunning nafaqat uning farzandlariga, balki barcha avlodlariga tegishli bo'lishi kerak.
Qizil-qora daraxtlarning xususiyatlari:

1) Har bir tugun qizil yoki qora rangga bo'yalgan (tugun ma'lumotlari tarkibida qo'shimcha maydon paydo bo'ladi - rang biti).

2) Ildiz qora rangga bo'yalgan.

3) Barglar (NULL tugunlari deb ataladi) qora rangga bo'yalgan.

4) Har bir qizil tugunda ikkita qora bola tugunlari bo'lishi kerak. Shuni ta'kidlash kerakki, qora tugunda qora tanli bolalar bo'lishi mumkin. Bolalikda faqat qora tugunlarda qizil tugunlar bo'lishi mumkin.

5) Tugundan uning barglarigacha bo'lgan yo'llar bir xil miqdordagi qora tugunlarni o'z ichiga olishi kerak (bu qora balandlik).

Xo'sh, nima uchun bunday daraxt muvozanatlangan?

Darhaqiqat, qizil-qora daraxtlar AVL daraxtlarida bo'lgani kabi qat'iy muvozanatni kafolatlamaydi (har qanday tugunning ikkita pastki daraxtining balandligi farqi 1 dan oshmasligi kerak). Ammo qizil-qora daraxtning xususiyatlariga rioya qilish qo'shish, o'chirish va olib kirish operatsiyalarini o'z vaqtida bajarilishini ta'minlashga imkon beradi.

Keling, bu haqiqatan ham shundaymi yoki yo'qligini bilib olaylik.

Bizda qizil-qora daraxt bor deylik. Qora balandlik bh.

Agar ildiz tugunidan barg tuguniga boradigan yo'lda qizil tugunlarning minimal soni (ya'ni nol) bo'lsa, u holda bu yo'l bh ga teng.
Agar yo'lda qizil tugunlarning maksimal soni bo'lsa, unda bu yo'l 2bh bo'ladi.
Ya'ni, ildizdan barggacha yo'llar ikki martadan ko'p farq qilishi mumkin.
bu erda h - kichik daraxtning balandligi), bu bunday daraxtdagi operatsiyalarni bajarish vaqti uchun etarli bo'ladi.

Typedef T operatorlari va compLT va compEQ ni taqqoslaganlar daraxt tugunlarida saqlanadigan ma'lumotlarga mos ravishda o'zgartirilishi kerak. Node turidagi har bir tugun ko'rsatkichlarni chapga, ikkita bolaga, ota-onaga ota-onaga saqlaydi. Tugun rangi rang maydonida saqlanadi va QIZIL yoki QORA bo'lishi mumkin. Haqiqiy ma'lumotlar ma'lumotlar maydonida saqlanadi. Daraxtning barcha barglari qo'riqchilar, bu kodlarni sezilarli darajada soddalashtiradi. Ildiz tuguni daraxtning ildizi va eng boshida qo'riqchi tuguni.

InsertNode funktsiyasi yangi tugun uchun xotirani so'raydi, uning maydonlarining kerakli qiymatlarini o'rnatadi va daraxtga kiritadi. Shunga ko'ra, u qizil-qora xususiyatlarning saqlanishiga ishonch hosil qiladigan insertFixup-ni chaqiradi. DeleteNode funktsiyasi daraxtdan tugunni olib tashlaydi. U qizil-qora xususiyatlarni tiklaydigan deleteFixup-ni chaqiradi. FindNode funktsiyasi daraxtni kerakli tugunni qidiradi.

/* red-black tree */

#include

#include
#include
#include
typedef int T; /* type of item to be stored */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/* Red-Black tree description */

typedef enum { BLACK, RED } nodeColor;

typedef struct Node_ {

struct Node_ *left; /* left child */
struct Node_ *right; /* right child */
struct Node_ *parent; /* parent */
nodeColor color; /* node color (BLACK, RED) */
T data; /* data stored in node */
} Node;

#define NIL &sentinel /* all leafs are sentinels */

Node sentinel = { NIL, NIL, 0, BLACK, 0};

Node *root = NIL; /* root of Red-Black tree */

void rotateLeft(Node *x) {

/**************************

* rotate node x to left *
**************************/

Node *y = x->right;

/* establish x->right link */

x->right = y->left;
if (y->left != NIL) y->left->parent = x;

/* establish y->parent link */

if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
} else {
root = y;
}

/* link x and y */

y->left = x;
if (x != NIL) x->parent = y;
}

void rotateRight(Node *x) {

/****************************

* rotate node x to right *
****************************/

Node *y = x->left;

/* establish x->left link */

x->left = y->right;
if (y->right != NIL) y->right->parent = x;

/* establish y->parent link */

if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
} else {
root = y;
}

/* link x and y */

y->right = x;
if (x != NIL) x->parent = y;
}

void insertFixup(Node *x) {

/*************************************

* maintain Red-Black tree balance *
* after inserting node x *
*************************************/

/* check Red-Black properties */

while (x != root && x->parent->color == RED) {
/* we have a violation */
if (x->parent == x->parent->parent->left) {
Node *y = x->parent->parent->right;
if (y->color == RED) {

/* uncle is RED */

x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

/* uncle is BLACK */

if (x == x->parent->right) {
/* make x a left child */
x = x->parent;
rotateLeft(x);
}

/* recolor and rotate */

x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
} else {

/* mirror image of above code */

Node *y = x->parent->parent->left;
if (y->color == RED) {

/* uncle is RED */

x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

/* uncle is BLACK */

if (x == x->parent->left) {
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
}

Node *insertNode(T data) {

Node *current, *parent, *x;

/***********************************************

* allocate node for data and insert in tree *
***********************************************/

/* find where node belongs */

current = root;
parent = 0;
while (current != NIL) {
if (compEQ(data, current->data)) return (current);
parent = current;
current = compLT(data, current->data) ?
current->left : current->right;
}

/* setup new node */

if ((x = malloc (sizeof(*x))) == 0) {
printf ("insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = RED;

/* insert node in tree */

if(parent) {
if(compLT(data, parent->data))
parent->left = x;
else
parent->right = x;
} else {
root = x;
}

insertFixup(x);

return(x);
}

void deleteFixup(Node *x) {

/*************************************

* maintain Red-Black tree balance *
* after deleting node x *
*************************************/

while (x != root && x->color == BLACK) {

if (x == x->parent->left) {
Node *w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateLeft (x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rotateRight (w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rotateLeft (x->parent);
x = root;
}
} else {
Node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateRight (x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rotateLeft (w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotateRight (x->parent);
x = root;
}
}
}
x->color = BLACK;
}

void deleteNode(Node *z) {

Node *x, *y;

/*****************************

* delete node z from tree *
*****************************/

if (!z || z == NIL) return;

if (z->left == NIL || z->right == NIL) {
/* y has a NIL node as a child */
y = z;
} else {
/* find tree successor with a NIL node as a child */
y = z->right;
while (y->left != NIL) y = y->left;
}

/* x is y's only child */

if (y->left != NIL)
x = y->left;
else
x = y->right;

/* remove y from the parent chain */

x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;

if (y != z) z->data = y->data;

if (y->color == BLACK)
deleteFixup (x);

free (y);

}

Node *findNode(T data) {

/*******************************

* find node containing data *
*******************************/

Node *current = root;

while(current != NIL)
if(compEQ(data, current->data))
return (current);
else
current = compLT (data, current->data) ?
current->left : current->right;
return(0);
}

void main(int argc, char **argv) {

int a, maxnum, ct;
Node *t;

/* command-line:

*
* rbt maxnum
*
* rbt 2000
* process 2000 records
*
*/

maxnum = atoi(argv[1]);

for (ct = maxnum; ct; ct--) {

a = rand() % 9 + 1;
if ((t = findNode(a)) != NULL) {
deleteNode(t);
} else {
insertNode(a);
}
}
}