- Trang Chủ
- Cơ sở dữ liệu
- Giáo trình hướng dẫn dùng thuật toán thêm một nút vào bên trái nhất của cây nhị phân p10
Xem mẫu
- 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
- 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
- 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
- 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
- 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