Pagpapatupad ng isang binary search tree

2024 May -akda: Angel Austin | [email protected]. Huling binago: 2023-12-17 05:44

Binary search tree - isang structured database na naglalaman ng mga node, dalawang link sa iba pang node, kanan at kaliwa. Ang mga node ay isang object ng klase na mayroong data, at ang NULL ay ang sign na nagmamarka sa dulo ng tree.

Madalas itong tinutukoy bilang BST, na may espesyal na katangian: ang mga node na mas malaki kaysa sa ugat ay matatagpuan sa kanan nito, at mas maliit sa kaliwa.

Pangkalahatang teorya at terminolohiya

Sa isang binary search tree, ang bawat node, hindi kasama ang root, ay konektado sa pamamagitan ng isang nakadirekta na gilid mula sa isang node patungo sa isa pa, na tinatawag na parent. Ang bawat isa sa kanila ay maaaring konektado sa isang arbitrary na bilang ng mga node, na tinatawag na mga bata. Ang mga node na walang "mga bata" ay tinatawag na mga dahon (mga panlabas na node). Ang mga elementong hindi dahon ay tinatawag na panloob. Ang mga node na may parehong magulang ay magkakapatid. Ang pinakamataas na node ay tinatawag na ugat. Sa BST, magtalaga ng elemento sa bawat node at tiyaking mayroon silang espesyal na property na nakatakda para sa kanila.

Terminolohiya ng puno:

1. Ang lalim ng isang node ay ang bilang ng mga gilid na tinukoy mula sa ugat hanggang dito.
2. Ang taas ng isang node ay ang bilang ng mga gilid na tinukoy mula dito hanggang sa pinakamalalim na dahon.
3. Ang taas ng puno ay tinutukoy ng taas ng ugat.
4. Ang binary search tree ay isang espesyal na disenyo, nagbibigay ito ng pinakamahusay na ratio ng taas at bilang ng mga node.
5. Taas h na may N node na hindi hihigit sa O (log N).

Madali mong mapatunayan ito sa pamamagitan ng pagbilang ng mga node sa bawat antas, simula sa ugat, sa pag-aakalang naglalaman ito ng pinakamalaking bilang ng mga ito: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Ang paglutas nito para sa h ay nagbibigay ng h=O (log n).

Mga pakinabang ng kahoy:

1. Sinalamin ang mga istrukturang ugnayan ng data.
2. Ginamit upang kumatawan sa mga hierarchy.
3. Tiyaking mahusay ang pag-install at paghahanap.
4. Ang mga puno ay napaka-flexible na data, na nagbibigay-daan sa iyong ilipat ang mga subtree nang may kaunting pagsisikap.

Paraan ng paghahanap

Sa pangkalahatan, para matukoy kung ang isang value ay nasa BST, magsimula ng binary search tree sa ugat nito at tukuyin kung nakakatugon ito sa mga kinakailangan:

• maging sa ugat;
• nasa kaliwang subtree ng ugat;
• sa kanang subtree ng ugat.

Kung walang base na rehistro ang nasiyahan, ang isang recursive na paghahanap ay isinasagawa sa kaukulang subtree. Mayroong talagang dalawang pangunahing opsyon:

1. Walang laman ang puno - return false.
2. Nasa root node ang value - ibalik ang true.

Dapat tandaan na ang binary search tree na may binuong schema ay palaging nagsisimulang maghanap sa daanan mula sa ugat hanggang sa dahon. Sa pinakamasamang kaso, napupunta ito hanggang sa dahon. Samakatuwid, ang pinakamasamang oras ay proporsyonal sa haba ng pinakamahabang landas mula sa ugat hanggang sa dahon, na siyang taas ng puno. Sa pangkalahatan, ito ay kapag kailangan mong malaman kung gaano katagal bago tumingin bilang isang function ng bilang ng mga value na nakaimbak sa tree.

Sa madaling salita, may kaugnayan sa pagitan ng bilang ng mga node sa isang BST at taas ng isang puno, depende sa "hugis" nito. Sa pinakamasamang kaso, ang mga node ay may isang anak lamang, at ang balanseng binary search tree ay mahalagang isang naka-link na listahan. Halimbawa:

