Binar daraxtlar
Daraxt - bu qirralar bilan bog‘langan tugunlardan tashkil topgan ierarxik ma’lumotlar strukturasi.
Har bir tugun o‘zining kichik tugunlariga qiymat va havolalarni o‘z ichiga oladi.
Ikkilik daraxtlar
Ikkilik daraxt - bu daraxt ma’lumotlar strukturasining bir turi bo‘lib, unda har bir tugunda maksimal ikkita tugun, chap va o‘ng tugun bo‘lishi mumkin.
Ushbu cheklov, ya’ni tugunda ko‘pi bilan ikkita tugun bo‘lishi mumkin, bu bizga ko‘p afzalliklarni beradi:
- Ketish, qidirish, qo‘shish va o‘chirish kabi algoritmlarni tushunish, amalga oshirish va tezroq ishlash osonroq bo‘ladi.
- Ikkilik qidiruv daraxtida (BST) saralangan ma’lumotlarni saqlash qidiruvni juda samarali qiladi.
- Daraxtlarni muvozanatlash, masalan, AVL Binary Tree-dan foydalangan holda, cheklangan miqdordagi tugunlar bilan qilish osonroq.
- Ikkilik daraxtlar massivlar sifatida taqdim etilishi mumkin, bu daraxtni xotirani yanada samarali qiladi.
Ikkilik daraxtni amalga oshirish
Yuqoridagi ikkilik daraxtni bog‘langan ro‘yxatga (Linked List) o‘xshash tarzda amalga oshirish mumkin, faqat har bir tugunni bitta keyingi tugunga bog‘lash o‘rniga, har bir tugun chap va o‘ng farzand tugunlariga bog‘lanadigan tuzilma yaratamiz.
Misol
Pythonda ikkilik daraxt yarating:
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD
nodeB.left = nodeE
nodeB.right = nodeF
nodeF.left = nodeG
# Test
print("root.right.left.data:", root.right.left.data)
Misolni ishga tushirish »
Ikkilik daraxtlarning turlari
Ikkilik daraxtlarning qanday tuzilishi mumkinligini yaxshiroq tushunish uchun muhokama qilish kerak bo‘lgan turli xil variantlar yoki turlar mavjud.
Ikkilik daraxtlarning har xil turlarini ham hozir eslatib o‘tish kerak, chunki bu so‘zlar va tushunchalar qo‘llanmada keyinroq qo‘llaniladi.
Quyida Binary Tree tuzilmalarining har xil turlari haqida qisqacha tushuntirishlar berilgan va tushuntirishlar quyida iloji boricha tushunishni osonlashtirish uchun ushbu turdagi tuzilmalarning chizmalari keltirilgan.
Muvozanatli Ikkilik daraxtning chap va o‘ng pastki daraxt balandligi o‘rtasida daraxtdagi har bir tugun uchun ko‘pi bilan 1 ta farq bor.
To‘liq Ikkilik daraxtda tugunlar bilan to‘la barcha darajalar mavjud, oxirgi darajadan tashqari, u ham to‘la yoki chapdan o‘ngga to‘ldirilishi mumkin. To‘liq Ikkilik daraxtning xususiyatlari uning muvozanatli ekanligini anglatadi.
To‘liq Ikkilik daraxt - bu har bir tugun 0 yoki 2 ta tugunga ega bo‘lgan daraxt turi.
Mukammal Ikkilik daraxtda barcha barg tugunlari bir xil darajada bo‘ladi, ya’ni barcha darajalar tugunlar bilan to‘la va barcha ichki tugunlarda ikkita tugun tugunlari mavjud. Mukammal Ikkilik daraxtning xususiyatlari uning ham to‘liq, muvozanatli va to‘liq ekanligini bildiradi.
Ikkilik daraxtning o‘tishi
Har bir tugunni, bir vaqtning o‘zida bitta tugunni ziyorat qilish orqali Daraxtdan o‘tish traversal deb ataladi.
Massivlar va bog‘langan listlar chiziqli ma’lumotlar tuzilmalari bo‘lganligi sababli, ularni kesib o‘tishning faqat bitta aniq usuli bor: birinchi element yoki tugundan boshlang va ularning barchasiga tashrif buyurmaguningizcha keyingisiga tashrif buyurishni davom eting.
Ammo Daraxt turli yo‘nalishlarda (chiziqli bo‘lmagan) shoxlanishi mumkinligi sababli, daraxtlarni kesib o‘tishning turli usullari mavjud.
Daraxtlarni kesish usullarining ikkita asosiy toifasi mavjud:
Breadth First Search (BFS) - bu daraxtning keyingi darajasiga o‘tishdan oldin bir xil darajadagi tugunlarga tashrif buyurilganda. Bu daraxt ko‘proq yon tomonga o‘rganilganligini anglatadi.
Chuqurlikdagi birinchi qidiruv (DFS) - bu o‘tishning daraxt bo‘ylab barg tugunlarigacha harakatlanishi va daraxt shoxlarini novdalar bo‘yicha pastga qarab o‘rganishdir.
DFS translatsiyalarining uch xil turi mavjud:
- oldindan tartib
- tartibda
- tartibdan keyin
Oldindan tartib bering Transvers of Binary Trees
Oldindan tartib berish - bu har bir tugunga ma’lum tartibda tashrif buyuriladigan chuqurlikdagi birinchi qidiruv turi.
Pre-order o‘tish avval ildiz tuguniga tashrif buyuradi, so‘ngra chap pastki daraxtda rekursiv pre-order o‘tishni, undan keyin o‘ng pastki daraxtda rekursiv pre-order o‘tishni amalga oshiradi. U daraxt nusxasini yaratish, ifoda daraxtining prefiks yozuvini olish va boshqa vazifalar uchun ishlatiladi.
Bu o‘tish "oldindan" tartibdir, chunki tugun chap va o‘ng pastki daraxtlarning rekursiv oldindan tartib o‘tishidan "oldin" tashrif buyuriladi.
Oldindan tartib berish uchun kod quyidagicha ko‘rinadi:
Misol
Pre-order aylanib chiqish:
def preOrderTraversal(node):
if node is None:
return
print(node.data, end=", ")
preOrderTraversal(node.left)
preOrderTraversal(node.right)
Misolni ishga tushirish »
Chop etilishi kerak bo‘lgan birinchi tugun R tugunidir, chunki Oldindan tartib O‘tkazish joriy tugunga (4-qator) birinchi bo‘lib tashrif buyurish yoki chop etish orqali, chap va o‘ng tugunlarni rekursiv ravishda chaqirishdan oldin ishlaydi (5 va 6-qator).
preOrderTraversal() funksiyasi o‘ng pastki daraxtga o‘tishdan oldin (6-qator) chap pastki daraxtni rekursiv ravishda (5-qator) kesib o‘tishni davom ettiradi. Shunday qilib, chop etiladigan keyingi tugunlar "A" va keyin "C" dir.
Birinchi martanodeargumenti None bo‘lganda,nodeC ning chap bolasi argument sifatida berilganda (C ning chap bolasi yo‘q).
C ning chap bolasini chaqirganda None birinchi marta qaytarilgandan so‘ng, C ning o‘ng bolasi ham Noneni qaytaradi va keyin rekursiv chaqiruvlar orqaga qaytishda davom etadi, shunda A ning o‘ng bolasi D keyingi chop etiladi.
R ning o‘ng pastki daraxtidagi qolgan tugunlar chop etilishi uchun kod qayta tarqalishda davom etadi.
Ikkilik daraxtlarning tartibli o‘tishi
In-tartibli o‘tish - bu chuqurlikdagi birinchi qidiruv turi bo‘lib, har bir tugunga ma’lum tartibda tashrif buyuriladi.
In-order o‘tish chap pastki daraxtda rekursiv in-order o‘tishni amalga oshiradi, ildiz tuguniga tashrif buyuradi va nihoyat o‘ng pastki daraxtda rekursiv in-order o‘tishni amalga oshiradi. Bu o‘tish asosan ikkilik qidiruv daraxtlari (Binary Search Tree) uchun qo‘llaniladi, chunki u qiymatlarni o‘sish tartibida qaytaradi.
Ushbu o‘tishni "tartibda" qiladigan narsa shundaki, tugun rekursiv funksiya chaqiruvlari orasida tashrif buyuriladi. Tugunga chap pastki daraxtning In-tartibli o‘tishdan keyin va o‘ng pastki daraxtning In-tartibli o‘tishdan oldin tashrif buyuriladi.
In-order Traversal uchun kod quyidagicha ko‘rinadi:
Misol
Tartib bo‘yicha o‘tishni yarating:
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
Misolni ishga tushirish »
inOrderTraversal() funksiyasi argument None bo‘lguncha va funksiya qaytguncha (2-3-qator) argument sifatida joriy chap tugun bilan o‘zini chaqirishni davom ettiradi.
Birinchi martanodeargumenti None bo‘lganda,nodeC ning chap bolasi argument sifatida berilganda (C ning chap bolasi yo‘q).
Shundan so‘ng, C tugunining data qismi chop etiladi (5-qator), ya’ni "C" birinchi bosiladigan narsadir.
Keyin, C tugunining o‘ng bolasi argument sifatida beriladi (6-qator), bu None, shuning uchun funksiya chaqiruvi boshqa hech narsa qilmasdan qaytadi.
'C' chop etilgandan so‘ng, oldingi inOrderTraversal() funksiya chaqiruvlari ishlashni davom ettiradi, shunda 'A' chop etiladi, keyin 'D', keyin 'R' va hokazo.
Ikkilik daraxtlarning tartibdan keyingi o‘tishi
tartibdan keyingi o‘tish - bu har bir tugunga ma’lum tartibda tashrif buyuriladigan chuqurlikdagi birinchi qidiruv turi.
Post-order o‘tish chap pastki daraxt va o‘ng pastki daraxtda rekursiv post-order o‘tishni bajaradi, so‘ngra ildiz tuguniga tashrif buyuradi. U daraxtni o‘chirish, ifoda daraxtining postfiks yozuvini olish va boshqa vazifalar uchun ishlatiladi.
Ushbu o‘tishni "post" qiladigan narsa shundaki, tugunga tashrif buyurish chap va o‘ng tugunlar rekursiv chaqirilgandan "keyin" amalga oshiriladi.
Post-order Traversal uchun kod quyidagicha ko‘rinadi:
Misol
Post-order Traversal:
def postOrderTraversal(node):
if node is None:
return
postOrderTraversal(node.left)
postOrderTraversal(node.right)
print(node.data, end=", ")
Misolni ishga tushirish »
postOrderTraversal() funksiyasi node argumenti sifatida C ning chap bolasi node chaqirilganda None qaytarilmaguncha, chap pastki daraxt bo‘ylab rekursiv (4-qator) o‘tishni davom ettiradi.
C ning chap asosiy tuguni Noneni qaytargandan so‘ng, 5-qator ishlaydi va C ning o‘ng qo‘shimcha tuguni Noneni qaytaradi va keyin 'C' harfi chop etiladi (6-qator).
Bu shuni anglatadiki, C ga uning chap va o‘ng tugunlari o‘tgandan keyin "keyin" tashrif buyuriladi yoki chop etiladi, shuning uchun u "post" tartibini o‘tish deb ataladi.
postOrderTraversal() funksiyasi oldingi rekursiv funksiya chaqiruvlariga qaytishda davom etadi, shuning uchun keyingi chop etiladigan tugun 'D', keyin esa 'A' bo‘ladi.
Funksiya barcha tugunlar chop etilgunga qadar yoki tashrif buyurilguncha orqaga va chop etish tugunlarini tarqatishda davom etadi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!