Backtracking algoritmi

Backtracking – biror muammoni yechish uchun har bir ehtimoliy kombinatsiyalarni tekshirib chiquvchi va natija topilganda dasturni to’xtatuvchi rekursiv algoritm. U tree ichida qidiruv yoki tree’ning barcha uchlarini (barglarini) topish kabi amallarni bajarib, har bir tree’ning uchlarigacha tekshirib chiqadi.

R-way tries

Binary search tree

Ushbu mavzu string key’lar qidiruvi uchun mo’ljallangan ma’lumotlar tuzilmasi – tries (trays) haqida bo’ladi. Shu vaqtgacha ko’rib o’tgan ma’lumotlar tuzilmalaridan qidiruv uchun eng yaxshisi red-black tree – key’ni qidirish / qo’shish / o’chirish uchun O(log N) vaqtni kafolatlardi.

Graph ma’lumotlar tuzilmasi

Graph

Biz chiziqli bo’lmagan ma’lumotlar tuzilmasini o’rganishni boshlaganimizda, ularning bazaviy xarakteristikasini ko’rib chiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (hech bo’lmaganda sanoq tartibiga ega emas).

AVL-Tree ustida amallar. API yozish

AVL-Tree’ga tegishli bo’lgan amallar to’rtta – chapga burish; o’ngga burish; avval chapga, keyin o’ngga burish; avval o’ngga, keyin chapga burish. Ular haqida avvalgi maqolada to’xtalganimiz bois, bu yerda faqat kod yozish bilan cheklanamiz.