50

/

10

15

30

/

20

Ang punong ito ay may 5 node at taas=5. Ang paghahanap ng mga value sa hanay na 16-19 at 21-29 ay mangangailangan ng sumusunod na landas mula sa ugat hanggang sa dahon (ang node na naglalaman ng halagang 20), i.e., aabutin ang oras na proporsyonal sa bilang ng mga node. Sa pinakamaganda, lahat sila ay may 2 anak, at ang mga dahon ay matatagpuan sa parehong lalim.

Ang binary search tree na ito ay may 7 node at taas=3. Sa pangkalahatan, ang isang punong katulad nito (full tree) ay magkakaroon ng taas na humigit-kumulang log 2 (N), kung saan ang N ay ang bilang ng mga node sa tree. Ang halaga ng log 2 (N) ay ang bilang ng beses (2) na maaaring hatiin ang N bago maabot ang zero.

Pagbubuod: ang pinakamasayang oras na kailangan para maghanap sa BST ay O (taas ng puno). Ang pinakamasamang kaso na "linear" na puno ay O(N), kung saan ang N ay ang bilang ng mga node sa puno. Sa pinakamaganda, ang isang "kumpleto" na puno ay O(log N).

BST binary insert

Nag-iisip kung saan dapatang bagong node ay matatagpuan sa BST, kailangan mong maunawaan ang lohika, dapat itong ilagay kung saan nahanap ito ng gumagamit. Bilang karagdagan, kailangan mong tandaan ang mga panuntunan:

1. Hindi pinapayagan ang mga duplicate, ang pagtatangkang maglagay ng duplicate na value ay magdudulot ng exception.
2. Ang paraan ng pampublikong pagpasok ay gumagamit ng isang helper recursive na "helper" na paraan upang aktwal na maipasok.
3. Ang isang node na naglalaman ng bagong value ay palaging ipinapasok bilang isang dahon sa BST.
4. Ang paraan ng pampublikong pagpasok ay nagbabalik ng walang bisa, ngunit ang paraan ng helper ay nagbabalik ng isang BSTnode. Ginagawa nito ito upang pangasiwaan ang kaso kung saan ang node na ipinasa dito ay null.

Sa pangkalahatan, ang paraan ng helper ay nagpapahiwatig na kung ang orihinal na binary search tree ay walang laman, ang resulta ay isang puno na may isang node. Kung hindi, ang resulta ay magiging pointer sa parehong node na ipinasa bilang argumento.

Pagtanggal sa binary algorithm

Tulad ng maaari mong asahan, ang pagtanggal ng isang elemento ay kinabibilangan ng paghahanap ng node na naglalaman ng value na aalisin. Mayroong ilang mga bagay sa code na ito:

Gumagamit ang

BST ng helper, overloaded na paraan ng pagtanggal. Kung ang elementong hinahanap mo ay wala sa puno, ang paraan ng helper ay tatawagin sa kalaunan ng n==null. Hindi ito itinuturing na isang error, ang puno ay hindi nagbabago sa kasong ito. Ang delete helper method ay nagbabalik ng value - isang pointer sa na-update na tree.

Kapag inalis ang isang dahon, itatakda ng pag-alis mula sa binary search tree ang katumbas na child pointer ng magulang nito sa null, o ang root sa null kung ang inaalis ayang node ay isang ugat at walang mga anak.

Tandaan na ang delete call ay dapat isa sa mga sumusunod: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), key)). Kaya, sa lahat ng tatlong kaso, tama na ang paraan ng pagtanggal ay nagbabalik lamang ng null.

Kapag nagtagumpay ang paghahanap para sa node na naglalaman ng value na tatanggalin, mayroong tatlong opsyon: ang node na tatanggalin ay isang dahon (walang mga anak), ang node na tatanggalin ay may isang anak, mayroon itong dalawa mga bata.

Kapag ang node na inaalis ay may isang anak, maaari mo lamang itong palitan ng isang bata, na nagbabalik ng isang pointer sa bata.

