Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
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 pps
Nội dung xem thử
Mô tả chi tiết
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
Trang: 208
B7: AncL->Bal = 1
Chuyeå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
h
Quaù trình quay keùp ñöôïc thöïc hieän thoâng caùc böôùc sau:
B1: AncestorNode->BAL_Left = AncLR->BAL_Right
B2: AncL->BAL_Right = AncLR->BAL_Left
B3: AncLR->BAL_Right = AncestorNode
B4: AncLR->BAL_Left = AncL
Hieäu chænh laïi caùc chæ soá caân baèng:
B5: AncestorNode->Bal = -1
B6: AncLR->Bal = 0
B7: AncL->Bal = 0
Chuyeån vai troø cuûa AncLR cho AncestorNode vaø chuùng ta coù caây caân baèng môùi:
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
Trang: 209
B8: 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 h
Quaù trình quay keùp ñöôïc thöïc hieän thoâng caùc böôùc sau:
B1: AncestorNode->BAL_Left = AncLR->BAL_Right
B2: AncL->BAL_Right = AncLR->BAL_Left
B3: AncLR->BAL_Right = AncestorNode
B4: AncLR->BAL_Left = AncL
Hieäu chænh laïi caùc chæ soá caân baèng:
B5: AncestorNode->Bal = 0
B6: AncLR->Bal = 0
B7: AncL->Bal = 0
Chuyeån vai troø cuûa AncLR cho AncestorNode vaø chuùng ta coù caây caân baèng môùi:
B8: AncestorNode = AncLR