Рекурсив маълумотлар тузилмаси

Режа:

• Бинар дарахтлар ҳақида тушунча.
• Кўп ўлчамли дарахтни бинар кўринишга келтириш.
• Дарахтлар устидаги амаллар.

7-Мавзу: Бинар дарахтлар ва ундаги амаллар

Бинар дарахтлар ҳақида тушунча

Def.1.
Агар дарахтни ташкил этувчи элемент (тугун)лардан кўпи билан иккита шоҳ чиқса, яъни ҳар бир тугун тузилманинг кўпи билан иккита тугуни билан боғланган бўлса, у ҳолда бундай дарахтга бинар дарахт дейилади.
Эслатма
Умумий ҳолда бинар дарахт ҳар бир элемент тўртта майдонга эга ёзув ҳисобланади.
Масалан, қуйидаги калитли элементлардан бинар дарахт қурамиз:
50, 46, 61, 48, 29, 55, 79. У қуйидаги кўринишга эга бўлади:
Изоҳ
Бинар дарахтда key(left_son).
ота
чап ўғил
ўнг ўғил

Таъриф 2. Агар дарахтнинг ўнг ва чап қисм дарахтлари босқичлари ва вазни тенг бўлса, у ҳолда бундай бинар дарахт идеал мувозанатланган дарахт дейилади.

Таъриф 2. Агар дарахтнинг ўнг ва чап қисм дарахтлари босқичлари ва вазни тенг бўлса, у ҳолда бундай бинар дарахт идеал мувозанатланган дарахт дейилади.

Юқорида хосил қилган бинар дарахтимиз идеал мувозанатланган дарахтга мисол бўлади.

Таъриф 3. Агар дарахтнинг ўнг ва чап қисм дарахтлари босқичлари орасидаги фарқ бирдан катта бўлмаса, у ҳолда бундай бинар дарахт мувозанатланган дарахт дейилади (қуйидаги чизмага қаранг).

m-ўлчамли дарахтни бинар кўринишга келтириш
Кўп ўлчамли дарахтни бинар кўринишга келтиришнинг ноформал алгоритми:

• Дарахтнинг хар бир тугунида катта ўғилга мос четки чап шохидан ташқари барча шохлари кесиб ташланади.
• Битта ота барча ўғиллари горизонтал чизиқ билан уланади.
• Хосил қилинган тузилманинг хар бир тугунида катта ўғил мазкур тугун пастида турган тугун хисобланади (агар у мавжуд бўлса).

Алгоритм амаллар кетма-кетлиги қуйида келтирилган.
ёки

• дарахт кўруви (элементларини маълум бир кўринишда тартиблаш ёки чоп этиш);
• дарахтга янги тугун қўйиш;
• дарахт тугунини ўчириш;
• дарахт тугунини қидириш.

Бинар дарахт устида бажариладиган асосий амаллар
Дарахт кўруви

• Тўғри (Юқоридан қуйига). Кўрув қуйидаги кетма-кетликда бажарилади: A-B-C;
• Симметрик (Чапдан ўнгга). Кўрув қуйидаги кетма-кетликда бажарилади: B-A-C.
• Тескари (Қуйидан юқорига). Кўрув қуйидаги кетма-кетликда бажарилади: B-C-A.

Дарахтга янги тугун қўйиш

Дарахтга янги тугун қўйиш

Дарахтга бирор бир тугун қўйишдан олдин дарахтда берилган калит бўйича қидирувни амалга ошириш лозим бўлади. Агар берилган калитга тенг калитли тугун мавжуд бўлса, у ҳолда дастур ўз ишини якунлайди, акс ҳолда дарахтга тугун қўйиш амалга оширилади.

Эслатма: Дарахтда янги тугун фақатгина кўрсаткичларини камида биттаси бўш бўлган тугундан кейин қўйилади.

Бинар дарахтдан элементни ўчириш
 
Дарахт тугуни ўчирилаётганда 3 ҳил ҳолат бўлиши мумкин:

• Топилган тугун терминал (барг). Бу ҳолатда тугун шунчаки ўчириб ташланади.
• Топилган тугун фақатгина битта ўғилга эга. У ҳолда ўғил ота ўрнига жойлаштирилади.
• Ўчирилаётган тугун иккита ўғилга эга. Бундай ҳолатда шундай қисм дарахтлар звеносини топиш лозимки, уни ўчирилаётган тугун ўрнига қўйиш мумкин бўлсин. Бундай звено ҳар доим мавжуд бўлади. Бу
• ёки чап қисм дарахтнинг энг ўнг томондаги тугуни (ушбу звенога эришиш учун кейинги учига чап шоҳ орқали ўтиб, навбатдаги учларига эса, мурожаат NIL бўлмагунча, фақатгина ўнг шоҳлари орқали ўтиш зарур).
• ёки ўнг қисм дарахтнинг энг чап тугуни (ушбу звенога эришиш учун кейинги учига ўнг шоҳ орқали ўтиб, навбатдаги учларига эса, мурожаат NIL бўлмагунча, фақатгина чап шоҳлари орқали ўтиш зарур).

Бинар дарахтдан тугунни ўчириш

Бинар дарахтда қидирув

Бинар дарахтда қидирув

Мазкур процедуранинг вазифаси шундан иборатки, у берилган калит бўйича дарахт тугуни қидирувини амалга оширади. Қидирув операциясининг давомийлиги дарахт тузилишига боғлиқ бўлади. Ҳақиқатдан, агар элементлар дарахтга калит қийматлари ўсиш (камайиш) тартибида келиб тушган бўлса, у ҳолда дарахт бир томонга йўналган рўйхат ҳосил қилади (чиқиш даражаси бир бўлади, яъни ягона шоҳга эга), масалан:

Бу ҳолда дарахтда қидирув вақти, бир томонлама йўналтирилган рўйхатдаги каби бўлиб, ўртача қараб чиқишлар сони N/2 бўлади.

Агар дарахт мувозанатланган бўлса, у ҳолда қидирув энг самарали натижа беради. Бу ҳолда қидирув дан кўп бўлмаган элементларни кўриб чиқади.

9-Мавзу бўйича назорат саволлари

• Бинар дарахт тушунчаси.
• Бинар дарахт қандай хосил қилинади?
• Кўп ўлчамли дарахтни қандай қилиб бинар дарахт кўринишига келтириш мумкин?
• Дарахтда қандай амалларни бажариш мумкин?
• Дарахтда кўрув қандай амалга оширилади?