Binar daraxtlar

Binar daraxtlar.
Binar daraxti shunday tuzilishga egaki, undagi har bir tugun ikkita tugundan ortiq bo’lmagan bir ajdod nasldan iborat bo’ladi. Daraxtning eng yuqori tuguni yagona ajdodsiz tugun hisoblanadi; u ildizli tugun dеb ataladi. N tugunli binar daraxti kam [log2N+1] tugunga ega (tugunlarning maksimal zichligida). Masalan, 15 tugunli to’la binar daraxtida bir ildiz, ikkinchi darajada 2 ta tugun, 3-darajada 4 ta tugun va 4-darajada 8 ta tugun bor; bizning tеngligimiz ham [log215]+1=[3.9]+1=4 darajani bеradi. Daraxtga yana bir tugunning qo’shilishi yangi darajaning hosil bo’lishiga olib kеladi va ularning soni tеng bo’ladi [log2 16] + 1 = [4] + 1 = 5. N tugunli eng katta binar daraxti N darajaga ega: bu daraxtning har bir tugunida bitta nasl bor (daraxtning o’zi ham oddiy ro’yxat ko’rinishiga ega).
Agar daraxtning darajalarini raqamlab chiqsak, ildiz 1 darajada dеb hisoblab, K raqamli darajada 2K-1 tuguni yotadi. J darajali (1 dan J gacha raqamlangan) to’la binar daraxtida hamma barglar J raqamli darajada yotadi va har bir tugunda birdan J-1 darajada ikkita to’g’ridan-to’g’ri nasl bor. J darajali to’la binar daraxtida 2J - 1 тугун бор. Bu axborot kеyinchalik ham sizga asqotishi mumkin. Bu formulalarni yaxshiroq tushunish uchun binar daraxtlarini chizishni va natijalaringizni yuqoridagi formulalar bilan solishtirishingizni maslahat bеramiz.
Ehtimolliklar.
Biz algoritmlarni kiruvchi ma'lumotlarga ko’ra tahlil qilmoqchimiz, buning uchun esa u yoki bu kiruvchi ma'lumotlar to’plami qanchalik ko’p uchrashini baholashimiz kеrak. Shu bilan birga, biz kiruvchi ma'lumotlar u yoki bu sharoitlarga to’gri kеlish extimolligi bilan ishlashimizga to’?ri kеladi. U yoki bu hodisaning extimolligi nol va bir orali?idagi sondan iborat, 0 extimolligi hodisa hеch qachon sodir bo’lmasligi,1 extimoli esa bo’lishi mumkinligini bildiradi. Agar bizga turli kiruvchi qiymatlarning soni aniq 10 ga tеngligi ma'lum bo’lsa, ishonch Bilan aytishimiz mumkinki, har qanday bunday kirishning extimolligi 0 va 1 oralig’ida bo’ladi, barcha extimolliklarning yig’indisi 1 ga tеng, chunki ulardan bittasi amalga oshishi mumkin. Agar har bir kirishning amalga oshish extimolligi bir xil bo’lsa, ulardan har birining extimolligi 0.1 ga tеng bo’ladi (10 dan 1 yoki 1/10).
Agar daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har bir tugun tuzilmaning ko`pi bilan 2ta tuguni bilan bog`langan bo`lsa, u holda bunday daraxt binar daraxt deyiladi.
Umumiy holda binary daraxt har bir elementi 4ta maydonga ega yozuv hisoblanadi.
Masalan, quyidagi kalit elementardan binar daraxt quramiz:
50, 46, 61, 48, 29, 55, 79. u quyidagi ko`riishga ega bo`ladi:
Izoh:
Binar daraxtda key(left_son).
оtа
Chаp o`g`il
O`ng o`g`il
Ta’rif 2. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi
Ta’rif 2. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi
Yuqorida hosil qilingan binary daraxtimiz ideal muvozanatlangan daraxtga misol bo`ladi.
Tarif 3. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari orasida farq 1 dan katta bo`lmasa, u holda bunday binary daraxt muvozanatlangan daraxt deyiladi:

m-o`lchamli daraxtni binar ko`rinishga keltirish

Ko`p o`lchamli daraxtni binary ko`rinishga keltirishning noformal algoritmi: Daraxtning har bir tugunida katta o`g`liga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.

• Bitta otaning barcha o`g`illari gorizontal chiziq bilan ulanadi.

• Hosil qilingan tuzilmada har bir katta o`g`il mazkur tugun pastida turgan tugun hisoblanadi. (agar u mavjud bo`lsa). Amallar ketma-ketligi quyida keltirilgan:

