Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 có nội dung trình bày về các heap hợp nhất, thời gian chạy của các thao tác lên heap hợp nhất, heap nhị thức, định nghĩa về cây nhị thức, đặc tính của cây nhị thức, biểu diễn heap nhị thức, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Caùc heap hôïp nhaát ñöôïc ª Heap nhò phaân ª Moät heap hôïp nhaát ñöôïc mergeable heap laø moät caáu truùc döõ lieäu hoã trôï naêm thao taùc sau goïi laø caùc thao taùc heap hôïp nhaát ñöôïc . MAKE-HEAP taïo vaø traû veà moät heap troáng. INSERT H x cheøn nuùt x maø tröôøng key cuûa noù ñaõ ñöôïc ñieàn vaøo heap H . MINIMUM H traû veà moät con troû chæ ñeán nuùt trong heap H maø khoùa cuûa noù laø nhoû nhaát. EXTRACT-MIN H taùch ra nuùt coù khoùa nhoû nhaát khoûi H vaø traû veà moät con troû chæ ñeán nuùt ñoù. UNION H1 H2 taïo vaø traû veà moät heap môùi chöùa taát caû caùc nuùt cuûa caùc heaps H1 vaø H2 . Caùc heaps H1 vaø H2 seõ bò huûy bôûi thao taùc naøy. 2.10.2004 Chöông 5 Heap nhò thöùc 1 Thôøi gian chaïy cuûa caùc thao taùc leân heaps hôïp nhaát ñöôïc ª n laø soá nuùt cuûa heap Thuû tuïc heap heap heap nhò phaân nhò thöùc Fibonacci worst-case worst-case khaáu hao MAKE-HEAP 1 1 1 INSERT lg n O lg n 1 MINIMUM 1 O lg n 1 EXTRACT-MIN lg n lg n O lg n UNION n O lg n 1 DECREASE-KEY lg n lg n 1 DELETE lg n lg n O lg n 2.10.2004 Chöông 5 Heap nhò thöùc 2 Heap nhò thöùc ª Heap nhò thöùc Hoã trôï theâm caùc thao taùc DECREASE-KEY H x k gaùn vaøo nuùt x trong heap H trò môùi k cuûa khoùa k nhoû hôn hay baèng trò hieän thôøi cuûa khoùa. DELETE H x xoùa nuùt x khoûi heap H. ª Nhaän xeùt Heap nhò thöùc khoâng hoå trôï thao taùc SEARCH höõu hieäu. Do ñoù caùc thao taùc DECREASE-KEY vaø DELETE caàn moät con troû ñeán nuùt caàn ñöôïc xöû lyù. 2.10.2004 Chöông 5 Heap nhò thöùc 3 Ñònh nghóa caây nhò thöùc ª Caây nhò thöùc Bk vôùi k 0 1 2 laø moät caây coù thöù töï ñöôïc ñònh nghóa ñeä quy Caây nhò thöùc B0 goàm moät nuùt duy nhaát. Caây nhò thöùc Bk goàm hai caây nhò thöùc Bk - 1 ñöôïc lieân keát vôùi nhau theo moät caùch nhaát ñònh Nuùt goác cuûa caây naøy laø con beân traùi nhaát cuûa nuùt goác cuûa caây kia. B0 Bk - 1 Bk - 1 Bk 2.10.2004 Chöông 5 Heap nhò thöùc 4 Ñònh nghóa caây nhò thöùc ñoä saâu 0 1 2 3 4 B0 B1 B2 B3 B4 2.10.2004 Chöông 5 Heap nhò thöùc 5 Ñaëc tính cuûa