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

Режа:

• Бинар дарахтлар ҳақида тушунча.
• Бинар дарахтни хосил қилиш.
• Дарахтлар устидаги амаллар.
• Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish algoritmlari.Qidiruv binar daaxtini muvozanatlash algoritmlari.

Бинар дарахтлар, уларни хосил қилиш ва ундаги амаллар

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

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

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

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

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

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

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

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