Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 7: 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