Bài giảng Thiết kế và đánh giá thuật toán - Cây tìm kiếm nhị phân - Lê Nguyên Khôi

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

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

 Dựng cây TKNP

 Cây TKNP cân bằng

 Cây Đỏ - Đen

 Cây AVL

 Cây Treap
1
Định Nghĩa

 Cây TKNP:

 cây nhị phân 

 lưu khóa ở đỉnh trong

 lá rỗng

 thỏa mãn tính chất:

  ≤ 
  ≤ 
 

 trong cây con trái của 

 trong cây con phải của 
2
6
92
41 8


Thao Tác Chính

 Cây TKNP thực hiện các tao thác chính

 Truy vấn: không thay đổi cấu trúc cây TKNP

Tìm kiếm (SEARCH)

Nhỏ nhất (MINIMUM)

Lớn nhất (MAXIMUM)

Trước (PREDECESSOR)

Sau (SUCCESSOR)

 Sửa đổi: thay đổi cấu trúc cây TKNP

Chèn (INSERT)

Xóa (DELETE)
3
Tính Chất

  trong cây con trái của ,  trong cây con phải của 

  ≤ 
  ≤ 
 

 Duyệt cây TKNP theo thứ tự trong, thăm các khóa theo
thứ tự tăng dần

 Sử dụng cây TKNP cho

 cài đặt từ điển

 Cây thứ tự bộ phận (heap)

 là cây tìm kiếm

 là cây nhị phân

 không phải cây TKNP

 dùng quản lý hàng đợi ưu tiên
4
Độ Phức Tạp Thời Gian

 ℎ đô cao của cây

 	 độ lớn của cây (số đỉnh trong)

 Thời gian 
(ℎ), với các thao tác chính

 Cây TKNP đầy đủ ℎ = log 	

 Cây TKNP là một xích 	 nút ℎ = 	
5
6
92
41 8 10
6
9
8
Truy Vấn – Tìm Kiếm
Tree-Search(,)
1 if  = NIL or  = . 
2 return 
3 if  < . 
4 return Tree-Search(. ,)
5 else return Tree-Search(. ℎ,)
 = 4: 6
 = 4: 6 → 2 → 4
 = 7: 6 → 9 → 8 → NIL
6
6
92
41 8
Truy Vấn – Tìm Kiếm
Iterative-Tree-Search(,)
1 while  ≠ NIL and  ≠ . 
2 if  < . 
3 	  ← . 
4 else  ← . ℎ
5 return 
Tìm  = 4: 6
Tìm  = 4: 6 → 2 → 4
Tìm  = 7: 6 → 9 → 8 → NIL
7
6
92
41 8
Truy Vấn – Nhỏ/Lớn Nhất
Tree-Minimum()
1 while .  ≠ NIL
2 	  ← . 
3 return 
Nhỏ nhất: 6 → 2 → 1
Tree-Maximum()
1 while . ℎ ≠ NIL
2 	  ← . ℎ
3 return 
Lớn nhất: 6 → 9
8
6
92
41 8
Truy Vấn – Trước
Tree-Predecessor()
1 if .  ≠ NIL
2 return Tree-Maximum(. )
3  = . +,	
4 while  ≠ NIL and  = . 
5  = 
6  = . +,	
7 return 
Trước:  = 6: 6 → 2 → 4
Trước:  = 8: 8 → 9 → 6
9
6
92
41 8
Truy Vấn – Sau
Tree-Succesor()
1 if . ℎ ≠ NIL
2 return Tree-Minimum(. ℎ)
3  = . +,	
4 while  ≠ NIL and  = . ℎ
5  = 
6  = . +,	
7 return 
Sau:  = 6: 6 → 9 → 8
Sau:  = 4: 4 → 2 → 6
10
6
92
41 8
Sửa Đổi – Chèn
Tree-Insert(-,.)
1  = NIL
2  = -. //
3 while  ≠ NIL
4  = 
5 if ..  < . 
6  = . 
7 else  = . ℎ
8 .. +,	 = 
9 if  = NIL
10 -. // = .
11 elseif ..  < . 
12 .  = .
13 else . ℎ = .
11
6
92
41 8
7
Sửa Đổi – Xóa

 Xóa nút . khỏi cây - cây, 3 trường hợp

 . không có con

