Pagkakaiba sa pagitan ng B-puno at Binary tree
Nilalaman
- Tsart ng paghahambing
- Kahulugan ng B-puno
- Mga Katangian ng B-puno ng pagkakasunud-sunod M
- Kahulugan ng Binary puno
- Mga Teknolohiya ng Traversal
- Konklusyon
Ang B-puno at Binary tree ay ang mga uri ng hindi linya na istraktura ng data. Bagaman ang mga termino ay tila magkapareho ngunit naiiba sa lahat ng aspeto. Ginagamit ang isang punungkahoy na puno kapag ang mga tala o data ay naka-imbak sa RAM sa halip na disk bilang ang bilis ng pag-access ng RAM ay mas mataas kaysa sa disk. Sa kabilang banda, ang B-puno ay ginagamit kapag ang data ay naka-imbak sa disk ay binabawasan ang oras ng pag-access sa pamamagitan ng pagbawas ng taas ng puno at pagdaragdag ng mga sanga sa node.
Ang isa pang pagkakaiba sa pagitan ng B-puno at ang punungkahoy na binary ay ang B-puno ay dapat magkaroon ng lahat ng mga node ng bata nito sa parehong antas samantalang ang binary tree ay walang ganoong pagpilit. Ang isang punungkahoy na binary ay maaaring magkaroon ng maximum na 2 subtrees o node samantalang sa B-puno ay maaaring magkaroon ng M walang mga subtrees o node kung saan ang M ay ang pagkakasunud-sunod ng B-puno.
- Tsart ng paghahambing
- Kahulugan
- Pangunahing Pagkakaiba
- Konklusyon
Tsart ng paghahambing
| Batayan para sa paghahambing | B-puno | Binary puno |
|---|---|---|
| Mahahalagang pagpilit | Ang isang node ay maaaring magkaroon ng max M bilang ng mga node ng bata (kung saan ang M ay ang pagkakasunud-sunod ng puno). | Ang isang node ay maaaring magkaroon ng pinakamataas na 2 bilang ng mga subtrees. |
| Ginamit | Ginagamit ito kapag ang data ay naka-imbak sa disk. | Ginagamit ito kapag ang mga tala at data ay naka-imbak sa RAM. |
| Taas ng puno | mag-logM N (kung saan ang utos ng puno ng M-way) | mag-log2 N |
| Application | Ang istraktura ng data ng pag-index ng code sa maraming DBMS. | Ang pag-optimize ng code, Huffman coding, atbp. |
Kahulugan ng B-puno
Ang isang B-puno ay ang balanseng M-way tree at kilala rin bilang balanseng uri ng puno. Pareho ito sa puno ng paghahanap sa binary kung saan ang mga node ay naayos sa batayan ng inorder traversal. Ang pagiging kumplikado ng puwang ng B-puno ay O (n). Ang pagiging kumplikado at pagtanggal ng pagiging kumplikado ng oras ay O (log n).
Mayroong ilang mga kundisyon na dapat totoo para sa isang B-puno:
- Ang taas ng puno ay dapat magsinungaling hangga't maaari hangga't maaari.
- Sa itaas ng mga dahon ng puno, hindi dapat magkaroon ng anumang mga walang laman na subtrees.
- Ang mga dahon ng puno ay dapat na dumating sa parehong antas.
- Ang lahat ng mga node ay dapat magkaroon ng hindi bababa sa bilang ng mga bata maliban sa mga iwanang node.
Mga Katangian ng B-puno ng pagkakasunud-sunod M
- Ang bawat node ay maaaring magkaroon ng maximum na M bilang ng mga bata at pinakamababang M / 2 na bilang ng mga bata o anumang bilang mula 2 hanggang sa maximum.
- Ang bawat node ay may isang key na mas mababa kaysa sa mga bata na may pinakamataas na M-1 key.
- Ang pag-aayos ng mga susi ay nasa ilang tiyak na pagkakasunud-sunod sa loob ng mga node. Ang lahat ng mga susi sa subtree na naroroon sa kaliwa ng susi ay nauna sa susi, at ang naroroon sa kanan ng susi ay tinatawag na mga kahalili.
- Sa oras ng pagpasok ng isang buong node, ang puno ay nahati sa dalawang bahagi, at ang susi na may halaga ng panggitna ay ipinasok sa node ng magulang.
- Ang operasyon ng pagsasama ay nangyayari kapag tinanggal ang mga node.
Kahulugan ng Binary puno
Ang Binary tree ay isang istraktura ng puno na maaaring magkaroon ng halos dalawang mga pointer para sa mga node ng bata. Nangangahulugan ito na ang pinakamataas na degree ng isang node ay maaaring magkaroon ng 2 at maaaring maging zero o isang degree na node din.
Mayroong ilang mga pagkakaiba-iba ng isang puno ng binary tulad ng mahigpit na binary puno, kumpletong puno ng binary, pinahabang binary tree, atbp.
- Ang mahigpit na binary tree ay isang puno kung saan ang bawat non-terminal node ay dapat na umalis sa subtree at kanang subtree.
- Ang isang puno ay tinawag na Kumpletong puno ng Binary kapag nasiyahan ang kondisyon ng pagkakaroon ng 2 ako node sa bawat antas kung saan ako ang antas.
- Threaded binary ay isang punungkahong binary na binubuo ng alinman sa 0 hindi ng node o 2 bilang ng mga node.
Mga Teknolohiya ng Traversal
Ang traversal ng puno ay isa sa mga madalas na operasyon na ginanap sa istraktura ng data ng puno kung saan ang bawat node ay binisita nang eksakto sa isang sistematikong paraan.
- Inorder- Sa punong ito ng traversal ang kaliwang subtree ay binibisita nang maingat pagkatapos ang root node ay binisita at sa huling kanang subtree ay binisita.
- Preorer- Sa punong ito ng traversal ang root node ay binisita sa una at pagkatapos ay kaliwa subtree at sa huling kanang subtree.
- Postorder- Ang pamamaraang ito ay bumibisita sa kaliwa ng subtree pagkatapos ng kanang subtree at sa huling root node.
- Sa B-puno, ang pinakamataas na bilang ng mga node ng bata na maaaring magkaroon ng non-terminal node ay M kung saan ang M ay ang pagkakasunud-sunod ng B-puno. Sa kabilang banda, ang isang Binary puno ay maaaring magkaroon ng higit sa dalawang mga subtrees o mga node ng bata.
- Ang B-puno ay ginagamit kapag ang data ay naka-imbak sa disk samantalang ginagamit ang binary tree kapag ang data ay nakaimbak sa mabilis na memorya tulad ng RAM.
- Ang isa pang lugar ng aplikasyon para sa B-tree ay ang istraktura ng data ng pag-index ng code sa DBMS, sa kaibahan, ang Binary tree ay nagtatrabaho sa pag-optimize ng code, huffman coding, atbp.
- Ang maximum na taas ng isang B-puno ay logMN (M ang pagkakasunud-sunod ng puno). Tulad ng laban sa, ang pinakamataas na taas ng puno ng kahoy ay mag-log2N (N ang bilang ng mga node at base ay 2 sapagkat ito ay para sa binary).
Konklusyon
Ang B-puno ay ginagamit sa paglipas ng binary at binary search tree ang pangunahing dahilan sa likod nito ay ang hierarchy ng memorya kung saan konektado ang CPU sa cache na may mataas na bandwidth channel habang ang koneksyon ay konektado sa disk sa pamamagitan ng mababang bandwidth channel. Ginagamit ang isang punungkahoy na puno kapag ang mga tala ay nakaimbak sa RAM (maliit at mabilis) at ginagamit ang B-tree kapag ang mga tala ay nakaimbak sa disk (malaki at mabagal). Kaya, ang paggamit ng B-puno sa halip na Binary tree ay makabuluhang binabawasan ang oras ng pag-access dahil sa mataas na kadahilanan ng sumasanga at nabawasan ang taas ng puno.