Kung ang node na tatanggalin ay may zero o 1 anak, ang paraan ng pagtanggal ay "susundan ang landas" mula sa ugat patungo sa node na iyon. Kaya ang pinakamasamang oras ay proporsyonal sa taas ng puno, para sa parehong paghahanap at pagsingit.

Kung ang node na aalisin ay may dalawang anak, ang mga sumusunod na hakbang ay gagawin:

1. Hanapin ang node na tatanggalin, na sinusundan ang landas mula sa ugat patungo dito.
2. Hanapin ang pinakamaliit na value ng v sa kanang subtree, na nagpapatuloy sa daan patungo sa dahon.
3. Recursively tanggalin ang value ng v, sundan ang parehong path tulad ng sa hakbang 2.
4. Kaya, sa pinakamasamang kaso, ang landas mula sa ugat hanggang sa dahon ay isinasagawa nang dalawang beses.

Order of traverses

Ang

Traversal ay isang proseso na bumibisita sa lahat ng node sa isang puno. Dahil ang C binary search tree ay isang non-linear na istraktura ng data, walang natatanging traversal. Halimbawa, kung minsan ilang mga algorithm ng traversalnakapangkat sa sumusunod na dalawang uri:

• crossing depth;
• first pass.

Mayroon lamang isang uri ng width crossing - pag-bypass sa antas. Ang traversal na ito ay bumibisita sa mga node level pababa at kaliwa, itaas at kanan.

May tatlong magkakaibang uri ng depth crossing:

1. Pagpapasa ng PreOrder - bisitahin muna ang magulang at pagkatapos ay ang kaliwa at kanang anak.
2. Passing InOrder - binibisita ang kaliwang anak, pagkatapos ay ang magulang at ang kanang anak.
3. Nakalipas ang PostOrder - binibisita ang kaliwang anak, pagkatapos ang kanang anak, pagkatapos ay ang magulang.

Halimbawa para sa apat na traversal ng isang binary search tree:

1. PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Ipinapakita ng figure ang pagkakasunud-sunod kung saan binibisita ang mga node. Ang numero 1 ay ang unang node sa isang partikular na traversal, at 7 ang huling node.

Ang mga pangkalahatang traversal na ito ay maaaring katawanin bilang isang algorithm, kung ipagpalagay na ang bawat node ay binibisita nang tatlong beses. Ang Euler tour ay isang paglalakad sa paligid ng isang binary tree kung saan ang bawat gilid ay itinuturing bilang isang pader na hindi makatawid ng user. Sa paglalakad na ito, bibisitahin ang bawat node sa kaliwa, o sa ibaba, o sa kanan. Ang Euler tour, na bumibisita sa mga node sa kaliwa, ay nagiging sanhi ng pag-bypass sa preposisyon. Kapag ang mga node sa ibaba ay binisita, sila ay dadaan sa pagkakasunud-sunod. At kapag ang mga node sa kanan ay binisita - kumuhastep-by-step bypass.

Navigation and Debugging

Upang padaliin ang pag-navigate sa puno, gumawa ng mga function na unang tumitingin kung sila ang kaliwa o kanang bata. Upang baguhin ang posisyon ng isang node, dapat mayroong madaling pag-access sa pointer sa parent node. Ang wastong pagpapatupad ng isang puno ay napakahirap, kaya kailangan mong malaman at ilapat ang mga proseso ng pag-debug. Ang binary search tree na may pagpapatupad ay kadalasang may mga pointer na hindi aktwal na nagsasaad ng direksyon ng paglalakbay.

Upang malaman ang lahat ng ito, ginagamit ang isang function na nagsusuri kung ang puno ay maaaring tama, at tumutulong upang makahanap ng maraming error. Halimbawa, sinusuri nito kung ang parent node ay isang child node. Sa assert(is_wellformed(root)) maraming mga error ang maaaring mahuli nang maaga. Gamit ang ilang ibinigay na breakpoint sa loob ng function na ito, matutukoy mo rin kung aling pointer ang mali.

Function Konsolenausgabe

I-flush ng function na ito ang buong puno sa console at samakatuwid ay lubhang kapaki-pakinabang. Ang pagkakasunud-sunod kung saan isinasagawa ang layunin ng tree output ay:

1. Para magawa ito, kailangan mo munang tukuyin kung anong impormasyon ang ilalabas sa pamamagitan ng node.
2. At kailangan mo ring malaman kung gaano kalawak at kataas ang puno upang matugunan kung gaano karaming espasyo ang maiiwan.
3. Kinakalkula ng mga sumusunod na function ang impormasyong ito para sa puno at bawat subtree. Dahil maaari ka lang sumulat sa console line by line, kakailanganin mo ring i-print ang tree line by line.
4. Ngayon kailangan namin ng isa pang paraan para mag-withdrawang buong puno, hindi lang linya sa linya.
5. Sa tulong ng dump function, maaari mong basahin ang puno at makabuluhang mapabuti ang output algorithm, hangga't bilis.

Gayunpaman, ang function na ito ay magiging mahirap gamitin sa malalaking puno.

Kopyahin ang constructor at destructor

Dahil ang isang puno ay hindi isang trivial na istraktura ng data, mas mainam na magpatupad ng isang copy constructor, isang destructor, at isang assignment operator. Ang destructor ay madaling ipatupad nang recursively. Para sa napakalalaking puno, kakayanin nito ang "heap overflow". Sa kasong ito, ito ay nabuo nang paulit-ulit. Ang ideya ay alisin ang dahon na kumakatawan sa pinakamaliit na halaga ng lahat ng mga dahon, kaya ito ay nasa kaliwang bahagi ng puno. Ang pagpuputol sa mga unang dahon ay lumilikha ng mga bago, at ang puno ay lumiliit hanggang sa tuluyang mawala ito.

Maaari ding ipatupad ang copy constructor nang recursively, ngunit mag-ingat kung may ibinabato na exception. Kung hindi, ang puno ay mabilis na nagiging nakalilito at madaling kapitan ng pagkakamali. Iyon ang dahilan kung bakit mas gusto ang umuulit na bersyon. Ang ideya ay dumaan sa lumang puno at sa bagong puno, tulad ng gagawin mo sa destructor, na i-clone ang lahat ng mga node na nasa lumang puno ngunit hindi ang mga bago.

Sa pamamaraang ito, ang pagpapatupad ng binary search tree ay palaging nasa malusog na estado at maaaring alisin ng destructor kahit na sa isang hindi kumpletong estado. Kung may nangyaring exception, ang kailangan mo lang gawin ay turuan ang destructor na tanggalin ang semi-finished tree. operator ng assignmentmadaling ipatupad gamit ang Copy & Swap.

Paggawa ng binary search tree

Ang pinakamainam na binary search tree ay hindi kapani-paniwalang mahusay kung pinamamahalaan nang maayos. Ilang panuntunan para sa mga binary search tree:

1. Ang parent node ay may hindi hihigit sa 2 child node.
2. Ang kaliwang child node ay palaging mas mababa kaysa sa parent node.
3. Ang isang wastong child node ay palaging mas malaki kaysa o katumbas ng parent node.

Ang array na gagamitin sa pagbuo ng binary search tree:

