Бинардык издөө дарагын ишке ашыруу

2024 Автор: Angel Austin | [email protected]. Акыркы өзгөртүү: 2023-12-17 05:34

Бинардык издөө дарагы - түйүндөр, оң жана сол башка түйүндөргө эки шилтемени камтыган структураланган маалымат базасы. Түйүндөр класстын маалыматтары бар объектиси, ал эми NULL дарактын аягын белгилеген белги.

Ал көбүнчө BST деп аталат, анын өзгөчө касиети бар: тамырдан чоңураак түйүндөр анын оң жагында, кичирээктери сол жагында жайгашкан.

Жалпы теория жана терминология

Бинардык издөө дарагында ар бир түйүн, тамырдан тышкары, бир түйүндөн экинчи түйүнгө багытталган чети менен туташты, ал ата-эне деп аталат. Алардын ар бири балдар деп аталган түйүндөрдүн ыктыярдуу санына туташтырылышы мүмкүн. «Балалары» жок түйүндөр жалбырак (тышкы түйүн) деп аталат. Жалбырак эмес элементтер ички деп аталат. Ата-энеси бир болгон түйүндөр бир туугандар. Эң жогорку түйүн тамыр деп аталат. BSTде ар бир түйүнгө бир элемент ыйгарыңыз жана алар үчүн атайын касиет коюлганын текшериңиз.

Дарак терминологиясы:

1. Түйүндүн тереңдиги - тамырдан ага чейин аныкталган четтердин саны.
2. Түйүндүн бийиктиги - андан эң терең жалбыракка чейин аныкталган четтердин саны.
3. Дарактын бийиктиги тамырдын бийиктиги менен аныкталат.
4. Бинардык издөө дарагы - бул өзгөчө дизайн, ал бийиктик менен түйүндөрдүн санынын эң жакшы катышын камсыз кылат.
5. Бийиктиги h эң көп N түйүн менен O (журнал N).

Сиз муну ар бир деңгээлдеги түйүндөрдү тамырынан баштап санап, алардын эң көп санын камтыса, аны оңой далилдей аласыз: n=1 + 2 + 4 + … + 2 с-1 + 2 ч=2 ч + 1 - 1 Муну h үчүн чечүү h=O (log n) берет.

Жыгачтын пайдасы:

1. Дайындардын структуралык байланыштарын чагылдырыңыз.
2. Иерархияларды көрсөтүү үчүн колдонулат.
3. Натыйжалуу орнотууну жана издөөнү камсыз кылыңыз.
4. Дарактар - өтө ийкемдүү маалымат, алар аз күч жумшап, ички дарактарды жылдырууга мүмкүндүк берет.

Издөө ыкмасы

Жалпысынан, маанинин BSTде экенин аныктоо үчүн, анын тамырынан бинардык издөө дарагын баштап, анын талаптарга жооп берерин аныктаңыз:

• тамырында бол;
• тамырдын сол ички дарагында болуңуз;
• тамырдын оң ички дарагында.

Эгерде эч кандай базалык регистр канааттандырылбаса, рекурсивдүү издөө тиешелүү ички даракчада аткарылат. Негизи эки негизги вариант бар:

1. Дарак бош - false кайтарылат.
2. Мааниси тамыр түйүнүндө - чындыкты кайтарыңыз.

Белгилей кетчү нерсе, иштелип чыккан схемасы бар бинардык издөө дарагы дайыма тамырдан жалбыракка чейинки жолдо издей баштайт. Эң начар учурда жалбыракка чейин барат. Демек, эң начар убакыт дарактын бийиктиги болгон тамырдан жалбыракка чейинки эң узун жолдун узундугуна пропорционалдуу. Жалпысынан, бул даракта сакталган маанилердин санынын функциясы катары издөөгө канча убакыт кетээрин билишиңиз керек болот.

Башкача айтканда, БСТдеги түйүндөрдүн саны менен дарактын бийиктигинин ортосунда анын "формасына" жараша байланыш бар. Эң начар учурда, түйүндөрдө бир гана бала бар, ал эми тең салмактуу экилик издөө дарагы - бул шилтемеленген тизме. Мисалы:

50

/

10

15

30

/

20

