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

лиги бор.

- Олдин дарахтни чапдан

ўнгга сканерлаб элементлар

дан массив хосил қилиш керак.

Бу эса хотирадан жой талаб этади.

- Бу усулда дарахтни бошқатдан қуриш керак бўлади. Кейинчалик мувозанатлашнинг бошқа алгоритмлари ишлаб чиқилган.

19
30
23
15
3
12
29
44
16

Мувозанатлаш алгоритмлари

Дарахтга янги элемент қўшилгач, тугунларнинг мувозанат коэффициентларини янгилаб чиқиш керак бўлади. Агар биронта тугуннинг бу параметри 2 ёки -2 га тенг бўлса, у холда бу қисм дарахтни буриш усули билан мувозанатлаш керак. Буриб мувозанатлаш алгоритмининг бир нечта усуллари мавжуд.

R – бир марта ўнгга бураш ;

L – бир марта чапга бураш ;

LR – икки марта чап-ўнгга бураш;

RL – икки марта ўнг-чапга бураш.

R – бир марта ўнгга бураш

• Чап қисмдарахтга 1 қўшилди
• Дарахт мувозанатланмаган

H(Left)=1 > H(Right)=-1

Ўнг қисмдарахт баландлигини ошириш керак.

R – бир марта ўнгга бураш

Илдиз ва чап тугунни боғловчи ёйни ўнгга бурамиз. Дарахт мувозанатланди..

R – бир марта ўнгга бураш

• Чап қисм дарахтга янги Х элемент қўшилди.
• Дарахт мувозанатланмаган

H(Left) > H(Right)

R – бир марта ўнгга бураш

L – бир марта чапга бураш

• Ўнг қисмдарахтга 3 қўшилди. Илдиз ва ўнг тугунни боғловчи ёйни чапга бурамиз.

L – бир марта чапга бураш

Ўнг қисмдарахтга янги элемент Х қўшилди.
Илдиз ва ўнг тугунни бирлаштирувчи ёйни чапга бурамиз.

LR – икки марта чап-ўнгга бураш

• Ушбу алгоритм илдиз чап тугунининг ўнг қисмдарахтига янги элемент киритилганда қўлланилади.
• 1. Р нинг чап қисмини чапга L буриш

LR – икки марта чап-ўнгга бураш

• 2. Янги дарахтнинг Р тугунини ўнгга R буриш

Дарахт мувозанатланди

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

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