Cây cân bằng - cây đỏ đen và cây 2-3-4

Nội dung chính của bài thuyết trình trình bày khái niệm, các thao tác, biểu diễn CTDL và đánh giá của cây cân bằng - cây đỏ đen và cây 2-3-4. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Cây cân bằng - cây đỏ đen và cây 2-3-4 MÔNCHUYÊNĐỀTỐTNGHIỆP KHOAHỌCMÁYTÍNH CHỦĐỀ1: CÂYCÂNBẰNG &CÂYĐỎĐEN&CÂY23 PhạmThịKhánhHuyền 4 Thànhviênnhóm: Ø Ø NguyễnThịKimDung Ø TrầnThịLan Ø NguyễnThịHồngNhung LOGO12/26/18 1 K65A_FIT_HNUE NỘIDUNGCHÍNH CÂYCÂNBẰNG CÂYĐỎĐEN CÂY234 BTREE12/26/18 2 K65A_FIT_HNUE CÂYCÂNBẰNG 1 Kháiniệm 2 Cácthaotác 3 BiểudiễnCTDL 4 Đánhgiá 5 Bàitậpminhhọa12/26/18 3 K65A_FIT_HNUE GIỚITHIỆUAVLTREE12/26/18 4 K65A_FIT_HNUE 1.KHÁINIỆMq CâycânbằngAVL • Là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độcaocủacâycontráivàcâyconphải khôngchênh lệchquá112/26/18 5 K65A_FIT_HNUE 1.KHÁINIỆMq Chỉsốcânbằngcủamộtnút:§ Định nghĩa: Chỉsốcânbằngcủamộtnútlà hiệu củachiềucaocâyconphảivàcâycontráicủanó.§ Đốivớimộtcâycânbằng,chỉsốcânbằng(CSCB) của mỗi nút chỉ có thể mang một trong ba giá trị sau: • CSCB(p)=0⇔Độcaocâyphải(p)=Độcaocâytrái(p) • CSCB(p)=1⇔Độcaocâyphải(p)>Độcaocâytrái(p) •12/26/18 CSCB(p)=1⇔Độcaocâyph6ải(p) 1.KHÁINIỆM 1. Câytrêncóphảilàcâycânbằnghaykhông? 2. XácđịnhCSCBcủamỗinúttrêncây?12/26/18 7 K65A_FIT_HNUE CÁCTRƯỜNGHỢPMẤTCÂNBẰNGq KhithêmnodemớivàocâyAVLcóthểxảyracác trườnghợpmấtcânbằngnhưsau: q Mấtcânbằngtrái–trái(LL) q Mấtcânbằngtrái–phải(LR) q Mấtcânbằngphải–phải(RR) q Mấtcânbằngphải–trái(RL)12/26/18 8 K65A_FIT_HNUE CÁCTRƯỜNGHỢPMẤTCÂNBẰNGq a)Mấtcânbằngtráitrái(LL)12/26/18 9 K65A_FIT_HNUE CÁCTRƯỜNGHỢPMẤTCÂNBẰNGq b)Mấtcânbằngtráiphải(LR)12/26/18 10 K65A_FIT_HNUE CÁCTRƯỜNGHỢPMẤTCÂNBẰNGq c)Mấtcânbằngphảiphải(RR)12/26/18 11 K65A_FIT_HNUE CÁCTRƯỜNGHỢPMẤTCÂNBẰNGq d)Mấtcânbằngphảitrái(RL)12/26/18 12 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Xửlýcụthểchocáctrườnghợpmấtcânbằngnhư sau: MẤTCÂNBẰNGPHẢIMấtcânbằngphảiphải(RR) Mấtcânbằngphảitrái(RL)Quaytráitạinodebịmấtcân Quayphảitạinodeconphảicủabằng nodebịmấtcânbằng Quaytráitạinodebịmấtcânbằng MẤTCÂNBẰNGTRÁIMấtcânbằngtráitrái(LL) Mấtcânbằngtráiphải(LR)Quayphảitạinodebịmấtcân Quaytráitạinodecontráicủabằng nodebịmấtcânbằng Quayphảitạinodebịmấtcân bằng 12/26/18 13 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Pmấtcânbằngphải–phải(RR):12/26/18 14 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Pmấtcânbằngphải–phải(RR):12/26/18 15 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Pmấtcânbằngphải–trái(RL)q Quátrìnhxửlýgồm2bướcsau:• Bước1:QuayphảiQ• Bước2:QuaytráicâyP12/26/18 16 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Pmấtcânbằngphải–trái(RL):• Bước1:QuayphảicâyQ12/26/18 17 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Pmấtcânbằngphải–trái(RL):• Bước2:QuaytráicâyP12/26/18 18 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Pmấtcânbằngphải–trái(RL):• Bước1:QuayphảicâyQ12/26/18 19 K65A_FIT_HNUE XỬLÝMẤTCÂNBẰNGq Pmấtcânbằngphải–trái(RL):• Bước2:QuaytráicâyP12/26/18 20 K65A_FIT_HNUE ...