Chương 10 Cây nhiều nhánh

Như chúng ta đã thấy, cây nhị phân là một dạng cấu trúc dữ liệu đơn giản và ... Cấu trúc dữ liệu và giải thuật , con Mỗi node có 2 liên kết first_child và next_sibling Dùng cây nhị phân.
Nội dung trích xuất từ tài liệu:
Chương 10 " Cây nhiều nhánh"Chöông 10 – Caây nhieàu nhaùnhChöông 10 – CAÂY NHIEÀU NHAÙNH Chöông naøy tieáp tuïc nghieân cöùu veà caùc caáu truùc döõ lieäu caây, taäp trung vaøo caùccaây maø soá nhaùnh taïi moãi nuùt nhieàu hôn hai. Chuùng ta baét ñaàu töø vieäc trình baøycaùc moái noái trong caây nhò phaân. Keá tieáp chuùng ta tìm hieåu veà moät lôùp cuûa caây goïilaø trie ñöôïc xem nhö töø ñieån chöùa caùc töø. Sau ñoù chuùng ta tìm hieåu ñeán caây B-treecoù yù nghóa raát lôùn trong vieäc truy xuaát thoâng tin trong caùc taäp tin. Moãi phaàntrong soá naøy ñoäc laäp vôùi caùc phaàn coøn laïi. Cuoái cuøng, chuùng ta aùp duïng yù töôûngcuûa B-tree ñeå coù ñöôïc moät lôùp khaùc cuûa caây nhò phaân tìm kieám goïi laø caây ñoû-ñen(red-black tree).10.1. Vöôøn caây, caây, vaø caây nhò phaân Nhö chuùng ta ñaõ thaáy, caây nhò phaân laø moät daïng caáu truùc döõ lieäu ñôn giaûn vaøhieäu quaû. Tuy nhieân, vôùi moät soá öùng duïng caàn söû duïng caáu truùc döõ lieäu caây maøtrong ñoù soá con cuûa moãi nuùt chöa bieát tröôùc, caây nhò phaân vôùi haïn cheá moãi nuùt chæcoù toái ña hai con khoâng ñaùp öùng ñöôïc. Phaàn naøy laøm saùng toû moät ñieàu ngaïc nhieânthuù vò vaø höõu ích: caây nhò phaân cung caáp moät khaû naêng bieåu dieãn nhöõng caây khaùcbao quaùt hôn.10.1.1. Caùc teân goïi cho caây Tröôùc khi môû roäng veà caùc loaïi caây, chuùng ta xeùt ñeán caùc ñònh nghóa. Trongtoaùn hoïc, khaùi nieäm caây coù moät yù nghóa roäng: ñoù laø moät taäp baát kyø caùc ñieåm (goïilaø ñænh), vaø taäp baát kyø caùc caëp noái hai ñænh khaùc nhau (goïi laø caïnh hoaëc nhaùnh)sao cho luoân coù moät daõy lieân tuïc caùc caïnh (ñöôøng ñi) töø moät ñænh baát kyø ñeán moätñænh baát kyø khaùc, vaø khoâng coù chu trình, nghóa laø khoâng coù ñöôøng ñi naøo baét ñaàutöø moät ñænh naøo ñoù laïi quay veà chính noù. Ñoái vôùi caùc öùng duïng trong maùy tính, chuùng ta thöôøng khoâng caàn nghieân cöùucaây moät caùch toång quaùt nhö vaäy, vaø khi caàn laøm vieäc vôùi nhöõng caây naøy, ñeå nhaánmaïnh, chuùng ta thöôøng goïi chuùng laø caùc caây töï do (free tree). Caùc caây cuûa chuùngta phaàn lôùn luoân coù moät ñænh ñaëc bieät, goïi laø goác cuûa caây, vaø caùc caây daïng naøychuùng ta seõ goïi laø caùc caây coù goác (rooted tree). Moät caây coù goác coù theå ñöôïc veõ theo caùch thoâng thöôøng cuûa chuùng ta laø goác naèmtreân, caùc nuùt vaø nhaùnh khaùc quay xuoáng döôùi, vôùi caùc nuùt laù naèm döôùi cuøng. Maëcduø vaäy, caùc caây coù goác vaãn chöa phaûi laø taát caû caùc daïng caây maø chuùng ta thöôøngduøng. Trong moät caây coù goác, thöôøng khoâng phaân bieät traùi hoaëc phaûi, hoaëc khi moätnuùt coù nhieàu nuùt con, khoâng theå noùi raèng nuùt naøo laø nuùt con thöù nhaát, thöù hai,v.v...Neáu khoâng vì moät lyù do naøo khaùc, söï thi haønh tuaàn töï caùc leänh thöôøng buoäcchaët moät thöù töï leân caùc nuùt con cuûa moät nuùt. Chuùng ta ñònh nghóa moät caây coù thöùGiaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 237Chöông 10 – Caây nhieàu nhaùnhtöï (ordered tree) laø moät caây coù goác trong ñoù caùc con cuûa moät nuùt ñöôïc gaùn chomoät thöù töï. Löu yù raèng caùc caây coù thöù töï maø trong ñoù moãi nuùt coù khoâng quaù hai con vaãnchöa phaûi cuøng moät lôùp vôùi caây nhò phaân. Neáu moät nuùt trong caây nhò phaân chæ coùmoät con, noù coù theå naèm beân traùi hoaëc beân phaûi, luùc ñoù ta coù hai caây nhò phaânkhaùc nhau, nhöng chuùng cuøng laø moät caây coù thöù töï. Nhö moät nhaän xeùt cuoái cuøng lieân quan ñeán caùc ñònh nghóa, chuùng ta haõy löu yùraèng caây 2-tree maø chuùng ta ñaõ nghieân cöùu khi phaân tích caùc giaûi thuaät ôû nhöõngchöông tröôùc laø moät caây coù goác (nhöng khoâng nhaát thieát phaûi laø caây coù thöù töï) vôùiñaëc tính laø moãi nuùt trong caây coù 0 hoaëc 2 nuùt con. Hình 10.1 - Caùc daïng khaùc nhau cuûa caây. Hình 10.1 cho thaáy raát nhieàu daïng caây khaùc nhau vôùi soá nuùt nhoû. Moãi lôùp caâykeå töø caây ñaàu tieân coù ñöôïc baèng caùch keát hôïp caùc caây töø caùc lôùp coù tröôùc theonhieàu caùch khaùc nhau. Caùc caây nhò phaân coù theå coù ñöôïc töø caùc caây coù thöù töï töôngöùng, baèng caùch phaân bieät caùc nhaùnh traùi vaø phaûi.Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 238Chöông 10 – Caây nhieàu nhaùnh10.1.2. Caây coù thöù töï10.1.2.1. Hieän thöïc trong maùy tính Neáu chuùng ta muoán söû duïng moät caây coù thöù töï nhö moät caáu truùc döõ lieäu, moätcaùch hieån nhieân ñeå hieän thöïc trong boä nhôù maùy tính laø môû roäng caùch hieän thöïcchuaån cuûa moät caây nhò phaân, vôùi soá con troû thaønh vieân trong moãi nuùt töông öùngsoá caây con coù theå coù, thay vì chæ coù hai nhö ñoái vôùi caây nhò phaân. Chaúng haïn,trong moät caây coù moät vaøi nuùt coù ñeán möôøi caây con, chuùng ta caàn phaûi giöõ ñeánmöôøi con troû thaønh vieân trong moät nuùt. Nhöng nhö vaäy seõ daãn ñeán vieäc caây phaûichöùa moät soá raát lôùn caùc con troû chöùa trò NULL. Chuùng ta coù theå tính ñöôïc chínhxaùc con soá naøy. Neáu caây coù n nuùt, moãi nuùt coù k con troû thaønh vieân, thì seõ coù taát caûlaø n x k con troû. Moãi nuùt coù chính xaùc laø moät con troû tham chieáu ñeán noù, ngoaïi tröønuùt goác. Nhö vaäy coù n-1 con troû khaùc NULL. Tæ leä caùc con troû NULL seõ laø: (n x k) – (n – 1) 1 ⎯⎯⎯⎯⎯⎯⎯ > 1-⎯ nxk k Neáu moät nuùt coù theå coù möôøi caây con, thì coù hôn 90% con troû laø NULL. Roõ raønglaø phöông phaùp bieåu dieãn caây coù thöù töï naøy hao toán raát nhieàu vuøng nhôù. Lyù do laøvì, trong moãi nuùt, chuùng ta ñaõ giöõ moät danh saùch lieân tuïc caùc con troû ñeán taát caûcaùc con cuûa noù, vaø caùc danh ...