Бул дарактын 5 түйүнү бар жана бийиктиги=5. 16-19 жана 21-29 диапазонундагы маанилерди табуу үчүн тамырдан жалбыракка (20 маанисин камтыган түйүн) төмөнкү жол керек болот, б.а., ал түйүндөрдүн санына пропорционалдуу убакытты талап кылат. Эң жакшы дегенде, алардын бардыгынын 2 баласы бар жана жалбырактары бир тереңдикте жайгашкан.

Бул бинардык издөө дарагында 7 түйүн бар жана бийиктиги=3. Жалпысынан мындай дарактын (толук дарактын) бийиктиги болжол менен log 2 (N) болот, мында N - дарактагы түйүндөрдүн саны. 2 журналынын (N) мааниси - нөлгө жеткенге чейин N канча жолу бөлүнө турган (2) саны.

Корытындылоо: BSTде издөө үчүн эң начар убакыт - O (дарактын бийиктиги). Эң начар "сызыктуу" дарак - O(N), мында N - дарактагы түйүндөрдүн саны. Эң жакшысы "толук" дарак - O(log N).

BST бинардык кыстарма

Кайсыл жерде болуш керек деп ойлонуп жатамжаңы түйүн BSTде жайгашкан, сиз логиканы түшүнүшүңүз керек, ал колдонуучу аны тапкан жерге жайгаштырылышы керек. Мындан тышкары, сиз эрежелерди эстен чыгарбоо керек:

1. Дубликацияга жол берилбейт, кайталанма маанини киргизүү аракети өзгөчө кырдаалды жаратат.
2. Ачык киргизүү ыкмасы иш жүзүндө киргизүү үчүн жардамчы рекурсивдүү "жардамчы" ыкмасын колдонот.
3. Жаңы маани камтыган түйүн ар дайым BSTде жалбырак катары киргизилет.
4. Ачык кыстаруу ыкмасы жараксыздыкты кайтарат, бирок жардамчы ыкма BSTnodeду кайтарат. Ал муну ага өткөн түйүн нөл болгон учурду иштетүү үчүн кылат.

Жалпысынан, жардамчы ыкмасы баштапкы экилик издөө дарагы бош болсо, натыйжа бир түйүндүү дарак болорун көрсөтөт. Болбосо, натыйжа аргумент катары берилген түйүнгө көрсөткүч болот.

Бинарлык алгоритмде жок кылуу

Сиз күткөндөй эле, элементти жок кылуу үчүн алынып салынуучу маани камтылган түйүндү табуу кирет. Бул коддо бир нече нерсе бар:

1. BST жардамчы, ашыкча жүктөлгөн жок кылуу ыкмасын колдонот. Эгерде сиз издеп жаткан элемент даракта жок болсо, анда жардамчы метод акыры n==нөл менен чакырылат. Бул ката деп эсептелбейт, бул учурда дарак жөн эле өзгөрбөйт. Өчүрүү жардамчы ыкмасы маанини кайтарат - жаңыртылган даракка көрсөткүч.
2. Жалбырак алынып салынганда, бинардык издөө дарагынан алып салуу анын ата-энесинин тиешелүү көмөкчү көрсөткүчүн нөлгө, ал эми алынып салынганы болсо, тамырды нөлгө коёт.түйүн тамыр жана анын балдары жок.
3. Жок кылуу чалуу төмөнкүлөрдүн бири болушу керек экенин эске алыңыз: root=жок кылуу (root, ачкыч), n.setLeft (delete (n.getLeft (), ачкыч)), n.setRight (Delete(n. getRight(), ачкыч)). Ошентип, үч учурда тең жок кылуу ыкмасы жөн гана нөлдү кайтарганы туура.
4. Жок кылына турган маанини камтыган түйүндү издөө ийгиликтүү аяктаганда, үч вариант бар: жок кылынуучу түйүн жалбырак (балдары жок), өчүрүлө турган түйүндө бир бала бар, анын экиси бар балдар.
5. Алынып жаткан түйүн бир балалуу болгондо, аны жөн гана балага алмаштырып, көрсөткүчтү балага кайтарсаңыз болот.
6. Эгер жок кылына турган түйүндө нөл же 1 бала болсо, анда жок кылуу ыкмасы тамырдан ошол түйүнгө чейин "жолду ээрчийт". Демек, издөө жана кыстаруу үчүн эң начар убакыт дарактын бийиктигине пропорционалдуу.

