Axborot texnologiyalari universiteti urganch filiali kompuyuter injineringi fakulteti kompyuter injieringi yo

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT

AXBOROT TEXNOLOGIYALARI UNIVERSITETI

URGANCH FILIALI KOMPUYUTER INJINERINGI

FAKULTETI KOMPYUTER INJIERINGI YO’NALISHI

911_19 GURUH TALABASI EGAMBERGANOV JAHONGIRNING

MALUMOTLAR TUZILMASI VA ALGORITMI FANIDAN

Mavzu: Ikkilik daraxtlar bilan ishlash (yaratish, qo'shish, qidirish, tarash)

Topshirdi: Egamberganov Jahongir

Qa’bul qildi: Temur Turdiyev

Urganch-2020

Reja

1) Ikkilik daraxtlar tog'risida tushuncha.

2)Ikkilik daraxtlarni qurish.

3)Ikkilik daraxtlar ustida yaratish, qo'shish, qidirish,tarash.

Ikkilik qidiruv daraxtlari odatda to'plamlar va assotsiativ massivlarni amalga oshirish uchun ishlatiladi (masalan, C ++ da set va map yoki java-da TreeSet va TreeMap). Keyinchalik murakkab dasturlarga arqonlar (kelgusi maqolamda aytib o'taman), turli xil hisoblash geometriyasi algoritmlari, asosan "skanerlash liniyasi" asosidagi algoritmlar kiradi.

Ushbu maqolada daraxtlar assotsiativ massivni amalga oshirish misolida ko'rib chiqiladi. Assotsiativ massiv - bu indekslar (odatda kalitlar deb ataladi) o'zboshimchalik bilan bo'lishi mumkin bo'lgan umumiy massiv.

Xo'sh, boshlaymiz

Ikkilik daraxt tugunlardan va ular orasidagi bog'lanishlardan iborat. Aniqrog'i, daraxtda maxsus vertex bor va har bir tepada chap va o'ng o'g'illari bo'lishi mumkin. Bu so'zlar bilan biroz murakkab bo'lib tuyuladi, lekin rasmga nazar tashlasangiz, hamma narsa aniq bo'ladi:

Bu daraxtda A tepalikning ildizi bo'ladi. Ko'rinib turibdiki, D tepasida chap o'g'li yo'q, B tepasida o'ng o'g'li bor, va G, H, F tepalari va menda ikkalasi ham. O'g'ilsiz cho'qqilar odatda barglar deb nomlanadi. Har bir X tepalik o'z tepasi, uning o'g'illari, o'g'illarining o'g'illari va boshqalardan iborat bo'lgan daraxt bilan bog'lanishi mumkin. Bunday daraxtga ildiz otgan X daraxt deyiladi, X ning chap va o'ng pastki daraxtlari navbati bilan X ning chap va o'ng o'g'illarida ildiz otgan daraxtlardir.E'tibor bering, agar Xda tegishli o'g'il bo'lmasa, bunday daraxtlar bo'sh bo'lishi mumkin. Daraxtdagi ma'lumotlar uning uchida saqlanadi. Dasturlarda daraxt tugunlari odatda ma'lumotlar va chap va o'ng bolalarga ikkita havolani saqlaydigan tuzilma bilan ifodalanadi. Yo'qolgan tepalar null yoki maxsus barg konstruktori bilan belgilanadi:

data Ord key => BSTree key value = Leaf | Branch key value (BSTree key value) (BSTree key value)

deriving (Show)

static class Node {

T1 key;

T2 value;

Node left, right;



Node(T1 key, T2 value) {

this.key = key;

this.value = value;

Misollardan ko'rinib turibdiki, biz bir-biri bilan taqqoslanadigan kalitlarni talab qilamiz ( Ord ahaskell va T1 implements Comparablejava-da). Bularning barchasi tasodifiy emas - daraxt foydali bo'lishi uchun unda ba'zi qoidalarga muvofiq ma'lumotlar saqlanishi kerak. Ushbu qoidalar nima? Hammasi oddiy: agar x tugmachasi X tepasida saqlansa, chap (o'ng) kichik daraxtda faqat x dan kichikroq (mos ravishda kattaroq) tugmalar saqlanishi kerak. Keling

, misol keltiraylik: bunday buyruq bizga nimani beradi? Daraxtda kerakli x tugmachasini osongina topishimiz mumkin! X-ni ildizdagi qiymat bilan taqqoslash kifoya. Agar ular teng bo'lsa, unda biz kerakli narsani topdik. Agar x kamroq (ko'proq) bo'lsa, u faqat chap (navbati bilan, o'ng) kichik daraxtda paydo bo'lishi mumkin. Masalan, daraxtdan 17 raqamini qidiryapmiz deylik:

l

qiymatni kalit orqali qabul qiladigan funktsiya:

get :: Ord key => BSTree key value -> key -> Maybe value

get Leaf _ = Nothing

get (Branch key value left right) k

| k < key = get left k

| k > key = get right k

| k == key = Just value

public T2 get(T1 k) {

Node x = root;

while (x != null) {

int cmp = k.compareTo(x.key);

if (cmp == 0) {

return x.value;

}

if (cmp < 0) {

x = x.left;

} else {

x = x.right;

}

}

return null;