Thiết Kế & Đánh Giá Thuật Toán Cây Tìm Kiếm Nhị Phân
TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung
(cid:1) Cây tìm kiếm nhị phân (TKNP) (cid:1) Dựng cây TKNP (cid:1) Cây TKNP cân bằng
(cid:1) Cây Đỏ - Đen (cid:1) Cây AVL (cid:1) Cây Treap
1
Định Nghĩa
(cid:1) Cây TKNP:
(cid:1) cây nhị phân
(cid:1) lưu khóa ở đỉnh trong (cid:1) lá rỗng
(cid:1) thỏa mãn tính chất:
(cid:1)(cid:2)(cid:3) (cid:4) ≤ (cid:1)(cid:2)(cid:3) (cid:6) ≤ (cid:1)(cid:2)(cid:3) (cid:7)
(cid:1) (cid:4) trong cây con trái của (cid:6) (cid:1) (cid:7) trong cây con phải của (cid:6)
(cid:6)
(cid:7)
(cid:4)
6
9 2
2
1 4 8
Thao Tác Chính
(cid:1) Cây TKNP thực hiện các tao thác chính
(cid:1) Truy vấn: không thay đổi cấu trúc cây TKNP
(cid:1) Tìm kiếm (SEARCH) (cid:1) Nhỏ nhất (MINIMUM) (cid:1) Lớn nhất (MAXIMUM) (cid:1) Trước (PREDECESSOR) (cid:1) Sau (SUCCESSOR)
(cid:1) Sửa đổi: thay đổi cấu trúc cây TKNP
(cid:1) Chèn (INSERT) (cid:1) Xóa (DELETE)
3
Tính Chất
(cid:1) (cid:4) trong cây con trái của (cid:6), (cid:7) trong cây con phải của (cid:6)
(cid:1)(cid:2)(cid:3) (cid:4) ≤ (cid:1)(cid:2)(cid:3) (cid:6) ≤ (cid:1)(cid:2)(cid:3) (cid:7)
(cid:1) Duyệt cây TKNP theo thứ tự trong, thăm các khóa theo
thứ tự tăng dần
(cid:1) Sử dụng cây TKNP cho
(cid:1) cài đặt từ điển
(cid:1) Cây thứ tự bộ phận (heap)
(cid:1) là cây tìm kiếm (cid:1) là cây nhị phân (cid:1) không phải cây TKNP (cid:1) dùng quản lý hàng đợi ưu tiên
4
Độ Phức Tạp Thời Gian
(cid:1) ℎ đô cao của cây (cid:1) (cid:9) độ lớn của cây (số đỉnh trong) (cid:1) Thời gian (cid:10)(ℎ), với các thao tác chính
(cid:1) Cây TKNP đầy đủ ℎ = log (cid:9) (cid:1) Cây TKNP là một xích (cid:9) nút ℎ = (cid:9)
6 6
9 9 2
5
10 1 4 8 8
Truy Vấn – Tìm Kiếm Tree-Search((cid:17),(cid:18)) 1
if (cid:17) = NIL or (cid:18) = (cid:17). (cid:18)(cid:23)(cid:24)
2
3
return (cid:17) if (cid:18) < (cid:17). (cid:18)(cid:23)(cid:24)
4
5
return Tree-Search((cid:17). (cid:26)(cid:23)(cid:27)(cid:28),(cid:18)) else return Tree-Search((cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28),(cid:18))
6
9 2
(cid:18) = 4: 6 (cid:18) = 4: 6 → 2 → 4 (cid:18) = 7: 6 → 9 → 8 → NIL
6
1 4 8
Truy Vấn – Tìm Kiếm
Iterative-Tree-Search((cid:17),(cid:18)) while (cid:17) ≠ NIL and (cid:18) ≠ (cid:17). (cid:18)(cid:23)(cid:24) 1
2
3
4
if (cid:18) < (cid:17). (cid:18)(cid:23)(cid:24) (cid:17) ← (cid:17). (cid:26)(cid:23)(cid:27)(cid:28) else (cid:17) ← (cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28)
5
return (cid:17)
6
9 2
Tìm (cid:18) = 4: 6 Tìm (cid:18) = 4: 6 → 2 → 4 Tìm (cid:18) = 7: 6 → 9 → 8 → NIL
7
1 4 8
Truy Vấn – Nhỏ/Lớn Nhất
Tree-Minimum((cid:17)) 1
while (cid:17). (cid:26)(cid:23)(cid:27)(cid:28) ≠ NIL
(cid:17) ← (cid:17). (cid:26)(cid:23)(cid:27)(cid:28)
6
2 3
9
return (cid:17) Nhỏ nhất: 6 → 2 → 1
2
1 4 8
Tree-Maximum((cid:17)) 1
while (cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28) ≠ NIL
(cid:17) ← (cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28)
2 3
return (cid:17) Lớn nhất: 6 → 9
8
Truy Vấn – Trước
Tree-Predecessor((cid:17)) 1
if (cid:17). (cid:26)(cid:23)(cid:27)(cid:28) ≠ NIL
2
return Tree-Maximum((cid:17). (cid:26)(cid:23)(cid:27)(cid:28))
3
4
(cid:24) = (cid:17). +,(cid:29)(cid:23)(cid:9)(cid:28) while (cid:24) ≠ NIL and (cid:17) = (cid:24). (cid:26)(cid:23)(cid:27)(cid:28)
5
6
(cid:17) = (cid:24) (cid:24) = (cid:24). +,(cid:29)(cid:23)(cid:9)(cid:28)
6
7
return (cid:24)
9 2
Trước: (cid:18) = 6: 6 → 2 → 4 Trước: (cid:18) = 8: 8 → 9 → 6
9
1 4 8
Truy Vấn – Sau
Tree-Succesor((cid:17)) if (cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28) ≠ NIL 1
2
return Tree-Minimum((cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28))
3
4
(cid:24) = (cid:17). +,(cid:29)(cid:23)(cid:9)(cid:28) while (cid:24) ≠ NIL and (cid:17) = (cid:24). (cid:29)(cid:30)(cid:31)ℎ(cid:28)
5
6
(cid:17) = (cid:24) (cid:24) = (cid:24). +,(cid:29)(cid:23)(cid:9)(cid:28)
6
7
return (cid:24)
9 2
Sau: (cid:18) = 6: 6 → 9 → 8 Sau: (cid:18) = 4: 4 → 2 → 6
10
1 4 8
Sửa Đổi – Chèn
6
9 2
1 4 8
if .. (cid:18)(cid:23)(cid:24) < (cid:17). (cid:18)(cid:23)(cid:24) (cid:17) = (cid:17). (cid:26)(cid:23)(cid:27)(cid:28) else (cid:17) = (cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28)
7
.. +,(cid:29)(cid:23)(cid:9)(cid:28) = (cid:24) if (cid:24) = NIL
-. (cid:29)//(cid:28) = .
elseif .. (cid:18)(cid:23)(cid:24) < (cid:24). (cid:18)(cid:23)(cid:24)
Tree-Insert(-,.) 1 (cid:24) = NIL 2 (cid:17) = -. (cid:29)//(cid:28) 3 while (cid:17) ≠ NIL 4 (cid:24) = (cid:17) 5 6 7 8 9 10 11 12 13
(cid:24). (cid:26)(cid:23)(cid:27)(cid:28) = . else (cid:24). (cid:29)(cid:30)(cid:31)ℎ(cid:28) = .
11
Sửa Đổi – Xóa
(cid:1) Xóa nút . khỏi cây - cây, 3 trường hợp
(cid:1) . không có con
(cid:1) xóa .
(cid:1) . chỉ có 1 con trái hoặc phải
(cid:1) chuyển con đó lên thay . (cid:1) . có cả con trái và phải
(cid:1) chuyển lớn nhất cây con trái hoặc nhỏ nhất cây
con phải (.′) lên thay .
(cid:1) xóa .′
(cid:1) Lưu ý: khi xóa . nên giảm độ cao của cây -
nếu có thể
12
Dựng Cây TKNP
(cid:1) Các thao tác chính trong thời gian (cid:10)(ℎ)
(cid:1) Dựng cây TKNP có độ cao (ℎ) càng nhỏ càng tốt
(cid:1) Dựng cây TKNP:
(cid:1) Chèn liên tục khóa vào cây, bắt đầu từ cây rỗng (cid:1) Tại mỗi nút, cây con trái và phải cân bằng
(cid:1) Chọn khóa (cid:18) nào cho nút . (cid:1) Vần đề tương tự như chọn phần tử chốt trong phân
hoạch của thuật toán Sắp Xếp Nhanh (cid:1) Chọn ngẫu nhiên khóa (cid:18) chèn vào cây
(cid:1) Độ cao trung bình ℎ = 1(log (cid:9))
13
Vấn Đề Khác (cid:1) Cần sửa Tree-Insert để xử lý khóa trùng nhau trong cây TKNP
(cid:1) Cách 1: chọn ngẫu nhiên cây
con trái/phải
if .. (cid:18)(cid:23)(cid:24) < (cid:17). (cid:18)(cid:23)(cid:24) (cid:17) = (cid:17). (cid:26)(cid:23)(cid:27)(cid:28) else (cid:17) = (cid:17). (cid:29)(cid:30)(cid:31)ℎ(cid:28)
(cid:1) Cách 2: dựa vào (cid:27)(cid:26),(cid:31) để chọn cây con trái/phải
(cid:1) Cách 3: sử dụng danh sách
.. +,(cid:29)(cid:23)(cid:9)(cid:28) = (cid:24) if (cid:24) = NIL
-. (cid:29)//(cid:28) = .
để lưu khóa trùng
elseif .. (cid:18)(cid:23)(cid:24) < (cid:24). (cid:18)(cid:23)(cid:24)
Tree-Insert(-,.) 1 (cid:24) = NIL 2 (cid:17) = -. (cid:29)//(cid:28) 3 while (cid:17) ≠ NIL 4 (cid:24) = (cid:17) 5 6 7 8 9 10 11 12 13
(cid:24). (cid:26)(cid:23)(cid:27)(cid:28) = . else (cid:24). (cid:29)(cid:30)(cid:31)ℎ(cid:28) = .
14
Cây TKNP Cân Bằng
(cid:1) Độ cao của cây TKNP cần nhỏ để các thao tác
chính thực hiện nhanh
(cid:1) Nếu cây TKNP “cân bằng” thực hiện các thao
tác trong 1(log (cid:9))
(cid:1) Tính chất “cân bằng” có thể bị phá vỡ với thao
tác sửa đổi (Chèn/Xóa) (cid:1) Sửa lại cấu trúc cây thông qua phép xoay
(cid:1) Hai loại cây TKNP “cân bằng”
(cid:1) Cây Đỏ - Đen (cid:1) Cây AVL
15
Cây Đỏ - Đen
(cid:1) Mỗi nút cần thêm 1-bit màu (cid:1) Tính chất
(cid:1) 1. Mỗi nút là đỏ hoặc đen (cid:1) 2. Gốc và lá (NIL) đen (cid:1) 3. Nếu một nút đỏ, thì con của nó đen (cid:1) 4. Mọi đường đi từ một nút đến các lá con có
cùng số lượng nút đen
(cid:1) 5. Không đường đi nào dài hơn gấp đôi
đường đi nào
(cid:1) Độ cao của cây Đỏ - Đen với (cid:9) nút
ℎ ≤ 2 log((cid:9) + 1)
16
Cây Đỏ - Đen – Ví Dụ
17
Cây Đỏ - Đen – Thao Tác
(cid:1) Các thao tác chèn và xóa có thể làm thay
đổi tính chất của cây (cid:1) Do chính các thao tác này (cid:1) Đổi màu các nút (cid:1) Cấu trúc lại các kết nối nút
(cid:1) Phép xoay: đảm bảo thứ tự trong của khóa (cid:1) Phép thực hiện trong thời gian 3(1)
18
Cây AVL
(cid:1) Georgy Adelson-Velsky & Evgenil Landis
đề xuất năm 1962
(cid:1) Độ cao 2 cây của của một nút khác nhau
nhiều nhất 1
(cid:1) Thời gian 3(log (cid:9)) cho các thao tác trong cả 2 trường hợp trung bình & xấu nhất
(cid:1) Cân bằng xây bằng phép xoay
19
Cây Treap
(cid:1) Dựng cây TKNP ngẫu nhiên (slide 13) sẽ
được cây tương đối cân bằng
(cid:1) Tuy nhiên nếu dữ liệu được cung cấp lần lượt, khóa sẽ không lựa chọn ngẫu nhiên
(cid:1) Cây Treap cung cấp giải pháp
(cid:1) Là sự kết hợp của cây TKNP và cây thứ tự
bộ phận (min-heap)
(cid:1) Khóa (cid:18)(cid:23)(cid:24) thỏa mãn cây TKNP (cid:1) Ưu tiên +(cid:29)(cid:30)/(cid:29)(cid:30)(cid:28)(cid:24) thỏa mãn cây min-heap
20
Cây TKNP Cân Bằng – Phép Xoay
(cid:1) Xem Mục 13.2 tr.312
21
