Bài giảng toán rời rạc phần các ứng dụng của cây
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (354.47 KB, 9 trang )
Cây
8.2. Các ứng dụng của cây
Tài liệu này được soạn theo sách Toán học rời rạc ứng dụng trong tin học , K. H.
Rosen, người dòch: Phạm Văn Thiều và Đặng Hữu Thònh, Nhà xuất bản Khoa học
và kỹ thuật, 1998.
Tài liệu lưu hành nội bộ
10/01/15
8.2. Các ứng dụng
1
Cây tìm kiếm nhò phân
– Cây tìm kiếm nhò phân: Cây nhò phân, trong đó:
° mỗi con của một đỉnh hoặc là con bên phải hoặc là con bên
trái, không có đỉnh nào có hơn một con bên phải hay con
bên trái,
° mỗi đỉnh được gán một khoá;
° Khoá của đỉnh lớn hơn khoá của tất cả các đỉnh thuộc cây
con bên trái, và nhỏ hơn khoá của tất cả các đỉnh thuộc cây
con bên phải của nó.
– Ví dụ 1. Tạo cây tìm kiếm nhò phân dùng thứ tự từ điển cho các
từ sau: mathematics, physics, geography, zoology, meteorology,
geology, psychology và chemistry.
10/01/15
8.2. Các ứng dụng
2
Cây tìm kiếm nhò phân: Xây dựng cây tìm kiếm nhò phân
10/01/15
8.2. Các ứng dụng
3
Cây tìm kiếm nhò phân: Thuật toán tìm kiếm nhò phân
•
•
•
•
•
•
•
•
procedure insertion(T: cây tìm kiếm nhò phân, x: phần tử)
v := gốc của T
{Đỉnh không có trong T sẽ có giá trò bằng null; với mọi x, label(null) ≠ x}
while v ≠ null và label(v) ≠ x
begin
• if x < label(v) then
•
if con bên trái của v ≠ null then v := con bên trái của v
•
else thêm đỉnh mới là con bên trái của v và đặt v := null
• else
•
if con bên phải của v ≠ null then v := con bên phải của v
•
else thêm đỉnh mới là con bên phải của v và đặt v := null
end
if gốc của T = null then thêm đỉnh r vào cây và gán cho nó nhãn là x
else if label(v) ≠ x then gán nhãn cho đỉnh mới là x.
10/01/15
8.2. Các ứng dụng
4
Cây tìm kiếm nhò phân
•
Độ phức tạp
– Cây tìm kiếm nhò phân T ứng với n phần tử
– Xây dựng cây nhò phân đầy đủ U từ T bằng cách thêm vào T
các đỉnh không có nhãn sao cho mọi đỉnh có khoá đều có 2 con.
– Số phép so sánh nhiều nhất để thêm phần tử mới là độ dài của
đường đi dài nhất trong U từ gốc tới một lá
° U có n đỉnh trong, (ii) Đònh lý 4 Chương 8.1 ⇒ U có n + 1 lá
° Hệ quả 1 Chương 8.1 ⇒ chiều cao của U ≥ log(n + 1)
° ⇒ Phải thực hiện ít nhất log(n + 1) phép so sánh để thêm
phần tử mới vào cây.
° Nếu T là cân đối thì U là cân đối, Hệ quả 1 Chương 8.1 ⇒
chiều cao của U là log(n + 1) .
10/01/15
8.2. Các ứng dụng
5
Cây tìm kiếm nhò phân
•
Thêm các đỉnh không nhãn để tạo cây tìm kiếm nhò phân đầy đủ
10/01/15
8.2. Các ứng dụng
6
Cây quyết đònh
– Cây quyết đònh: cây có gốc, trong đó:
° mỗi đỉnh tương ứng với một quyết đònh, và mỗi cây con tại
các đỉnh này ứng với mỗi một kết cục có thể của quyết đònh.
– Ví dụ 2. Có bảy đồng xu, tất cả có trọng lượng như nhau, và một
đồng giả có trọng lượng nhỏ hơn các đồng khác.
° Nếu dùng một chiếc cân có có hai đóa cân thì phải cần bao
nhiêu lần cân để xác đònh đồng xu nào trong tám đồng xu
này là đồng xu giả.
° Hãy đề xuất một thuật toán tìm đồng xu giả.
10/01/15
8.2. Các ứng dụng
7
Cây quyết đònh
– Có 3 khả năng xảy ra mỗi lần cân:
° 1. Hai đóa có trọng lượng bằng nhau
° 2. Đóa thứ nhất nặng hơn
° 3. Đóa thứ hai nặng hơn
– Vậy cây quyết đònh cho một dãy các lần cân là cây 3-phân.
° Cây quyết đònh có ít nhất 8 lá
° Số lần cân nhiều nhất để xác đònh đồng xu giả là chiều cao
của cây quyết đònh
° Chiều cao của cây quyết đònh thoả
• h ≥ logm l = log3 8 = 2
°
°
⇒ Cần ít nhất 2 lần cân.
Có thể xác đònh đồng xu giả bằng 2 lần cân.
10/01/15
8.2. Các ứng dụng
8
Cây quyết đònh
•
Cây quyết đònh để xác đònh đồng xu giả
10/01/15
8.2. Các ứng dụng
9
