Tìm hiểu tầm quan trọng của cấu trúc dữ liệu trong giải thuật phần 10

Tham khảo tài liệu tìm hiểu tầm quan trọng của cấu trúc dữ liệu trong giải thuật phần 10, công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Tìm hiểu tầm quan trọng của cấu trúc dữ liệu trong giải thuật phần 10 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 ...