1. Isang base integer array ng pitong value sa unsorted order.
2. Ang unang value sa array ay 10, kaya ang unang hakbang sa pagbuo ng tree ay gumawa ng 10 root node, gaya ng ipinapakita dito.
3. Sa isang hanay ng mga root node, lahat ng iba pang value ay magiging mga anak ng node na ito. Sa pagtukoy sa mga panuntunan, ang unang hakbang na dapat gawin upang magdagdag ng 7 sa puno ay ihambing ito sa root node.
4. Kung ang value 7 ay mas mababa sa 10, ito ang magiging kaliwang child node.
5. Kung ang value na 7 ay mas malaki sa o katumbas ng 10, lilipat ito sa kanan. Dahil ang 7 ay kilala na mas mababa sa 10, ito ay itinalaga bilang ang kaliwang child node.
6. Recursively magsagawa ng mga paghahambing para sa bawat elemento.
7. Pagkasunod sa parehong pattern, gawin ang parehong paghahambing laban sa ika-14 na value sa array.
8. Paghahambing ng value 14 sa root node 10, alam na 14 ang tamang bata.
9. Paglalakad sa hanay,dumating sa 20.
10. Magsimula sa pamamagitan ng paghahambing ng array sa 10, alinman ang mas malaki. Kaya lumipat sa kanan at ihambing ito sa 14, lampas na siya sa 14 at walang mga anak sa kanan.
11. Ngayon ay may value na 1. Sumusunod sa parehong pattern tulad ng iba pang mga value, ihambing ang 1 sa 10, paglipat sa kaliwa at paghahambing sa 7 at panghuli sa 1 kaliwang anak ng 7th node.
12. Kung ang value ay 5, ihambing ito sa 10. Dahil ang 5 ay mas mababa sa 10, pumasa sa kaliwa at ihambing ito sa 7.
13. Alam na ang 5 ay mas mababa sa 7, magpatuloy pababa sa puno at ihambing ang 5 sa 1 halaga.
14. Kung ang 1 ay walang anak at ang 5 ay higit sa 1, ang 5 ay isang wastong anak ng 1 node.
15. Sa wakas, ilagay ang value 8 sa puno.
16. Kapag ang 8 ay mas mababa sa 10, ilipat ito sa kaliwa at ihambing ito sa 7, ang 8 ay mas malaki sa 7, kaya ilipat ito sa kanan at kumpletuhin ang puno, na ginagawang 8 ang tamang anak ng 7.

Pagkuha at pagsusuri sa simpleng kagandahan ng pinakamainam na binary search tree. Tulad ng maraming paksa sa programming, ang kapangyarihan ng mga binary search tree ay nagmumula sa kanilang kakayahang magresolba ng data sa maliliit, nauugnay na mga bahagi. Mula ngayon, maaari mong gamitin ang buong dataset sa isang organisadong paraan.

Potensyal na Mga Isyu sa Binary Search

Ang mga binary search tree ay mahusay, ngunit may ilang mga caveat na dapat tandaan. Ang mga ito ay kadalasang epektibo lamang kung sila ay balanse. Ang balanseng puno ay isang puno kung saanang pagkakaiba sa pagitan ng taas ng mga subtree ng anumang node sa puno ay hindi hihigit sa isa. Tingnan natin ang isang halimbawa na maaaring makatulong na linawin ang mga patakaran. Isipin natin na ang array ay nagsisimula bilang sortable.

Kung susubukan mong magpatakbo ng binary search tree algorithm sa punong ito, gagana ito nang eksakto na parang umuulit lang ito sa array hanggang sa matagpuan ang gustong value. Ang kapangyarihan ng binary na paghahanap ay nakasalalay sa kakayahang mabilis na i-filter ang mga hindi gustong halaga. Kapag ang isang puno ay hindi balanse, hindi ito magbibigay ng parehong mga benepisyo gaya ng isang balanseng puno.

Napakahalagang suriin ang data na ginagamit ng user kapag gumagawa ng binary search tree. Maaari mong isama ang mga gawain tulad ng array randomization bago ipatupad ang isang binary search tree para sa mga integer upang balansehin ito.

Mga halimbawa ng pagkalkula ng binary na paghahanap

Kailangan nating matukoy kung anong uri ng puno ang magreresulta kung 25 ang ilalagay sa sumusunod na binary search tree:

10

/

/

5 15

/ /

/ /

2 12 20

Kapag ipinapasok ang x sa isang punong T na wala pang x, palaging inilalagay ang susi x sa bagong dahon. Kaugnay nito, ang bagong puno ay magmumukhang:

10

/

/

5 15

/ /

/ /

2 12 20

25

Anong uri ng puno ang makukuha mo kung maglalagay ka ng 7 sa sumusunod na binary search tree?

10

/

/

5 15

/ /

/ /

2 12 20

Sagot:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

Maaaring gamitin ang binary search tree upang mag-imbak ng anumang bagay. Ang bentahe ng paggamit ng isang binary search tree sa halip na isang naka-link na listahan ay kung ang puno ay makatwirang balanse at mas katulad ng isang "buong" puno kaysa sa isang "linear", ang pagpapasok, paghahanap, at lahat ng mga operasyon sa pagtanggal ay maaaring ipatupad upang tumakbo sa. O(log N) oras.