Tìm Hiểu Về Cấu Trúc Dữ Liệu Cây Tìm Kiếm Ưu Tiên (PST)

Tram Ho

Giới thiệu

Trong khoa học máy tính, cây tìm kiếm ưu tiên (priority search trees) là một cấu trúc dữ liệu dạng cây để lưu trữ các điểm trong không gian hai chiều (Oxy). Ban đầu cây tìm kiếm ưu tiên được giới thiệu bởi Edward McCreight năm 1985. Ban đầu cây tìm kiếm ưu tiên là sự mở rộng của hàng đợi ưu tiên (priority queue) với mục đích cải thiện thời gian tìm kiếm từ: O(n)O(n)O(n) đến OOO (sss + lognlog nlogn ) trong đó n là số điểm trong cây và s là số trong tổng số điểm được trả về bởi tìm kiếm. Sau đó, cây tìm kiếm ưu tiên được sử dụng để lưu trữ một tập hợp các điểm 2 chiều được sắp xếp theo mức độ ưu tiên(priority) và theo một giá trị khóa (key value). Điều này được thực hiện bằng cách tạo kết hợp giữa hàng đợi ưu tiên (priority queue)cây tìm kiếm nhị phân (binary search tree). Kết quả là một cây trong đó mỗi nút đại diện cho một điểm trong tập dữ liệu gốc. Điểm được chứa bởi nút là điểm có mức độ ưu tiên thấp nhất. Ngoài ra, mỗi nút còn chứa một giá trị khóa dùng để chia các điểm còn lại (thường là trung vị của các khóa, không kể điểm của nút) thành cây con trái và phải. Các điểm được chia bằng cách so sánh các giá trị khóa của chúng với khóa nút, ủy nhiệm các giá trị có khóa thấp hơn cho cây con bên trái và các giá trị lớn hơn cho cây con bên phải.

Hình 1: Ví dụ về cây tìm kiếm ưu tiên:
1

Cách xây dựng cây PST

Cây tìm kiếm ưu tiên là một cấu trúc dữ liệu lưu trữ các điểm trên không gian 2 chiều. Đầu tiên, chúng ta xem xét n các điểm trên cùng một mặt phẳng, mỗi điểm đều có tọa độ x và tọa độ y biểu diễn trên hình 2. Bài toán xây dựng cây tìm kiếm ưu tiên được mô tả như sau:
Đầu vào: Ta có n điểm thuộc mặt phẳng SSS = { pip_{i}pii=1,2,3…ni=1,2,3…ni=1,2,3n } và các điểm pi(pi.x,pi.y)p_i (p_i.x, p_i.y)pi(pi.x,pi.y).
Đầu ra: Cây tìm kiếm ưu tiên lưu trữ các điểm trong không gian 2 chiều.

Trình tự:

  1. Nếu S = NULL thì trả về NULL.
  2. Tìm điểm pip_{i}pi có tọa độ y là nhỏ nhất đặt làm root (gốc), pip_{i}pi = min ⁡{ pip_{i}pi.y ∊S }
  3. Tìm đường trung tuyến (median) chia đôi các điểm về 2 phía trái và phải. Ở phía bên trái tìm điểm pip_{i}pi = min⁡ { pip_{i}pi.y ∊ SlS_lSl {pparentp_{parent}pparent} } gán làm con của nút cha ở bước 2, thực hiện tương tự với phía bên phải xem hình 3.
  4. Đệ quy lại PST(s) với phía bên trái.
  5. Đệ quy lại PST(s) với phái bên phải.
  6. Kết thúc.

Hình 2: Biểu diễn các điểm trên mặt phẳng Oxy

Hình 3: Mô tả xác dựng cây PST

Mã giải được viết bằng pascal:

Thêm nút mới vào cây

