Cây AA (AA tree)
Đượ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ác khái niệm
Tính chất
Ví dụ
Các phép biến đổi cây
Các thao tác trên cây
16 trang |
Chia sẻ: candy98 | Lượt xem: 770 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cấu trúc cây (P3) - Văn Chí Nam, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
©FIT-HCMUS 1
AA tree
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
73
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
74
Đượ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).
©FIT-HCMUS 2
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
75
Mức của node
Liên kết ngang
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
76
Mức của node:
Số liên kết trái từ node đó đến node NULL.
Mức của NULL là 0.
Mức của node lá là 1.
5 10
15
20
Mức 1
Mức 2
©FIT-HCMUS 3
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
77
Liên kết ngang:
Liên kết giữa node cha và node con có cùng mức.
5 10
15
20
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
78
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ại 2 liên kết ngang liên tiếp.
[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.
©FIT-HCMUS 4
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
79
30 70
85
5
60
80
10
90
15
20
50
35 40 6555
Mức của các node?
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
80
30 70
85
5
60
80
10
90
15
20
50
35 40 6555
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
©FIT-HCMUS 5
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
81
30 70
85
5
60
80
10
90
15
20
50
35 40 6555
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
82
30 70
85
5
60
80
10
90
15
20
50
35 40 6555
Có tồn tại 2 liên kết ngang liên tiếp?
©FIT-HCMUS 6
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
83
30 70
85
5
60
80
10
90
15
20
50
35 40 6555
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
84
30 70
85
5
60
80
10
90
15
20
50
35 40 6555
So sánh mức của các node con của các node: 15, 70, 60, 85?
©FIT-HCMUS 7
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
85
Skew
Split
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
86
Skew:
Dùng để loại bỏ liên kết ngang trái.
P X
A B C
P X
A B C
©FIT-HCMUS 8
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
87
Split:
Dùng để loại bỏ 2 liên kết ngang liên tiếp
X P
A B
G
X
P
A B
G
C D
C D
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
88
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.
©FIT-HCMUS 9
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
89
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
90
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.
©FIT-HCMUS 10
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
91
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
92
6
9
3
4
5 7
27
158 40
©FIT-HCMUS 11
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
93
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
94
9
27
5 7
3 4 6 8 15 40
©FIT-HCMUS 12
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
95
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
96
Xóa phần tử 8
6
9
3
4
5 7
27
158 40
©FIT-HCMUS 13
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
97
Xóa phần tử 8
6
9
3
4
5 7
27
15 40
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
98
Xóa phần tử 5
6
9
3
4
5 7
27
158 40
©FIT-HCMUS 14
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
99
Xóa phần tử 5
6
9
3
4
7
27
158 40
Giảm mức của 4
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
100
Xóa phần tử 5
6
93 4
7
27
158 40
Skew tại 4
©FIT-HCMUS 15
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
101
Xóa phần tử 5
6
943
7
27
158 40
Giảm mức
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
102
Xóa phần tử 5
6 9
43 7
27
158 40
©FIT-HCMUS 16
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
103
Xóa phần tử 5
6 9
43 7
27
158 40
Split tại 6
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
104
Xóa phần tử 5
6
9
43 7
27
158 40