Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc cây

ữ ệ

ấ

ả

C u trúc d li u và gi

ậ i thu t

Cấu trúc cây

ả

Gi ng viên:

Đậu Ngọc Hà Dương

Nội dung trình bày

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Khái niệm

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Một số thuật ngữ

 Tree

 Search tree

 Binary search tree

 Balanced tree

 AVL tree

 AA tree

 Red-Black tree

 … ấ C u trúc d li u và gi

ữ ệ ả ậ i thu t HCMUS 2011

Cây tổng quát

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây tổng quát

Cây thư mục

Sơ đồ tổ chức ậ

ữ ệ ấ ả C u trúc d li u và gi i thu t HCMUS 2011

Định nghĩa

Cây (cây có gốc) được xác định đệ quy như

ộ

là m t cây. Cây này có

g cố là

ậ ỉ

đ nhỉ ồ ợ 1. T p h p g m 1 ấ ủ đ nh duy nh t c a nó.

ắ

ọ

2. G i T1, T2, … Tk (k ≥ 1) là các cây không c t nhau

ố ươ ứ

có g c t

ng ng r1, r2, … rk.

ộ

ạ

ậ

ồ

ả ử r là m t đ nh m i không thu c các cây Ti. Khi r và các cây Ti t o thành

c ượ

ớ ớ ố r. Các cây T1, T2, … Tk đ

ộ ỉ ớ s ỉ ợ đó, t p h p T g m đ nh ộ m t cây m i v i g c ủ ố ọ g i là cây con c a g c r. ữ ệ ậ i thu t HCMUS 2011 C u trúc d li u và gi

ấ ả

Định nghĩa

Nút gốc

r

r 2

r 1

r k

T2

T1

Tk

Cây con

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các khái niệm

 node: đỉnh

 root: gốc cây

 leaf: lá

 inner node/internal node: đỉnh trong

 parent: đỉnh cha

 child: đỉnh con

 path: đường đi

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các khái niệm

Nút gốc

r

rk

r 2

r 1

r k

k 1

k 2

T2

T1

Tk

k 3

k 4

k 5

Cây con

Nút lá

Đường đi

k 6

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các khái niệm

 degree/order: bậc

ậ ủ

ủ

ố

 B c c a node: S con c a node

ậ ủ

ậ ớ

ấ

ố

 B c c a cây: b c l n nh t trong s các con

 depth/level: độ sâu/mức

ứ

ủ

ề

ủ ườ

ừ

ng đi t

ộ ố ế

ộ

 M c (đ sâu)c a node: Chi u dài c a đ node g c đ n node đó c ng thêm 1.

 height: chiều cao

ề

 Chi u cao cây:

 Cây rỗng: 0

 Cây khác rỗng: Mức lớn nhất giữa các node của cây

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các khái niệm

Bậc = k Nút gốc

r

Bậc = 2

Độ cao = 4

rk

r 2

r 1

r k

k 1

k 2

T2

T1

Tk

k 3

k 4

k 5

Cây con

Nút lá

Đường đi

k 6

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép duyệt cây

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép duyệt cây

 Đảm bảo đến mỗi node trên cây chính xác một

lần một cách có hệ thống.

 Nhiều thao tác xử lý trên cây cần phải sử dụng

đến phép duyệt cây.

 Các phép cơ bản:

ệ ướ

 Duy t tr

c (Preorder)

ấ ậ ả i thu t HCMUS 2011

ệ

 Duy t sau (Postorder)

ữ ệ ệ C u trúc d li u và gi ữ  Duy t gi a (Inorder)

Phép duyệt cây

Parent(a)?

Parent(b) = a

a

Eldest- Child(c) = g

c

b

e

d

f

g

h

NextSibling(g) = h

i

NextSibling(h)?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép duyệt cây

Duyệt theo chiều sâu

b c

g e f h

i j k

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép duyệt cây

 Pre-order

 Post-order

void Preorder(NODE A)

void Postorder(NODE A)

