Giáo trình lý thuyết CTDL-GT-CD-TH

Nội dung của giáo trình đề cập những khái niệm cơ bản về vi xử lý, về công nghệ của một số vi xử lý thông dụng từ 8-bit đến 64-bit, từ kiến trúc tập lệnh phức tạp (CISC) đến kiến trúc tập lệnh giảm thiểu (RISC), được các nhà sản xuất hàng đầu thế giới như Intel, Zilog, Motorola, HP, IBM, Sun,… tạo ra; diễn giải các tập lệnh của các vi xử lý thông qua lập trình hợp ngữ, các nguyên tắc phối ghép và trao đổi thông tin giữa vi xử lý với thế giới vật lý...
Nội dung trích xuất từ tài liệu:
Giáo trình lý thuyết CTDL-GT-CD-TH Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi ThuaätB7: AncL->Bal = 1Chuyeån vai troø cuûa AncLR cho AncestorNode vaø chuùng ta coù caây caân baèng môùi:B8: AncestorNode = AncLR AncestorNode AncLR AncL 0 AncLL 1 AncLRL AncLRR 0 AncR h-1 h h h- AncLRL coù chieàu cao laø h vaø AncLRR coù chieàu cao laø h-1 (AncRL->Bal =1; h ≥ 1) AncestorNode AncL 2 AncR AncLL -1 AncLR AncLRL 1 AncLRR h h h-1 hQuaù trình quay keùp ñöôïc thöïc hieän thoâng caùc böôùc sau:B1: AncestorNode->BAL_Left = AncLR->BAL_RightB2: AncL->BAL_Right = AncLR->BAL_LeftB3: AncLR->BAL_Right = AncestorNodeB4: AncLR->BAL_Left = AncLHieäu chænh laïi caùc chæ soá caân baèng:B5: AncestorNode->Bal = -1B6: AncLR->Bal = 0B7: AncL->Bal = 0Chuyeån vai troø cuûa AncLR cho AncestorNode vaø chuùng ta coù caây caân baèng môùi: Trang: 208 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi ThuaätB8: AncestorNode = AncLR AncestorNode AncLR AncL 0 AncLL 0 AncLRL AncLRR -1 AncR h-1 h h h- Caû AncLRL vaø AncLRR ñeàu coù chieàu cao laø h (AncRL->Bal =0; h ≥ 0) AncestorNode AncL 2 AncR AncLL -1 AncLR AncLRL 1 AncLRR h h h hQuaù trình quay keùp ñöôïc thöïc hieän thoâng caùc böôùc sau:B1: AncestorNode->BAL_Left = AncLR->BAL_RightB2: AncL->BAL_Right = AncLR->BAL_LeftB3: AncLR->BAL_Right = AncestorNodeB4: AncLR->BAL_Left = AncLHieäu chænh laïi caùc chæ soá caân baèng:B5: AncestorNode->Bal = 0B6: AncLR->Bal = 0B7: AncL->Bal = 0Chuyeån vai troø cuûa AncLR cho AncestorNode vaø chuùng ta coù caây caân baèng môùi:B8: AncestorNode = AncLR Trang: 209 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät AncestorNode AncLR AncL 0 AncLL 0 AncLRL AncLRR 0 AncR h h h hVí duï: Theâm nuùt coù Key = 44 vaøo caây nhò phaân tìm kieám caân baèng sau ñaây: BALTree 50 1 35 0 70 0 20 0 40 0 NULL NULL NULL NULL NULL NULLCaây nhò phaân tìm kieám caân baèng sau khi theâm nuùt coù Key = 44 nhö sau: BALTree 50 2 35 -1 70 0 20 0 40 -1 NULL NULL NULL NULL NULL 44 0 NULL NULLThöïc hieän quay caây con phaûi cuûa BALTree->BAL_Left, caây nhò phaân tìm kieám sau khiquay trôû thaønh caây nhò phaân tìm kieám nhö sau: Trang: 210 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät BALTree 50 2 40 1 70 0 35 1 ...