yoki
• Daraxt ko’ruvi (elementlarni ma’lum bir ko’rinishda tartiblash yoki chop etish);

• Daraxtga yangi tugun qo’yish;
• Daraxt tugunini o’chirish;
• Daraxt tugunini qidirish.

Binar daraxti ustida bajariladigan asosiy amallar.

Daraxt ko’ruvi

• Tog’ri (Yuqoridan quyiga). Ko’ruv quyidagi ketma-ketlikda bajariladi: A-B-C;
• Simmetrik (Chapdan o’ngga). Ko’ruv quyidagi ketma-ketlikda bajariladi: B-A-C.
• Teskari (quyidan yuqoriga). Ko’ruv quyidagi ketma-ketlikda bajariladi: B-C-A.
Daraxtga yangi tugun qo’shish
Daraxtga biron bir tugun qo’shishdan oldin daraxtga berilgan kalit bo’yicha qidiruvni amalga oshirish lozim bo’ladi. Agar berilgan kalitga teng kalitli tugun mavjud bo’lsa, u xolda dastur o’z ishini yakunlaydi, aks holda daraxtga tugun qo’yish amalga oshiriladi.
Eslatma: Daraxtda yangi tugun faqatgina ko’rsatgichlarini kamida bittasi bo’sh bo’lgan tugundan keyin qo’yiladi.
Binar daraxtdan elementlarni o’chirish.
Daraxt tuguni o’chrilayotganda 3 hil holat bo’lishi mumkin:
• Topilgan tugun terminal. Bu holatda tugun shunchaki o’chirib tashlanadi.
• Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.
• O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism daraxtlar zvenosini topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. Bunday zveno har doim mavjud bo’ladi. Bu
• Yoki chap qism daraxtning eng ‘ng tomondagi tuguni (ushbu zvenoga erishish uchun keying uchiga chap shoh orqali o’tib, navbatdagi uchlariga esa murojaat NIL bo’lmagunicha, faqatgina o’ng shohlari orqali o’tish zarur).
• Yoki o’ng qisim daraxtning eng chap tuguni (ushbu zvenoga erishish uchun keying uchta o’ng shoh orqali o’tib, navbatdagi uchlariga esa, murojaat NIL bo’lmaguncha, faqatgina chap shohlari orqali o’tish zarur).
Binar daraxtidan tugunni o’chirish.
Binar daraxtda qidiruv
Mazkur prodseduraning vazifasi shundan iboratki, u berigan kalit bo’yicha daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga kalit qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir tomonga yo’nalgan ro’yhat hosil qiladi (chiqish darajasi 1 bo’ladi, ya’ni yagona shohga ega),
Bu holatda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yhatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.
Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi.
Muvozanatlashgan Binar daraxt.
Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari va tugunlari soni teng bo’lsa, u holda bunday binar daraxt ideal muvozanatlashgan daraxt deyiladi.
Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari orasidagi farq birdan katta bo’lmasa, u holda bunday binar daraxt muvozanatlashgan daraxt deyiladi. Masalan:
Binar daraxtlar ustida bajariladigan amallar:
•daraxtni aylanib o’tish (daraxtda o’tish) (bunda, asosan, tugunlarni chop etish tushuniladi);
•daraxtga yangi tugun qo’yish;
•daraxt tugunini o’chirish;
•daraxt tugunini qidirish.
1-amal. Daraxtda o’tish.
Daraxtda o’tish asosan uchta ko’rinishi mavjud, ya’ni berilgan daraxtda:
To’g’ri o’tish: Ildiz »» Chap qismdaraxt »» O’ng qismdaraxt
Natijada hosil bo’lgan ro’yxat: {1, 2, 4, 8, 5, 9, 10, 3, 6, 7}
Teskari o’tish: Chap qismdaraxt »» Ildiz »» O’ng qismdaraxt
Natijada hosil bo’lgan ro’yxat: {8, 4, 2, 9, 5, 10, 1, 6, 3, 7}
Oxiridan o’tish: Chap qismdaraxt »» O’ng qismdaraxt »» Ildiz
Natijada hosil bo’lgan ro’yxat: {8, 4, 9, 10, 5, 2, 6, 7, 3, 1}
B daraxti va Binar daraxt o'rtasidagi farq
B daraxti va Ikkilik daraxti - bu ma'lumotlarning chiziqli bo'lmagan tuzili h turlari. Garchi atamalar o'x ha h bo'l a-da, lekin har jihatdan har xil.
B daraxti va Ikkilik daraxti - bu ma'lumotlarning chiziqli bo'lmagan tuzilish turlari. Garchi atamalar o'xshash bo'lsa-da, lekin har jihatdan har xil. Ikkilik daraxt, yozuvlar yoki ma'lumotlar RAM o'rniga disk o'rniga saqlanganda ishlatiladi, chunki RAMga kirish tezligi diskka qaraganda ancha yuqori. Boshqa tomondan, B-daraxti ma'lumotlar diskda saqlanganda, daraxtning balandligini kamaytirish va tugundagi shoxlarini ko'paytirish orqali kirish vaqtini qisqartirganda ishlatiladi.
B daraxti bilan ikkilik daraxtining yana bir farqi shundaki, B daraxti barcha tugun tugunlarini bir xil darajada bo'lishi kerak, ikkilik daraxt esa bunday cheklovga ega emas. Ikkilik daraxt maksimal 2 ta kichik daraxtga yoki tugunga ega bo'lishi mumkin, ammo B daraxtida M hech qanday kichik daraxt yoki tugunga ega bo'lishi mumkin, bu erda M - bu B daraxtining tartibi.
Taqqoslash jadvali
Taqqoslash uchun asos B daraxti Ikkilik daraxt Muhim cheklov Tugun
maksimal M bolalar tugunlari soniga ega bo'lishi mumkin (bu erda M - daraxtning tartibi). Tugun maksimal 2 tagacha daraxt bo'lishi mumkin. Ishlatilgan ma'lumotlar diskda saqlanganda ishlatiladi. Bu yozuvlar va ma'lumotlar RAMda saqlanganda ishlatiladi.
Daraxtning balandligi jurnalM N (bu erda m - M yo'l daraxtining tartibi) jurnal2 N
Ilova Ko'p DBMS-larda ma'lumotlar indekslarini kodlash, Kodni optimallashtirish, Huffman kodlash va boshqalar.
B daraxtining ta'rifi
B-daraxt - bu muvozanatli M-yo'l daraxti va u muvozanatli navli daraxt sifatida ham tanilgan. Bu tugunlar inorder traversal asosida tashkil etilgan ikkilik qidiruv daraxtiga o'xshaydi. B daraxtining kosmik murakkabligi O (n) dir. Kiritish va o'chirish vaqtining murakkabligi O (log n).
B daraxti uchun to'g'ri bo'lishi kerak bo'lgan ba'zi shartlar mavjud:
• Daraxtning balandligi iloji boricha minimal bo'lishi kerak.
• Daraxt barglari ustida hech qanday bo'sh daraxt bo'lmasligi kerak.
• Daraxtning barglari bir xil darajada bo'lishi kerak.
• Barcha tugunlarda ta'til tugunlaridan tashqari eng kam bola bo'lishi kerak.
M tartibidagi B daraxtining xususiyatlari
• Har bir tugunda maksimal M bolalar soni va minimal M / 2 bolalar soni yoki 2 dan maksimalgacha bo'lgan har qanday son bo'lishi mumkin.
• Har bir tugunda maksimal M-1 tugmachalari bo'lgan bolalarga qaraganda bitta tugmacha kam.
• Klavishlarning joylashishi tugunlar ichida ma'lum bir tartibda. Kalitning chap tomonida joylashgan subtree-dagi barcha tugmachalar kalitning oldingilari va kalitning o'ng tomonida joylashganlari vorislar deb ataladi.
• To'liq tugunni kiritish paytida daraxt ikki qismga bo'linadi va ota-ona tuguniga o'rtacha qiymati bo'lgan kalit qo'yiladi.
• Birlashtirish jarayoni tugunlar o'chirilganda amalga oshiriladi.
Ikkilik daraxtning ta'rifi
Ikkilik daraxt - bu daraxt tugunlari uchun eng ko'p ikkita ko'rsatgichga ega bo'lgan daraxt tuzilishi. Bu shuni anglatadiki, tugunning eng yuqori darajasi 2 ga teng va u erda nol yoki bir darajali tugun ham bo'lishi mumkin.
Ikkilik daraxtning ma'lum variantlari mavjud, masalan, qat'iy binar daraxt, to'liq ikkilik daraxt, kengaytirilgan binar daraxt va boshqalar.
• Ikkilamchi daraxt - bu har bir terminal bo'lmagan tugun chap pastki va o'ng pastki daraxtlarga ega bo'lishi kerak bo'lgan daraxt.
• Daraxt 2 ga ega bo'lish shartini qondirganda unga to'liq Ikkilik daraxt deyiladi men i daraja bo'lgan har bir darajadagi tugunlar.
• Tishli ikkilik - bu 0 tugunidan yoki 2 tugun sonidan iborat bo'lgan ikki tomonlama daraxt.
Yo'l harakati usullari
Daraxtlarni kesib o'tish - bu har bir tugun aniq bir marta muntazam ravishda tashrif buyurgan daraxtlar ma'lumotlari tarkibida amalga oshiriladigan eng tez-tez bajariladigan operatsiyalardan biridir.
• Tartibda: Ushbu daraxtni kesib o'tishda chap pastki daraxtga rekursiv ravishda tashrif buyuriladi, so'ngra ildiz tuguniga va oxirgi o'ng daraxtga tashrif buyuriladi.
• Oldindan buyurtma: Ushbu daraxtni kesib o'tishda dastlab ildiz tuguniga chap chap daraxtga va oxirgi o'ng daraxtga tashrif buyuriladi.
• Pochta buyurtmasi: Ushbu uslub chap subtree, keyin o'ng subtree va nihoyat ildiz tuguniga tashrif buyuradi.
Binar daraxtni vizuallashtirish
Binar daraxtni ko’rikdan o’tkazayotganda biz yuqorida har bir tugunni o’ngida va chapida turgan tugunlarni so’z bilan ifodaladik. Lekin bu usul bir muncha noqulay. Daraxtni vizual ko’rinishda ifodalash uni anglashning juda qulay usuli hisoblanadi. Daraxtni vizuallashtirishning grafik ko’rinishi va konsol oynasida ifodalash kabi turlari mavjud. Shundan konsol oynasida daraxtni vizuallashtirishni ko’rib chiqamiz. Bunda sonlar daraxt shaklida joylashtiriladi. Quyida bunday usulning dastur kodi keltirilgan.
void vizual(node *tree,int l)
{ int i;
if(tree!=NULL) {
vizual(tree->right,l+1);
for (i=1; i<=l; i++) cout<<" ";
cout
vizual(tree->left,l+1);
}
}

Misol: berilgan binar daraxtning balandligini aniqlang va muvozanatlang.
Dastur kodi:
#include
using namespace std;
class node{
public: int info;
node *left;
node *right;
};
int k=0;
int intrave(node *tree){
if (tree!=NULL){int a=NULL, b=NULL;
if (tree->left!=NULL){ a=tree->left->info; }
if (tree->right!=NULL){ b=tree->right->info; }
cout"<’ngida=>"<
intrave(tree->left);
intrave(tree->right); }
return 0;
}
int height(node *tree){
int h1,h2;
if (tree==NULL) return (-1);
else {
h1 = height(tree->left);
h2 = height(tree->right);
if (h1>h2) return (1 + h1);
else return (1 + h2);
}
}
int create_arr(node *tree,int *arr){
if(!tree) return 0;
else{
create_arr(tree->left,arr);
arr[k++]=tree->info;
create_arr(tree->right,arr);
}
}
node *new_tree(int *arr, int start, int end)
{
if(start>end) return NULL;
else {
int mid=(start+end)/2;
node *tree=new node;
tree->info=arr[mid];
tree->left=new_tree(arr,start,mid-1);
tree->right=new_tree(arr,mid+1,end);
return tree;
}
}
void vizual(node *tree,int l)
{ int i;
if(tree!=NULL) {
vizual(tree->right,l+1);
for (i=1; i<=l; i++) cout<<" ";
cout
vizual(tree->left,l+1);
}
}
int main()
{ int n,key,s; node *tree=NULL,*next=NULL;
cout<<"n="; cin>>n; int arr[n];
for(int i=0; i<="" i="">
node *p=new node;
node *last=new node;
cin>>s;
p->info=s;
p->left=NULL;
p->right=NULL;
if(i==0){tree=p; next=tree; continue; }
next=tree;
while(1)
{ last=next;
if(p->infoinfo)next=next->left;
else next=next->right;
if(next==NULL)break; }
if(p->infoinfo)last->left=p;
else last->right=p;}
cout<
intrave(tree);
cout<<"\nya'ni\n";
vizual(tree,0);
int h=height(tree);
cout<<"balandligi="<
create_arr(tree,arr);
for(int i=0;i
tree=new_tree(arr,0,k-1);
vizual(tree,0);
getch();
}

<="" i="">
Misol: berilgan binar daraxtdan ko’rsatilgankey kalitga mos tugunni o’chirish dasturini tuzing.
Asosiy dastur tanasi - int main()
1. i=0; n – daraxtga kiritiladigan elementlar sonini aniqlash. Daraxt ildizi ko’rsatkichi tree=NULL. Next yangi elementni joylashtiradigan shoxga o’tishda ishlatiladi va last next dan 1 qadam orqada yuradi.
2. Agar i bo’lsa, daraxtga kiritiladigan navbatdagi elementga qiymat kiritish va uni yangi p element info maydoniga yozish, left va right maydonlarga NULL yozish. Aks holda 8-qadamga o’tish.
3. Agar tree=NULL bo’lsa, p ni daraxt ildizi qilish, ya’ni tree=p va next=last=p.
4. Agar p->info next->info dan kichik bo’lsa, chap shoxga o’tish kerak, ya’ni last=next va next=next->left, aks holda o’ng shoxga o’tamiz, ya’ni last=next va next=next->right.
5. Agar next=NULL bo’lsa, 6-qadamga o’tish, aks holda 4-qadamga o’tish.
6. Agar p->infoinfo bo’lsa, last->left=p, aks holda last->right=p.
7. i++, 2-qadamga o’tish.
8. intrave(tree) funksiyasini ishlatish.
9. Key kalitga mos elementni daraxtdan o’chiradigan del(tree,key) funksiyasini ishlatish.
10. Natijaviy daraxtni ko’rikdan o’tkazish uchun intrave(tree) funksiyasini ishlatish va algoritmni yakunlash.
Dastur kodi:
#include
using namespace std;
class node{
public: int info;
node *left;
node *right;
};
int intrave(node *tree){
if (tree!=NULL){int a=0, b=0;
if (tree->left!=NULL){ a=tree->left->info; }
if (tree->right!=NULL){ b=tree->right->info; }
cout"<"<
intrave(tree->left);
intrave(tree->right); }
return 0;
}
node *del(node *tree,int key){
node *p=new node;
node *next=tree;
node *q=NULL;
while(next!=NULL)
{ if (next->info==key){cout<<"Binar daraxtda "<
p=next;break; }
if (next->info>key){ q=next; next=next->left; }
else {q=next;next=next->right;}
}
if(next==NULL) cout<<"tuzilmada izlangan element yo’q!!!"<
node *v=NULL,*t=NULL,*s=NULL;
if(p->left==NULL) v=p->right;
else if(p->right==NULL) v=p->left;
if((p->left!=NULL)&&(p->right!=NULL)){t=p; v=p->right; s=v->left;}
while(s!=NULL){
t=v;
v=s;
s=v->left;
}
if((t!=NULL)&&(t!=p)){
t->left=v->right;
v->right=p->right;
v->left=p->left;
}
if(t==p) v->left=p->left;
if(q==NULL){
couttree=v;
delete(p);
return tree;
}
if(p==q->left)
q->left=v;
else q->right=v;
delete(p); // o’chirilgan element joylashgan xotira yacheykasini tozalash
return tree;
}
int main()
{ int n,key,s; node *tree=NULL,*next=NULL;
cout<<"n="; cin>>n;
for(int i=0; i<="" i="">
node *p=new node;
node *last=new node;
cin>>s;
p->info=s;
p->left=NULL;
p->right=NULL;
if(i==0){tree=p; next=tree; continue; }
next=tree;
while(1)
{ last=next;
if(p->infoinfo)next=next->left;
else next=next->right;
if(next==NULL)break; }
if(p->infoinfo)last->left=p;
else last->right=p;}
cout<
intrave(tree);
cout<<"delete qilinadigan elementni kiriting \n";
cout<<"key="; cin>>key;
tree=del(tree,key);
intrave(tree);
getch();
}
Dasturning ishlashi natijasi:
n=10
8 3 9 12 10 15 13 11 16 14
8—chapida=>3 o’ngida=>9
3—chapida=>0 o’ngida=>0
9—chapida=>0 o’ngida=>12
12—chapida=>10 o’ngida=>15
10—chapida=>0 o’ngida=>11
11—chapida=>0 o‘ngida=>0
15—chapida=>13 o’ngida=>16
13—chapida=>0 o’ngida=>14
14—chapida=>0 o’ngida=>0
16—chapida=>0 o’ngida=>0
delete qilinadigan elementni kiriting
key=12
Binar daraxtda 12 Mavjud
8—chapida=>3 o’ngida=>9
3—chapida=>0 o’ngida=>0
9—chapida=>0 o’ngida=>13
13—chapida=>10 o’ngida=>15
10—chapida=>0 o’ngida=>11
11—chapida=>0 o’ngida=>0
15—chapida=>14 o’ngida=>16
14—chapida=>0 o’ngida=>0
16—chapida=>0 o’ngida=>0
Xulosa
B daraxti ikkilik va ikkilik qidiruv daraxtlari ustida ishlatiladi, buning asosiy sababi CPU protsessor yuqori o'tkazuvchanlik kanallari bilan keshga ulangan xotira iyerarxiyasidir, protsessor diskka past o'tkazuvchanlik kanali orqali ulanadi.