Yakuniy yozma (M. T. A). Ma’lumotlarning tarmoqli tuzilmalari: ta’riflar, asosiy tushunchalar

68. Daraxtda o’tish amallari: chap qismdaraxt - o’ng qism daraxt-ildiz.

Daraxt – bu siklik bo’lmagan (asiklik) bog’langan graf.

Graf – bu bo’sh bo’lmagan tugunlar va tugunlar juftliklarini bog’lovchi yoylar to’plami.

Bog’liqlik – har bir tugunlar juftligi orasida hech bo’lmaganda bitta yo’l (yoy) mavjud

Siklik bo’lmagan (Asiklik) – ixtiyoriy tugunlar juftligida faqat bitta yo’l mavjud.

Binar daraxt – har bir tugunga ikkitadan ko’p bo’lmagan tugunlar bog’langan tartiblangan daraxt.

Binar daraxt – har bir tugunga ikkitadan ko’p bo’lmagan tugunlar bog’langan tartiblangan daraxt.

::= ( ) |

::=

::=
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}
69. Binar daraxtdan tugunni o’chirish amalini tushuntirib bering: o’chirilayotgan tugun barg, oraliq tugun, ildiz.
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.
Daraxt tuguni o’chirilayotganda 3 ta holat bo’lishi mumkin:
1-holat. Topilgan tugun terminal (barg). Bu holatda tugun shunchaki o’chirib tashlanadi.
2-holat. Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.
3-holat. O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism daraxtni topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. Bunday qismdaraxt har doim mavjud bo’ladi. Bu
chap qism daraxtning eng o’ng tomondagi tuguni;
o’ng qism daraxtning eng chap tuguni.