Эгерде чыгарыла турган түйүн эки балалуу болсо, төмөнкү кадамдар жасалат:

1. Жок кылына турган түйүндү тамырдан ага чейинки жол менен табыңыз.
2. Жалбыракка баруучу жолду улантуу менен оң под дарактан vнин эң кичине маанисин табыңыз.
3. V маанисин рекурсивдүү алып салыңыз, 2-кадамдагыдай жолду басыңыз.
4. Ошентип, эң начар учурда, тамырдан жалбыракка чейинки жол эки жолу аткарылат.

Трассалардын тартиби

Кыдырып өтүү - бул дарактын бардык түйүндөрүн кыдыруучу процесс. C бинардык издөө дарагы сызыктуу эмес маалымат структурасы болгондуктан, уникалдуу өтүү жок. Мисалы, кээде бир нече өтүү алгоритмдеритөмөнкү эки түргө топтоштурулган:

• кетүү тереңдиги;
• биринчи өтүү.

Энди кесип өтүүнүн бир гана түрү бар - деңгээлди айланып өтүү. Бул өтүү түйүндөрдүн ылдый жана сол, жогору жана оң деңгээлинде барат.

Тереңдиктин үч башка түрү бар:

1. Алдын ала буйрутма өтүүдө - адегенде ата-энеге, андан кийин сол жана оң балага барыңыз.
2. Тартиптен өтүү - сол баланы, андан кийин ата-энени жана оң баланы зыярат кылуу.
3. PostOrder'ден өткөн - сол балага, андан кийин оң балага, анан ата-энеге зыярат кылуу.

Бинардык издөө дарагынын төрт өтүшүнө мисал:

1. Алдын ала буйрутма - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. Тартипте - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. Буйрутмадан кийин берүү - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Сүрөт түйүндөрдүн баруу тартибин көрсөтөт. 1 саны белгилүү бир өтүүдө биринчи түйүн, ал эми 7 акыркы түйүн болуп саналат.

Бул жалпы өтүүлөрдү ар бир түйүн үч жолу кирди деп эсептесек, бир алгоритм катары көрсөтсө болот. Эйлер тур - бул экилик дарактын айланасында сейилдөө, анда ар бир чети колдонуучу өтө албаган дубал катары каралат. Бул сейилдөөдө ар бир түйүн же сол жакта, же ылдыйда, же оң жакта болот. Сол жактагы түйүндөрдү кыдырган Эйлер туру предлогтун айланып өтүшүнө себеп болот. Төмөнкү түйүндөр бар болгондо, алар ирети менен өтүшөт. Ал эми оң жактагы түйүндөр барганда - алуукадам-кадам айланып өтүү.

Навигация жана мүчүлүштүктөрдү оңдоо

Бакты чабыттоону жеңилдетүү үчүн, алгач алардын сол же оң бала экенин текшерген функцияларды түзүңүз. Түйүндүн абалын өзгөртүү үчүн, негизги түйүндөгү көрсөткүчкө оңой жетүү болушу керек. Даракты туура ишке ашыруу өтө кыйын, андыктан мүчүлүштүктөрдү оңдоо процесстерин билип, колдонуу керек. Ишке ашыруусу бар бинардык издөө дарагында көбүнчө саякат багытын көрсөтпөгөн көрсөткүчтөр болот.

Мунун баарын түшүнүү үчүн дарактын туура болушун текшерген функция колдонулат жана көптөгөн каталарды табууга жардам берет. Мисалы, ата-эне түйүн бала түйүн экендигин текшерет. assert(is_wellformed(root)) менен көптөгөн каталарды мөөнөтүнөн мурда кармоого болот. Бул функциянын ичинде бир нече берилген токтотуу чекиттерин колдонуп, кайсы көрсөткүч туура эмес экенин так аныктай аласыз.

Function Konsolenausgabe

Бул функция бүт даракты консолго жууп салат жана ошондуктан абдан пайдалуу. Дарак чыгаруу максатынын аткарылуу тартиби:

1. Бул үчүн адегенде түйүн аркылуу кандай маалымат чыгаарын аныкташыңыз керек.
2. Ошондой эле канча орун калтыруу үчүн дарактын канчалык кең жана бийик экенин билишиңиз керек.
3. Төмөнкү функциялар дарак жана ар бир ички дарак үчүн бул маалыматты эсептейт. Консолго сапка сапка гана жаза алганыңыздан, даракты сапка сап басып чыгарууңуз керек болот.
4. Эми бизге чыгуунун башка жолу керексап боюнча эмес, бүт дарак.
5. Дамп функциясынын жардамы менен сиз даракты окуп, ылдамдыкка байланыштуу чыгаруу алгоритмин бир топ жакшыртсаңыз болот.

Бирок бул функцияны чоң дарактарда колдонуу кыйын болот.

Конструкторду жана деструкторду көчүрүү

Дарак майда-чүйдөсүнө чейин маалымат структурасы болбогондуктан, көчүрүү конструкторун, кыйратуучуну жана дайындоо операторун ишке ашыруу жакшы. Деструкторду рекурсивдүү түрдө ишке ашыруу оңой. Өтө чоң дарактар үчүн, ал "үймөлөп толуп кетүүнү" чече алат. Бул учурда, ал итеративдик түрдө түзүлөт. Идея бардык жалбырактардын эң кичинекей маанисин билдирген жалбыракты алып салуу, ошондуктан ал дарактын сол тарабында болот. Биринчи жалбырактарды кесип жаңы жалбырактарды жаратат, ал эми дарак акыры жок болгуча кичирейет.

Көчүрмө конструктору рекурсивдүү түрдө да ишке ашырылышы мүмкүн, бирок өзгөчө учур болсо этият болуңуз. Болбосо, дарак бат эле баш аламан болуп, ката кетирет. Ошондуктан кайталанма версияга артыкчылык берилет. Идея - эски дарактан жана жаңы дарактан өтүү, деструктордогудай эле, эски дарактагы, бирок жаңылары эмес, бардык түйүндөрдү клондоо.

Бул ыкма менен бинардык издөө дарагынын ишке ашырылышы ар дайым ден-соолукта болот жана ал түгүл толук эмес абалда деструктор тарабынан алынып салынышы мүмкүн. Эгерде өзгөчө жагдай пайда болсо, сиз эмне кылышыңыз керек болсо, деструкторго жарым-жартылай даяр даракты жок кылууну буйрук кылуу керек. дайындоо операторуКөчүрүү жана алмаштыруу аркылуу оңой ишке ашырылса болот.

Экилик издөө дарагы түзүлүүдө

Оптималдуу экилик издөө дарактары туура башкарылса, укмуштуудай эффективдүү болот. Экилик издөө дарактары үчүн кээ бир эрежелер:

1. Ата-эне түйүндө эң көп дегенде 2 кошумча түйүн бар.
2. Сол кошумча түйүн ата-энелик түйүндөн дайыма азыраак болот.
3. Жарактуу кошумча түйүн ар дайым аталык түйүнгө барабар же чоңураак.

Бинардык издөө дарагын куруу үчүн колдонула турган массив:

1. Сорттолбогон тартипте жети мааниден турган негизги бүтүн сан массиви.
2. Массивдеги биринчи маани 10, андыктан даракты куруудагы биринчи кадам бул жерде көрсөтүлгөндөй 10 тамыр түйүн түзүү.
3. Тамыр түйүндөрүнүн топтому менен, бардык башка маанилер бул түйүндүн балдары болот. Эрежелерге шилтеме жасап, даракка 7 кошуу үчүн жасала турган биринчи кадам - аны тамыр түйүнүнө салыштыруу.
4. Эгер 7 мааниси 10дон аз болсо, ал сол кошумча түйүн болуп калат.
5. Эгер 7 мааниси 10дон чоң же барабар болсо, ал оңго жылат. 7 10дон аз экени белгилүү болгондуктан, ал сол кошумча түйүн катары белгиленген.
6. Ар бир элемент үчүн рекурсивдүү салыштырууларды жүргүзүңүз.
7. Ошол эле үлгү боюнча, массивдеги 14-маани менен бирдей салыштырууну аткарыңыз.
8. 14 маанисин 10-тамыр түйүнүнө салыштыруу, 14 туура бала экенин билүү.
9. Массивди басып өтүү,20га кел.
10. Кайсысы чоңураак болсо, массивди 10 менен салыштырып баштаңыз. Андыктан оңго жылдырып, аны 14кө салыштырыңыз, ал 14төн ашты жана оң жакта балдары жок.
11. Эми 1 мааниси бар. Башка маанилер сыяктуу эле, 1ден 10го чейин салыштырып, солго жылып, 7ге жана акырында 7-түйүндүн 1 сол баласына салыштырыңыз.
12. Эгер маани 5 болсо, аны 10 менен салыштырыңыз. 5 10дон аз болгондуктан, солго өтүп, аны 7ге салыштырыңыз.
13. 5 7ден аз экенин билип, даракты ылдый карай улантып, 5ти 1 мааниге салыштырыңыз.
14. Эгер 1де бала жок болсо жана 5 1ден чоң болсо, анда 5 1 түйүндүн жарактуу баласы болуп саналат.
15. Акыры даракка 8 маанисин киргизиңиз.
16. 8 10дон аз болгондо, аны солго жылдырыңыз жана аны 7ге салыштырыңыз, 8 7ден чоң, андыктан аны оңго жылдырып, даракты бүтүрүңүз, 8 7дин туура баласы болсун.

Оптималдуу бинардык издөө дарактарынын жөнөкөй көрктүүлүгүн алуу жана баалоо. Программалоодогу көптөгөн темалар сыяктуу эле, бинардык издөө дарактарынын күчү алардын маалыматтарды майда, байланышкан компоненттерге чечүү жөндөмүнөн келип чыгат. Мындан ары, сиз толук маалымат топтому менен уюшкан түрдө иштей аласыз.

Потенциалдуу экилик издөө маселелери

Бинардык издөө дарактары сонун, бирок эстен чыгарбоо керек болгон бир нече эскертүүлөр бар. Алар, адатта, тең салмактуу болгондо гана натыйжалуу болот. Салмактуу дарак - бул даракдарактын кайсы бир түйүнүнүн астыңкы дарактарынын бийиктиктеринин ортосундагы айырма эң көп дегенде бир. Келгиле, эрежелерди тактоого жардам бере турган мисалды карап көрөлү. Массив ирээттөөчү катары башталат деп элестетип көрөлү.

Эгер сиз бул даракта бинардык издөө дарагынын алгоритмин иштеткенге аракет кылсаңыз, ал керектүү маани табылганга чейин массивде итерациялангандай эле аткарат. Бинардык издөөнүн күчү керексиз баалуулуктарды тез чыпкалоо жөндөмүндө. Дарак тең салмактуу болбосо, ал тең салмактуу дарак сыяктуу пайда бербейт.

Бинардык издөө дарагын түзүүдө колдонуучу иштеп жаткан маалыматтарды текшерүү абдан маанилүү. Бүтүн сандарды теңдөө үчүн бинардык издөө дарагын ишке ашыруудан мурун массивди рандомизациялоо сыяктуу процедураларды бириктире аласыз.

Экилик издөө эсептөө мисалдары

Төмөнкү бинардык издөө дарагына 25 киргизилсе, кандай дарак пайда болорун аныкташыбыз керек:

10

/

/

5 15

/ /

/ /

2 12 20

Х али камтылбаган T дарагына x киргизгенде, х ачкычы ар дайым жаңы жалбыракка жайгаштырылат. Буга байланыштуу жаңы дарак төмөнкүдөй болот:

10

/

/

5 15

/ /

/ /

2 12 20

25

Эгер сиз төмөнкү бинардык издөө дарагына 7 киргизсеңиз, кандай даракты алмаксыз?

10

/

/

5 15

/ /

/ /

2 12 20

Жооп:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

Бинардык издөө дарагы каалаган объектти сактоо үчүн колдонулушу мүмкүн. Байланышкан тизменин ордуна бинардык издөө дарагын колдонуунун артыкчылыгы, эгерде дарак акылга сыярлык тең салмактуу болсо жана "сызыктуу" даракка караганда "толук" даракка көбүрөөк окшош болсо, киргизүү, издөө жана бардык жок кылуу операцияларын иштетүү үчүн ишке ашырууга болот. O(log N) убакыт.