Бинарлы іздеу ағашын іске асыру

2024 Автор: Angel Austin | [email protected]. Соңғы өзгертілген: 2023-12-17 05:33

Екілік іздеу ағашы - түйіндерді, оң және сол жақ басқа түйіндерге екі сілтемені қамтитын құрылымдық дерекқор. Түйіндер деректері бар сыныптың нысаны, ал 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. Ағаш бос - жалған мәнін қайтарыңыз.
2. Мән түбірлік түйінде - ақиқат мәнін қайтарады.

Схемасы дамыған екілік іздеу ағашы әрқашан тамырдан жапыраққа дейінгі жол бойымен іздеуді бастайтынын атап өткен жөн. Ең нашар жағдайда ол жапыраққа дейін барады. Сондықтан ең нашар уақыт тамырдан жапыраққа дейінгі ең ұзын жолдың ұзындығына пропорционалды, бұл ағаштың биіктігі. Жалпы, бұл ағашта сақталған мәндер санының функциясы ретінде іздеуге қанша уақыт кететінін білу қажет.

Басқаша айтқанда, BST-дегі түйіндер саны мен оның «пішініне» байланысты ағаштың биіктігі арасында байланыс бар. Ең нашар жағдайда түйіндерде тек бір ғана еншілес болады және теңдестірілген екілік іздеу ағашы негізінен байланыстырылған тізім болып табылады. Мысалы:

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==null арқылы шақырылады. Бұл қате деп саналмайды, бұл жағдайда ағаш жай өзгермейді. Көмекші жою әдісі мәнді қайтарады - жаңартылған ағашқа көрсеткіш.
2. Жапырақ жойылған кезде, екілік іздеу ағашынан жою оның ата-анасының сәйкес еншілес көрсеткішін нөлге, ал егер жойылатын болса, түбірді нөлге орнатады.түйін түбір және еншілес емес.
3. Жою шақыруы келесі әрекеттердің бірі болуы керек екенін ескеріңіз: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), перне)). Осылайша, үш жағдайда да жою әдісі нөлді қайтаратыны дұрыс.
4. Жойылатын мәнді қамтитын түйінді іздеу сәтті болған кезде, үш опция бар: жойылатын түйін - парақ (балалар жоқ), жойылатын түйінде бір еншілес, оның екі еншісі бар балалар.
5. Жойылып жатқан түйінде бір бала болса, оны жай ғана баламен ауыстыруға болады, көрсеткішті балаға қайтарады.
6. Жойылатын түйінде нөл немесе 1 еншілес болса, жою әдісі түбірден сол түйінге дейін "жолмен жүреді". Сондықтан іздеу және кірістіру үшін ең нашар уақыт ағаштың биіктігіне пропорционал.

Жойылатын түйіннің екі баласы болса, келесі қадамдар орындалады:

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

Трассалар реті

Треверсал - ағаштың барлық түйіндерін аралайтын процесс. C екілік іздеу ағашы сызықты емес деректер құрылымы болғандықтан, бірегей өту жоқ. Мысалы, кейде бірнеше өту алгоритмдерікелесі екі түрге топтастырылған:

• қиылысу тереңдігі;
• алғашқы өту.

Ені қиылысудың бір ғана түрі бар - деңгейді айналып өту. Бұл өтпелі жол төмен және солға, жоғарғы және оңға деңгейлі түйіндерді аралайды.

Тереңдік қиылыстарының үш түрлі түрі бар:

1. Алдын ала тапсырыстан өту - алдымен ата-анаға, содан кейін сол және оң балаға барыңыз.
2. Тәртіптен өту - сол балаға, содан кейін ата-анаға және оң балаға бару.
3. Тапсырыс беруден өткен – сол балаға, содан кейін оң жақ балаға, содан кейін ата-анаға бару.

Бинарлы іздеу ағашының төрт өту мысалы:

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. LevelRorder - 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-тің дұрыс еншілес екенін біле отырып, 14 мәнін 10-түбірлік түйінмен салыстыру.
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

Құрамында әлі x жоқ T ағашына x кірістіру кезінде 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) уақыты.