Minimal narxli daraxt skeleti dasturiy ta’minotini tuzish

Daraxt grafik va chiziqsiz ro’yhat shaklidagi tasvirlanishi.

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

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

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

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

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

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

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

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

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

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