Kế tiếp, cũng đến với vấn đề thêm một nút mới vào cây. Giả sử có một nút mới với tọa độ xnewx_{new}xnewynewy_{new}ynew cần phải thêm vào cây. Như vậy sẽ cần tính toán lại xem có sự thay đổi ở gốc cây (root) và các đường trung tuyến (median). Sau đó sẽ so sánh xem nút mới có thể chèn vào gốc cây hoặc là các nút ở phía bên trái, phải.

Mã giải pascal thêm nút mới vào cây:

Xóa nút ở trên cây

Kế tiếp, cũng đến với vấn đề thêm một nút mới vào cây. Giả sử có một nút cũ với tọa độ xoldx_{old}xoldyoldy_{old}yold cần phải xóa khỏi cây. Như vậy sẽ cần tính toán lại xem có sự thay đổi ở gốc cây, các nút cha, các đường trung tuyến (median) và cập nhập lại cây.

Mã giải pascal xóa một nút ở trên cây:

Truy vấn các điểm trên cây

Tiếp theo, hãy xem xét vấn đề tìm kiếm trên cây. Cây tìm kiếm ưu tiên có thể giúp tìm kiếm các điểm thỏa mãn các điều kiện trên mặt phẳng Oxy, điều đó khác so với cây tìm kiếm nhị phân (BST) là chỉ tìm kiếm 1 điểm trên cây. Khi tìm kiếm ta cần xác định được phạm vi tìm kiếm dưới dạng hình chữ nhật có giới hạn xminx_{min}xminxmaxx_{max}xmax và độ ưu tiên y. Trong hình dưới đây hãy xem xét vấn đề tìm kiếm các điểm trên cây tìm kiếm ưu tiên với ymaxy_{max}ymax làm gốc.

Hình 4: Mô tả phạm vi tìm kiếm

Hình 5: Mô tả phương pháp tìm kiếm

Mã giải pascal thuật toán tìm kiếm:

Thuật toán triển khai với Python:

Bài toán tìm kiếm điểm có y nhỏ nhất

Bài toán đưa ra vấn đề đó là tìm kiếm một điểm có tọa độ y nhỏ nhất trong một phạm vi hình chữ nhật cho trước trên mặt phẳng Oxy. Bằng mắt thường có thể thấy ngay điểm cần tìm trong phạm vị với số lượng ít các điểm trên mặt phẳng. Nếu tìm tuần tự so sánh từng điểm với nhau thì độ phức tạp của thuật toán sẽ là O(n)O(n)O(n). Vì thế ta sử dụng cấu trúc dữ liệu cây tìm kiếm ưu tiên để thực hiện việc tìm kiếm với độ phức tạp từ
O(n)O(n)O(n) đến OOO (sss + lognlog nlogn ).

Mã giải thuật toán:

Bài toán tìm điểm có x lớn nhất

Bài toán đưa ra vấn đề đó là tìm kiếm một điểm có tọa độ x lớn nhất trong một phạm vi hình chữ nhật cho trước trên mặt phẳng Oxy. Bằng mắt thường có thể thấy ngay điểm cần tìm trong phạm vị với số lượng ít các điểm trên mặt phẳng. Nếu tìm tuần tự so sánh từng điểm với nhau thì độ phức tạp của thuật toán sẽ là O(n)O(n)O(n). Vì thế ta sử dụng cấu trúc dữ liệu cây tìm kiếm ưu tiên để thực hiện việc tìm kiếm với độ phức tạp từ
O(n)O(n)O(n) đến OOO (sss + lognlog nlogn ).

Mã giải thuật toán:

Tải về mã nguồn

Xem toàn bộ source code bằng python tại github

Tham khảo

[1] McCreight, Edward (May 1985). “Priority search trees”. SIAM Journal on Scientific Computing.

[2] D.T. Lee. “Interval, Range, and Priority Search Tree”. Academia Sinica.

[3] Dina Q Goldin Karon (March 8, 1993). “Priority Search Tree”. Computational Geometry.

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo