Хоёртын хайлтын модыг хэрэгжүүлэх

2024 Зохиолч: Angel Austin | [email protected]. Хамгийн сүүлд өөрчлөгдсөн: 2023-12-17 05:36

Хоёртын хайлтын мод - зангилаа, баруун болон зүүн бусад зангилааны хоёр холбоосыг агуулсан бүтэцлэгдсэн мэдээллийн сан. Зангилаа нь өгөгдөлтэй ангийн объект бөгөөд 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 (лог n) гарна.

Модны ашиг тус:

1. Өгөгдлийн бүтцийн хамаарлыг тусгана.
2. Шатлалыг төлөөлөхөд ашигладаг.
3. Үр ашигтай суурилуулалт болон хайлтыг баталгаажуулна уу.
4. Мод нь маш уян хатан өгөгдөл бөгөөд танд хамгийн бага хүчин чармайлтаар дэд модыг зөөх боломжийг олгодог.

Хайлтын арга

Ерөнхийдөө утга нь BST-д байгаа эсэхийг тодорхойлохын тулд түүний үндэс дээр хоёртын хайлтын модыг эхлүүлж, шаардлагад нийцэж байгаа эсэхийг тодорхойлно уу:

• үндэс нь байх;
• язгуурын зүүн дэд модонд байх;
• язгуурын баруун дэд модонд.

Хэрэв суурь бүртгэл хангагдаагүй бол харгалзах дэд модоор рекурсив хайлт хийнэ. Үнэндээ хоёр үндсэн сонголт байна:

1. Мод хоосон байна - худал гэж буцаана.
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-г буцаана. Энэ нь өөрт нь дамжуулсан зангилаа null байх тохиолдолд үүнийг зохицуулахын тулд үүнийг хийдэг.

Ерөнхийдөө туслах арга нь хэрэв анхны хоёртын хайлтын мод хоосон байвал үр дүн нь нэг зангилаатай мод болохыг заадаг. Үгүй бол үр дүн нь аргумент болгон дамжуулсан ижил зангилаа руу заагч болно.

Хоёртын алгоритмаар устгах

Таны таамаглаж байгаачлан элементийг устгах нь устгах утгыг агуулсан зангилааг олох явдал юм. Энэ кодонд хэд хэдэн зүйл байна:

1. BST нь туслах, хэт ачаалалтай устгах аргыг ашигладаг. Хэрэв таны хайж буй элемент модонд байхгүй бол туслах аргыг эцэст нь n==null гэж дуудна. Энэ нь алдаа гэж тооцогддоггүй, энэ тохиолдолд мод зүгээр л өөрчлөгддөггүй. Устгах туслах арга нь утгыг буцаана - шинэчлэгдсэн модны заагч.
2. Навчийг хасах үед хоёртын хайлтын модноос хассанаар түүний эцэг эхийн харгалзах хүүхэд заагчийг null, хэрэв устгаж байгаа бол үндсийг null болгоно.зангилаа нь үндэс бөгөөд хүүхэдгүй.
3. Устгах дуудлага нь дараахь зүйлсийн аль нэг байх ёстойг анхаарна уу: root=устгах (root, key), n.setLeft (устгах (n.getLeft (), түлхүүр)), n.setRight (устгах(n. getRight(), түлхүүр)). Иймээс гурван тохиолдолд устгах арга нь зүгээр л null гэж буцаана.
4. Устгах утгыг агуулсан зангилааг хайж олоход гурван сонголт байна: устгах зангилаа нь навч (хүүхэд байхгүй), устгах зангилаа нэг хүүхэдтэй, хоёр хүүхэдтэй байна. хүүхдүүд.
5. Устгаж буй зангилаа нэг хүүхэдтэй бол та зүгээр л хүүхэд рүү заагчийг буцааж өгснөөр үүнийг хүүхдээр сольж болно.
6. Хэрэв устгах гэж буй зангилаа тэг эсвэл 1 хүүхэдтэй бол устгах арга нь уг зангилаа хүртэлх "замыг дагах" болно. Тиймээс хайх болон оруулах аль алинд нь хамгийн муу цаг нь модны өндөртэй пропорциональ байна.

Хэрэв арилгах зангилаа хоёр хүүхэдтэй бол дараах алхмуудыг хийнэ:

1. Устгах цэгийг үндсэн цэгээс нь дагах замаар олно уу.
2. Баруун талын дэд модны v-ийн хамгийн бага утгыг олж, навч руу явах зам дагуу үргэлжлүүлээрэй.
3. v-ийн утгыг рекурсиваар хасч, 2-р алхамтай ижил замыг дагана уу.
4. Тиймээс хамгийн муу тохиолдолд үндэснээс навч хүртэлх замыг хоёр удаа хийдэг.

Голын дараалал

Traversal нь модны бүх зангилаанд зочилдог процесс юм. 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. Level Order - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Зоглогчид зочилсон дарааллыг зурагт харуулав. 1-ийн тоо нь тодорхой эргэлтийн эхний зангилаа, 7 нь сүүлчийн зангилаа юм.

Зангилаа бүрийг гурван удаа зочилсон гэж үзвэл эдгээр ерөнхий дамжуулалтыг нэг алгоритм хэлбэрээр илэрхийлж болно. Эйлерийн аялал нь хоёртын модыг тойрон алхах бөгөөд ирмэг бүр нь хэрэглэгч хөндлөн гарах боломжгүй хана мэт үздэг. Энэ алхалтын үед зангилаа бүрийг зүүн, доор эсвэл баруун талд зочлох болно. Зүүн талын зангилаануудаар зочилдог Эйлерийн аялал нь угтвар үгийг тойрч гарахад хүргэдэг. Доорх зангилаанууд дээр очиход тэдгээрийг дарааллаар нь дамждаг. Мөн баруун талд байгаа зангилаанууд зочлоход - аваарайалхам алхмаар алгасах.

Навигаци болон дибаг хийх

Мод руу шилжихэд хялбар болгохын тулд эхлээд тэдгээр нь зүүн эсвэл баруун хүүхэд мөн эсэхийг шалгах функцуудыг үүсгэнэ үү. Зангилааны байрлалыг өөрчлөхийн тулд үндсэн зангилааны заагч руу хялбархан хандах боломжтой байх ёстой. Модыг зөв хэрэгжүүлэх нь маш хэцүү тул та дибаг хийх процессуудыг мэдэж, хэрэгжүүлэх хэрэгтэй. Хэрэгжилттэй хоёртын хайлтын мод нь ихэвчлэн аяллын чиглэлийг заадаггүй заагчтай байдаг.

Энэ бүгдийг ойлгохын тулд мод зөв эсэхийг шалгах функцийг ашиглаж, олон алдааг олоход тусалдаг. Жишээлбэл, эцэг эх нь хүүхэд зангилаа эсэхийг шалгадаг. assert(is_wellformed(root))-ийн тусламжтайгаар олон алдааг эрт илрүүлж болно. Энэ функц дотор өгөгдсөн хэд хэдэн таслах цэгийг ашигласнаар аль заагч буруу байгааг тодорхойлох боломжтой.

Функц 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) цаг.