Xem mẫu

  1. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k B2: AncR->BAL_Left = AncRL->BAL_Right AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h B3: AncRL->BAL_Left = AncestorNode AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h Trang: 198
  2. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k B4: AncRL->BAL_Right = AncR AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h Hieäu chænh laïi caùc chæ soá caân baèng: B5: AncestorNode->Bal = 0 B6: AncRL->Bal = 0 B7: AncR->Bal = -1 Chuyeån vai troø cuûa AncRL cho AncestorNode vaø chuùng ta coù caây caân baèng môùi: B8: AncestorNode = AncRL AncestorNode AncRL 0 AncR AncL 0 AncRLL AncRLR -1 AncRR h-1 h h h Trang: 199
  3. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k - AncRLL coù chieàu cao laø h-1 vaø AncRLR coù chieàu cao laø h (AncRL->Bal =-1; h ≥ 1) AncestorNode AncL -2 AncR AncRL 1 AncRR h -1 AncRLL AncRLR h h-1 h Ñeå caân baèng laïi AncestorNode hoaøn toaøn gioáng vôùi tröôøng hôïp treân, duy chæ khaùc nhau veà giaù trò chæ soá caân baèng sau khi quay keùp. Chuùng ta cuõng thöïc hieän caùc böôùc sau: B1: AncestorNode->BAL_Right = AncRL->BAL_Left B2: AncR->BAL_Left = AncRL->BAL_Right B3: AncRL->BAL_Left = AncestorNode B4: AncRL->BAL_Right = AncR B5: AncestorNode->Bal = 1 B6: AncR->Bal = 0 B7: AncRL->Bal = 0 B8: AncestorNode = AncRL Sau khi quay keùp caây seõ trôû thaønh: AncestorNode AncRL 0 AncR AncL 1 AncRLL AncRLR 0 AncRR h-1 h h h Trang: 200
  4. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k - Caû AncRLL vaø AncRLR ñeàu coù chieàu cao laø h (AncRL->Bal =0; h ≥ 0) AncestorNode AncL -2 AncR AncRL 1 AncRR h 0 AncRLL AncRLR h h h Cuõng töông töï, chuùng ta caân baèng laïi AncestorNode baèng caùch quay keùp gioáng nhö tröôøng hôïp treân nhöng veà giaù trò chæ soá caân baèng sau khi quay thì khaùc nhau. Caùc böôùc thöïc hieän nhö sau: B1: AncestorNode->BAL_Right = AncRL->BAL_Left B2: AncR->BAL_Left = AncRL->BAL_Right B3: AncRL->BAL_Left = AncestorNode B4: AncRL->BAL_Right = AncR B5: AncestorNode->Bal = 0 B6: AncR->Bal = 0 B7: AncRL->Bal = 0 B8: AncestorNode = AncRL Sau khi quay keùp caây seõ trôû thaønh: AncestorNode AncRL 0 AncR AncL 0 AncRLL AncRLR 0 AncRR h h h h Trang: 201
  5. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o Ví duï: Theâm nuùt coù Key = 27 vaøo caây nhò phaân tìm kieám caân baèng sau ñaây: c u -tr a c k c u -tr a c k BALTree 25 -1 19 0 40 0 NULL NULL 30 0 44 0 NULL NULL NULL NULL Caây nhò phaân tìm kieám caân baèng sau khi theâm nuùt coù Key = 27 nhö sau: BALTree 25 -2 19 0 40 1 NULL NULL 30 1 44 0 27 0 NULL NULL NULL NULL NULL Thöïc hieän quay ñôn caây con traùi cuûa BALTree->BAL_Right caây nhò phaân tìm kieám sau khi quay trôû thaønh caây nhò phaân tìm kieám nhö sau: BALTree 25 -2 19 0 30 -1 NULL NULL 27 0 40 -1 NULL NULL NULL 44 0 NULL NULL Thöïc hieän quay ñôn caây con phaûi cuûa BALTree caây nhò phaân tìm kieám sau khi quay trôû thaønh caây nhò phaân tìm kieám caân baèng nhö sau: Trang: 202
nguon tai.lieu . vn