{

NODE B;

Visit(A);

B = EldestChild(A); while (B != (cid:0)

(cid:0) ) {

B = EldestChild(A); while (B != (cid:0)

(cid:0) ) {

Preorder(B);

Postorder(B);

B = NextSibling(B);

}

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Visit(A);

}

Phép duyệt cây

In-Order

void Inorder(NODE A) {

NODE B; B = EldestChild(A); if (B != (cid:0)

(cid:0) ) { Inorder(B); B = NextSibling(B);

} Visit(A); while (B != (cid:0)

(cid:0) ) {

Inorder(B); B = NextSibling(B);

}

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Biểu diễn cây

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bằng danh sách cây con

child

info id next

2 3 1 a

5 4 2 b

a

7 6 8 3 c

4 d 9 10

b

c

5 e

6 f 11

7 g

d

e

f

h

g

8 h

9 i

k

i

j

10 j ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

11 k

Bằng danh sách cây con

A Root

B C

D E F H G

I J K

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bằng đỉnh trái nhất và đỉnh kề phải

Info Eldest Child Next Sibling

a

1 a 2 0

2 b 4 3

3 c 6 0

b

c

4 d 0 5

5 e 9 0

6 f 0 7

g

d

e

f

h

7 g 11 8

8 h 0 0

9 i 0 10

i

j

k

10 j 0 0

11 k 0 0

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bằng đỉnh trái nhất và đỉnh kề phải

A Root

B C

D E F H G

I J K

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bằng cha mỗi đỉnh

Info Parent

a

1 a 0

2 b 1

3 c 1

4 d 2

b

c

5 e 2

6 f 3

7 g 3

g

d

e

f

h

8 h 3

9 i 5

10 j 5

i

j

k

11 k 7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây nhị phân

 Binary tree

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây nhị phân

a

 Là cây mà mỗi đỉnh có bậc tối đa bằng 2.

b

c

 Các cây con được

d

e

f

g

gọi là cây con trái và cây con phải.

j

h

i

 Có toàn bộ các thao tác cơ bản của cây.

struct NODE {

Data key; NODE *pLeft; NODE *pRight;

};

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Một số ứng dụng

 Cây tổ chức thi đấu

 Cây biểu thức số học

 Lưu trữ và tìm kiếm

* +

thông tin.

4 - 1 sin

Cây biểu thức: 4 * (3 – 4) + (1 + sin(30))

3 4 30

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây nhị phân tìm kiếm

 Cây nhị phân tìm kiếm là cây nhị phân thỏa mãn

các điều kiện sau:

1. Khóa của các đỉnh thuộc cây con trái nhỏ hơn

khóa gốc.

2. Khóa của gốc nhỏ hơn khóa các đỉnh thuộc

cây con phải.

3. Cây con trái và cây con phải của gốc cũng là

cây nhị phân tìm kiếm.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây nhị phân tìm kiếm

8

4

10

9

23

2

6

20

5

7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây nhị phân tìm kiếm

 Đặc điểm:

 Có th tứ ự

ầ ử

 Không có ph n t

trùng

ạ ữ ệ ắ

ễ

ế

 D dàng t o d li u s p x p, và tìm ki m

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thao tác trên cây nhị phân tìm kiếm

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các thao tác

 Thêm phần tử (khóa)

 Tìm kiếm phần tử (khóa)

 Xóa phần tử (khóa)

 Sắp xếp

ữ ệ ả ậ i thu t HCMUS 2011

 Quay cây

ấ C u trúc d li u và gi  Duyệt cây

Thêm phần tử

 Bước 1: Bắt đầu từ gốc

 Bước 2: So sánh dữ liệu (khóa) cần thêm với

dữ liệu (khóa) của node hiện hành.

ồ ạ

ế

ằ

 N u b ng nhau => Đã t n t

ế i. K t thúc

ỏ ơ

ế ướ

ế

 N u nh h n => Đi qua nhánh trái, Ti p b

c 2.

ế ớ

ế ướ

ả

 N u l n h n => Đi qua nhánh ph i, Ti p b

c 2.

 Bước 3: Không thể đi tiếp nữa => Tạo node mới ấ C u trúc d li u và gi

ữ ệ ậ ả

với dữ liệu (khóa) cần thêm. Kết thúc i thu t HCMUS 2011

Tìm kiếm phần tử

 Bước 1: Bắt đầu từ gốc

 Bước 2: So sánh dữ liệu (khóa) cần tìm với dữ

liệu (khóa) của node hiện hành.

ế

ằ

ấ

 N u b ng nhau => Tìm th y. K t thúc

ỏ ơ

ế ướ

ế

 N u nh h n => Đi qua nhánh trái, Ti p b

c 2.

ế ớ

ế ướ

ả

 N u l n h n => Đi qua nhánh ph i, Ti p b

c 2.

 Bước 3: Không thể đi tiếp nữa => Không tìm ấ C u trúc d li u và gi

ữ ệ ậ ả i thu t HCMUS 2011

thấy. Kết thúc.

Xóa phần tử

 Tìm đến node chứa dữ liệu (khóa) cần xóa.

 Xét các trường hợp:

 Node lá

ỉ  Node ch có 1 con

ầ ử ế ạ

ể

 Node có 2 con: dùng ph n t

ế th m ng đ xóa th .

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Sắp xếp

15

 Cho cây nhị phân tìm kiếm

8

19

 Thứ tự duyệt các node

nếu sử dụng Duyệt giữa?

16

1

9

13

18

 Nêu nhận xét

ạ ữ ệ ắ ế

ể ễ

 Có th d dàng t o d li u s p x p

14 ệ ữ n u dùng phép duy t gi a 15 13

ế 8

14

9

1

16

18

19

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép duyệt cây

 Duyệt trước

4 4

2 2 20 20

1 1 3 3 25 25

23 23

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép duyệt cây

 Duyệt giữa

4 4

2 2 20 20

1 1 3 3 25 25

23 23

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép duyệt cây

 Duyệt sau

4 4

2 2 20 20

1 1 3 3 25 25

23 23

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép quay trái

Quay trái cây P P P

b a

T3 T1

T2 T3 T1 T2

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép quay trái

Quay trái cây P

18 35

8 35 18 50

8 20 50 20 55

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép quay phải

Quay phải cây P

P P

b a

a b T3 T 1

T1 T2 T 2 T 3

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Phép quay phải

Quay phải cây P

40 50

37 50 40 55

55 36 65 45 37 45

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thời gian thực hiện các phép toán

 Đối với phép tìm kiếm:

ườ

ợ ố

ề

ấ

ỗ

 Tr

ng h p t

ừ t nh t: m i nút (tr nút lá) đ u có 2

ủ

ề

con: O(log2n) (chính là chi u cao c a cây).

ấ

ở ng h p x u nh t: cây tr thành danh sách liên

 Tr

ợ ườ k t: ế O(n).

ườ

ợ

 Tr

ng h p trung bình là bao nhiêu?

O(log2n)

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Tạo cây nhị phân tìm kiếm theo thứ tự nhập

như sau: 1, 8, 9, 12, 14, 15, 16, 18, 19

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Tạo cây nhị phân tìm kiếm theo thứ tự nhập

như sau: 1, 8, 9, 12, 14, 15, 16, 18, 19

1

8

9

12

14

15

16

18

19

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây AVL

 AVL tree

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Giới thiệu

 Do G.M. Adelsen Velskii và E.M. Lendis đưa ra

vào năm 1962, đặt tên là cây AVL.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Định nghĩa

 Cây cân bằng AVL là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độ cao của cây con trái và cây con phải không chênh lệch quá 1.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây AVL

 Ví dụ :

12 12

8 8 18 18

11 17 5 5 11 17

7 4 4 7

Cây AVL?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xây dựng cây cân bằng

 Việc xây dựng cây cân bằng dựa trên cây nhị phân tìm kiếm, chỉ bổ sung thêm 1 giá trị cho biết sự cân bằng của các cây con như thế nào.

 Cách làm gợi ý:

struct NODE {

Data key;

NODE pLeft, pRight;

int bal;

}; ấ C u trúc d li u và gi  Trong đó giá trị bal (balance, cân bằng) có thể

ữ ệ ậ ả i thu t HCMUS 2011

là: 0: cân bằng; 1: lệch trái; 2: lệch phải

Các trường hợp mất cân bằng

 Mất cân bằng trái-trái (L-L)

 Mất cân bằng trái-phải (L-R)

 Mất cân bằng phải-phải (R-R)

 Mất cân bằng phải-trái (R-L)

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các trường hợp mất cân bằng

 Mất cân bằng trái-trái (L-L)

8 18

17 5

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các trường hợp mất cân bằng

 Mất cân bằng trái-phải (L-R)

8 18

17 5

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các trường hợp mất cân bằng

 Mất cân bằng phải-phải (R-R)

8 18

11 5 22

25 7 4

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các trường hợp mất cân bằng

 Mất cân bằng phải-trái (R-L)

8 18

11 5 22

7 4 20

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 Giả sử tại một node cây xảy ra mất cân bằng

bên phải (cây con phải chênh lệch với cây con trái hơn một đơn vị):

ấ

ằ

ả

 M t cân b ng ph iph i (RR)

 Quay trái

ấ

ằ

ả

 M t cân b ng ph itrái (RL)

 Quay phải

 Quay trái ả C u trúc d li u và gi

ữ ệ ấ ậ i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-phải (RR):

Quay trái cây P P P

b a Q

b a

h+1 T1 h

h h+1 h h T2 T1 T2

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-phải (RR):

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-phải (RR):

Quay trái cây P

18 35

8 35 18 50

8 20 50 20 55

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-trái (RL):

ướ

ả

 B c 1: quay ph i Q

ướ

 B c 2: quay trái cây P

b h T1

c h T4

h-1 T3 h T2

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-trái (RL):

ả

 B c 1: quay ph i cây Q

ướ P

P Quay phải cây Q

a a

Q Q

c b h h T1 T 1

b h c h T4 T 2

T3 h- 1 T3 h-1 h h T2 T 4

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-trái (RL):

 B c 2: quay trái cây P

ướ P

P Quay trái cây P

c a

a c b T1 h

b h T2 T1 T2 h T 4 T 3 h- 1

h h

T3 h- 1 T4 h

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-trái (RL) – Bước 1:

P Quay phải cây Q

35 35

50 40 18 18

37 50 40 55 8 20 8 20

36 45 55 65 37 45

36 65

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 P mất cân bằng phải-trái (RL) - Bước 2:

P Quay trái cây P

35 40 Q

40 18 50 35

37 50 45 55 8 20 37 18

36 45 55 65 36 8 20

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xử lý mất cân bằng

 Khi một node cây xảy ra mất cân bằng bên trái (cây con trái chênh lệch với cây con phải hơn một đơn vị): (thực hiện đối xứng với trường hợp mất cân bằng bên phải)

ấ

ằ

 M t cân b ng tráitrái (LL)

 Quay phải

ấ

ằ

 M t cân b ng tráitrái (LR)

 Quay trái

ấ ữ ệ ậ C u trúc d li u và gi i thu t HCMUS 2011 ả  Quay phải

Xử lý mất cân bằng

Theo Wikipedia ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thao tác tìm kiếm

 Thực hiện hoàn toàn tương tự cây nhị phân tìm

kiếm.

8

4

10

9

23

2

6

20

5

7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thao tác thêm phần tử

 Thực hiện tương tự với việc thêm phần tử của

cây nhị phân tìm kiếm.

 Nếu xảy ra việc mất cân bằng thì xử lý bằng các

trường hợp mất cân bằng đã biết.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thao tác xóa phần tử

 Thực hiện tương tự cây nhị phân tìm kiếm: xét 3 trường hợp, và tìm phần tử thế mạng nếu cần.

 Sau khi xóa, nếu cây mất cân bằng, thực hiện

cân bằng cây.

 Lưu ý: việc cân bằng sau khi hủy có thể xảy ra

dây chuyền.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thao tác xóa phần tử

 Ví dụ: xóa 35

Phần tử thế mạng là 36

40 40

50 50 36 35

55 55 45 45 37 37 18 18

36 8 20 65 8 20 65

Cây vẫn cân bằng nên không phải hiệu chỉnh

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thao tác xóa phần tử

 Xóa phần tử 45

40 40

50 50 36 36

55 55 45 37 37 18 18

65 8 20 8 20 65

Node 50 bị lệch phải !!!

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thao tác xóa phần tử

 Xóa phần tử 45: cân bằng lại cây

Quay trái tại node 50

40 40

55 50 36 36

50 65 37 55 18 37 18

65 8 20 8 20

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Cây AA

 AA tree

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Hình thành

 Được đặt tên theo tác giả Arne Anderson (Thụy

Điển).

 Công trình được công bố năm 1993 (Balanced

Search Trees Made Simple).

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các khái niệm

 Mức của node

 Liên kết ngang

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các khái niệm

 Mức của node:

ố

ừ

ế

 S liên k t

node đó đ n node NULL.

ế trái t

 Mức của NULL là 0.

 Mức của node lá là 1.

15 M c 2ứ

M c 1ứ 5 10 20

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các khái niệm

 Liên kết ngang:

ữ

ứ

ế

 Liên k t gi a node cha và node con có cùng m c.

5 10 20

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Tính chất

 Cây AA là cây nhị phân tìm kiếm thỏa mãn các

tính chất sau:

ứ ủ

ỏ ơ

ứ

ả

ộ

ắ [1] M c c a node con trái b t bu c ph i nh h n m c ủ c a node cha.

ứ ủ

ặ ằ

ỏ ơ

ứ

ả [2] M c c a node con bên ph i nh h n ho c b ng m c ủ c a node cha.

ộ ướ

ế

ắ

ả

Liên k t ngang b t bu c h

ng sang ph i.

ứ ủ

ả ắ

ỏ ơ

ứ

ộ

[3] M c c a node cháu bên ph i b t bu c nh h n m c ủ c a node ông.

ồ ạ ả

ế

Không t n t ữ ệ C u trúc d li u và gi

i 2 liên k t ngang liên ti p. i thu t HCMUS 2011

ứ ớ

ả

ọ

[4] M i node có m c l n h n 1 ph i có 2 node con.

ế

ả

ộ

[5] N u m t node không có liên k t ngang ph i thì c hai

ủ

ứ

ả

node con c a nó ph i cùng m c.

ấ ậ

Ví dụ

70 30

15 50 60 85

80 90 35 40 55 65 5 10 20

ứ ủ M c c a các node?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

70 30

15 50 60 85

80 90 35 40 55 65 5 10 20

ự ế ủ ớ ứ ủ ứ ủ

ặ So sánh m c c a node con trái v i m c c a node cha tr c ti p c a nó? Các c p node: 15 và 30, 5 và 15, 50 và 70, 35 và 50, 55 và 60, 80 và 85

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

70 30

15 50 60 85

80 90 35 40 55 65 5 10 20

ướ ế Các liên k t ngang? ế ủ H ng c a liên k t ngang?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

70 30

15 50 60 85

80 90 35 40 55 65 5 10 20

ồ ạ ế ế Có t n t i 2 liên k t ngang liên ti p?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

70 30

15 50 60 85

80 90 35 40 55 65 5 10 20

ứ ớ ơ ọ ề M i node có m c l n h n 1 đ u có 2 node con?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

70 30

15 50 60 85

80 90 35 40 55 65 5 10 20

ứ ủ ủ So sánh m c c a các node con c a các node: 15, 70, 60, 85?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các phép biến đổi cây

 Skew

 Split

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các phép biến đổi cây

 Skew:

ể ạ ỏ

ế

 Dùng đ lo i b liên k t ngang trái.

P X P X

A B C A B C

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các phép biến đổi cây

 Split:

ể ạ ỏ

ế

ế  Dùng đ lo i b 2 liên k t ngang liên ti p

X P G

X G

A B C D

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Các phép biến đổi cây

 Skew: dùng để loại bỏ liên kết ngang bên trái.

 Split: dùng để loại bỏ 2 liên kết ngang (phải) liên

tiếp.

 Biến đổi theo thứ tự Skew -> Split (nếu có).

 Khi thực hiện thao tác Split, node giữa được

tăng thêm một mức.

ữ ệ ậ ấ ả C u trúc d li u và gi i thu t HCMUS 2011

Các thao tác trên cây

 Duyệt cây, Tìm kiếm:

ươ

ự

ế

ị

 T

ng t

cây nh phân tìm ki m

 Thêm phần tử

 Xóa phần tử

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Thêm phần tử

 Thực hiện tương tự trên cây nhị phân tìm kiếm.

 Phần tử được thêm vào luôn ở mức 1.

 Sau khi thêm, thực hiện các thao tác Skew và/hoặc Split để đảm bảo tính chất của cây.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

ứ ự ậ

ẽ

 V cây AA theo th t

nh p sau đây:

4, 7, 6, 3, 5, 9, 15, 27, 8, 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

4 9 27

3 5 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Hãy vẽ cây AA theo thứ tự nhập sau đây:

 40, 8, 27, 15, 9, 5, 3, 6, 7, 4

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

27 5 7

40 3 4 6 8 15

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Xóa phần tử

 Nếu không phải là node lá (mức của node là 1),

tìm phần tử thế mạng:

ầ ử ớ

ấ

 Ph n t

l n nh t bên nhánh trái (node lá).

 Xóa node lá:

ứ ủ

ế

ỏ  Gi m m c c a node cha n u m c c a node lá nh

ả h n.ơ

ự

ệ

ầ

 Th c hi n các thao tác Skew, Split c n thi

ế t

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 8

4 9 27

3 5 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 8

4 9 27

3 5 7 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 5

4 9 27

3 5 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 5

100

4 9 27

ứ ủ ả Gi m m c c a 4

3 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 5

101

3 4 9 27

Skew t i 4ạ

7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 5

102

ả ứ Gi m m c

4 3 9 27

7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 5

103

6 9 27

3 4 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 5

104

Split t i 6ạ

6 9 27

3 4 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

 Xóa phần tử 5

105

6 27

3 4 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

106

Bài tập

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bài tập

107

1. Xây dựng giải thuật xóa một đỉnh với khóa cho

trước ra khỏi cây nhị phân tìm kiếm.

2. Hãy chứng tỏ rằng trường hợp tìm kiếm trung bình cho cây nhị phân tìm kiếm là O(log2n)?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bài tập

108

3. Biểu diễn tình trạng cây nhị phân tìm kiếm sau khi thực hiện các thao tác sau:

ầ ượ

ự

 L n l

t thêm các node theo trình t

: M G B K S P D

C A H L F X N T W R.

 Xóa M.

 Xóa S.

ả

ự

ệ ế ế t k t qu sau khi duy t cây theo các trình t ướ

 Cho bi ữ gi a, tr

c và sau.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bài tập

109

4. Xây dựng giải thuật thực hiện các thao tác sau trên cây nhị phân tìm kiếm:

- Đếm số node lá.

- Tính độ cao cây.

- Tính độ cao của 1 node trong cây.

- Xuất ra các node có cùng độ cao.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bài tập

110

5. Biểu diễn tình trạng cây cân bằng AVL/cây AA sau khi thực hiện các thao tác sau:

ầ ượ

ự

 L n l

t thêm các node theo trình t

: 13 7 2 11 19 16

4 3 1 8 12 6 24 14 20 23 18

 Xóa 13.

 Xóa 19

ế

ườ

ằ

ợ

L u ý: cho bi

t các tr

ấ ng h p m t cân b ng.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bài tập

111

6. Hãy vẽ cây AVL với 12 nút có chiều cao cực đại trong tất cả các cây AVL 12 nút.

7. Tìm 1 dãy N khoá sao cho khi lần lượt dùng thuật toán thêm vào cây AVL sẽ phải thực hiện mỗi thao tác cân bằng (LL, LR, RL, RR) lại ít nhất 1 lần.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Hỏi và Đáp

112

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Đọc thêm ví dụ thêm phần tử

113

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

ứ ự ậ

ẽ

 V cây AA theo th t

nh p sau đây:

4, 7, 6, 3, 5, 9, 15, 27, 8, 40

114

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

115

ẩ 7

ữ ệ ấ ả ậ Thêm 4 ị Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

116

ẩ 6

ữ ệ ấ ả ậ Thêm 7 ị Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

117

ữ ệ ậ ấ ả Thêm 6 ế Quan sát các liên k t m i thêm C u trúc d li u và gi ớ i thu t HCMUS 2011

Ví dụ

118

6 7

ả 7

ấ ả ậ Thêm 6 Quay ph i nút ữ ệ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

119

ế ả ả K t qu sau khi quay ph i nút 7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

120

4 6 7

ế ế Hai liên k t ngang liên ti p

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

121

4 7

ẩ 3

ữ ệ ấ ả ậ ị Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

122

4 7

3 4 7

Thêm 3

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

123

3 4 7

ẩ 5

ữ ệ ấ ả ậ ị Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

124

3 4 7

Thêm 5

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

125

5 3 4 7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

126

4 7

3 5

ứ ệ M c hi n hành c a ủ 4, 6?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

127

4 6

7 3 5

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

128

4 6

7 3 5

ẩ ị Chu n b : Thêm 9

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

129

4 6

7 3 5

ẩ 15

ữ ệ ấ ả ậ Thêm 9 ị Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

130

4 6

7 3 5

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

131

4 6

7 9 15 3 5

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

132

4 6

9 3 5

15 7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

133

4 6 9

3 5 15 7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

134

4 9

3 5 7 15

ẩ 27

ữ ệ ấ ả ậ ị Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

135

4 9

3 5 7 15

ữ ệ ấ ả ậ Thêm 27 ị ẩ Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

136

4 9

3 5 7 15

8 27

Thêm 8

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

137

4 9

8 3 5 7 15 27

ẩ 40

ữ ệ ấ ả ậ ị Chu n b : Thêm C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

138

4 9

8 3 5 7 15 27

Thêm 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

139

4 9

8 3 5 7 15 27 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

140

4 9

3 5 7 27 8

15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Ví dụ

141

4 9 27

3 5 7 8 15 40

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011

Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc cây - Đậu Ngọc Hà Dương