xóa .

 . chỉ có 1 con trái hoặc phải

chuyển con đó lên thay .

 . có cả con trái và phải

chuyển lớn nhất cây con trái hoặc nhỏ nhất cây
con phải (.′) lên thay .

xóa .′

 Lưu ý: khi xóa . nên giảm độ cao của cây -
nếu có thể
12
Dựng Cây TKNP

 Các thao tác chính trong thời gian 
(ℎ)

 Dựng cây TKNP có độ cao (ℎ) càng nhỏ càng tốt

 Dựng cây TKNP:

 Chèn liên tục khóa vào cây, bắt đầu từ cây rỗng

 Tại mỗi nút, cây con trái và phải cân bằng

Chọn khóa  nào cho nút .

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

 Chọn ngẫu nhiên khóa  chèn vào cây

Độ cao trung bình ℎ = 1(log 	)
13
Vấn Đề Khác

 Cần sửa Tree-Insert để
xử lý khóa trùng nhau trong
cây TKNP

 Cách 1: chọn ngẫu nhiên cây
con trái/phải

 Cách 2: dựa vào , để
chọn cây con trái/phải

 Cách 3: sử dụng danh sách
để lưu khóa trùng
14
Tree-Insert(-,.)
1  = NIL
2  = -. //
3 while  ≠ NIL
4  = 
5 if ..  < . 
6  = . 
7 else  = . ℎ
8 .. +,	 = 
9 if  = NIL
10 -. // = .
11 elseif ..  < . 
12 .  = .
13 else . ℎ = .
Cây TKNP Cân Bằng

 Độ cao của cây TKNP cần nhỏ để các thao tác
chính thực hiện nhanh

 Nếu cây TKNP “cân bằng” thực hiện các thao
tác trong 1(log 	)

 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)

 Sửa lại cấu trúc cây thông qua phép xoay

 Hai loại cây TKNP “cân bằng”

 Cây Đỏ - Đen

 Cây AVL
15
Cây Đỏ - Đen

 Mỗi nút cần thêm 1-bit màu

 Tính chất

 1. Mỗi nút là đỏ hoặc đen

 2. Gốc và lá (NIL) đen

 3. Nếu một nút đỏ, thì con của nó đen

 4. Mọi đường đi từ một nút đến các lá con có
cùng số lượng nút đen

 5. Không đường đi nào dài hơn gấp đôi
đường đi nào

 Độ cao của cây Đỏ - Đen với 	 nút
ℎ ≤ 2 log(	 + 	1)
16
Cây Đỏ - Đen – Ví Dụ
17
Cây Đỏ - Đen – Thao Tác

 Các thao tác chèn và xóa có thể làm thay
đổi tính chất của cây

 Do chính các thao tác này

 Đổi màu các nút

 Cấu trúc lại các kết nối nút

Phép xoay: đảm bảo thứ tự trong của khóa

Phép thực hiện trong thời gian 3(1)
18
Cây AVL

 Georgy Adelson-Velsky & Evgenil Landis 
đề xuất năm 1962

 Độ cao 2 cây của của một nút khác nhau
nhiều nhất 1

 Thời gian 3(log 	) cho các thao tác trong
cả 2 trường hợp trung bình & xấu nhất

 Cân bằng xây bằng phép xoay
19
Cây Treap

 Dựng cây TKNP ngẫu nhiên (slide 13) sẽ
được cây tương đối cân bằng

 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

 Cây Treap cung cấp giải pháp

 Là sự kết hợp của cây TKNP và cây thứ tự
bộ phận (min-heap)

 Khóa  thỏa mãn cây TKNP

Ưu tiên +/ thỏa mãn cây min-heap
20
Cây TKNP Cân Bằng – Phép Xoay

 Xem Mục 13.2 tr.312
21