DAA - Cây tìm kiếm nhị phân chi phí tối ưu
Cây tìm kiếm nhị phân (BST) là cây nơi các giá trị khóa được lưu trữ trong các nút bên trong. Các nút bên ngoài là các nút rỗng. Các khóa được sắp xếp theo thứ tự từ vựng, nghĩa là đối với mỗi nút bên trong, tất cả các khóa trong cây con bên trái nhỏ hơn các khóa trong nút và tất cả các khóa trong cây con bên phải lớn hơn.
Khi chúng ta biết tần suất tìm kiếm từng khóa, sẽ khá dễ dàng để tính toán chi phí dự kiến của việc truy cập từng nút trong cây. Cây tìm kiếm nhị phân tối ưu là một BST có chi phí định vị mỗi nút dự kiến tối thiểu
Thời gian tìm kiếm của một phần tử trong BST là O(n), trong khi trong thời gian tìm kiếm Balanced-BST là O(log n). Một lần nữa, thời gian tìm kiếm có thể được cải thiện trong Cây Tìm kiếm Nhị phân Chi phí Tối ưu, đặt dữ liệu được sử dụng thường xuyên nhất trong phần tử gốc và gần phần tử gốc hơn, trong khi đặt dữ liệu ít được sử dụng nhất gần các lá và trong các lá.
Ở đây, thuật toán cây tìm kiếm nhị phân tối ưu được trình bày. Đầu tiên, chúng tôi xây dựng một BST từ một tập hợp cácn số lượng khóa riêng biệt < k1, k2, k3, ... kn >. Ở đây chúng tôi giả định, xác suất truy cập một khóaKi Là pi. Một số phím giả (d0, d1, d2, ... dn) được thêm vào vì một số tìm kiếm có thể được thực hiện cho các giá trị không có trong Bộ khóa K. Chúng tôi giả định, đối với mỗi khóa giảdi xác suất truy cập là qi.
Optimal-Binary-Search-Tree(p, q, n)
e[1…n + 1, 0…n],
w[1…n + 1, 0…n],
root[1…n + 1, 0…n]
for i = 1 to n + 1 do
e[i, i - 1] := qi - 1
w[i, i - 1] := qi - 1
for l = 1 to n do
for i = 1 to n – l + 1 do
j = i + l – 1 e[i, j] := ∞
w[i, i] := w[i, i -1] + pj + qj
for r = i to j do
t := e[i, r - 1] + e[r + 1, j] + w[i, j]
if t < e[i, j]
e[i, j] := t
root[i, j] := r
return e and rootPhân tích
Thuật toán yêu cầu O (n3) thời gian, kể từ khi ba lồng vào nhau forvòng lặp được sử dụng. Mỗi vòng lặp này đảm nhiệm tối đan các giá trị.
Thí dụ
Xem xét cây sau, chi phí là 2,80, mặc dù đây không phải là kết quả tối ưu.
| Nút | Chiều sâu | Xác suất | Sự đóng góp |
|---|---|---|---|
| k 1 | 1 | 0,15 | 0,30 |
| k 2 | 0 | 0,10 | 0,10 |
| k 3 | 2 | 0,05 | 0,15 |
| k 4 | 1 | 0,10 | 0,20 |
| k 5 | 2 | 0,20 | 0,60 |
| d 0 | 2 | 0,05 | 0,15 |
| d 1 | 2 | 0,10 | 0,30 |
| d 2 | 3 | 0,05 | 0,20 |
| d 3 | 3 | 0,05 | 0,20 |
| d 4 | 3 | 0,05 | 0,20 |
| d 5 | 3 | 0,10 | 0,40 |
| Total | 2,80 |
Để có được một giải pháp tối ưu, sử dụng thuật toán được thảo luận trong chương này, các bảng sau được tạo.
Trong các bảng sau, chỉ mục cột là i và chỉ số hàng là j.
| e | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 5 | 2,75 | 2,00 | 1,30 | 0,90 | 0,50 | 0,10 |
| 4 | 1,75 | 1,20 | 0,60 | 0,30 | 0,05 | |
| 3 | 1,25 | 0,70 | 0,25 | 0,05 | ||
| 2 | 0,90 | 0,40 | 0,05 | |||
| 1 | 0,45 | 0,10 | ||||
| 0 | 0,05 |
| w | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 5 | 1,00 | 0,80 | 0,60 | 0,50 | 0,35 | 0,10 |
| 4 | 0,70 | 0,50 | 0,30 | 0,20 | 0,05 | |
| 3 | 0,55 | 0,35 | 0,15 | 0,05 | ||
| 2 | 0,45 | 0,25 | 0,05 | |||
| 1 | 0,30 | 0,10 | ||||
| 0 | 0,05 |
| nguồn gốc | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 5 | 2 | 4 | 5 | 5 | 5 |
| 4 | 2 | 2 | 4 | 4 | |
| 3 | 2 | 2 | 3 | ||
| 2 | 1 | 2 | |||
| 1 | 1 |
Từ các bảng này, cây tối ưu có thể được hình thành.