6-лаборатория: Бинар дарахтни мувозанатлаш Ишдан мақсад

Натижада қуйидагича мувозанатланган бинар дарахт хосил бўлади. Олдинги кўринишида дарахт баландлиги 4 га тенг эди. Энди эса 3 га тенг. Лекин бу алгоритмнинг бир мунча ноқулай

• Натижада қуйидагича мувозанатланган бинар дарахт хосил бўлади. Олдинги кўринишида дарахт баландлиги 4 га тенг эди. Энди эса 3 га тенг. Лекин бу алгоритмнинг бир мунча ноқулай
• лиги бор.
• - Олдин дарахтни чапдан
• ўнгга сканерлаб элементлар
• дан массив хосил қилиш керак.
• Бу эса хотирадан жой талаб этади.
• - Бу усулда дарахтни бошқатдан қуриш керак бўлади. Кейинчалик мувозанатлашнинг бошқа алгоритмлари ишлаб чиқилган.

• 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 қўшилди. Илдиз ва ўнг тугунни боғловчи ёйни чапга бурамиз.