Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Cây tìm kiếm ngón động (Dynamic Finger Search Trees) trong Cấu trúc dữ liệu

  • Cấu trúc dữ liệu tìm kiếm ngón động (dynamic finger search data structure) ngoài tìm kiếm ngón còn phải thực hiện chèn và xóa phần tử tại vị trí cho bởi ngón.
  • Cây tìm kiếm ngón (Finger search trees) là biến thể của B-tree hỗ trợ tìm kiếm ngón O(log d) và cập nhật O(1), giả định chỉ duy trì O(1) ngón di động (moveable fingers).
  • Duyệt ngón d vị trí tốn O(log d) thời gian.
  • Các cấu trúc cây tìm kiếm ngón (tức AVL, red-black trees) hoặc chỉ xét số ngón hằng số hoặc chỉ hỗ trợ cập nhật thời gian khấu hao hằng số.
  • Các cấu trúc hỗ trợ số ngón tùy ý và cập nhật trường hợp xấu O(1) đã được tạo ra.
  • Một cây tìm kiếm hỗ trợ cập nhật tại vị trí tùy ý trong O(1) trường hợp xấu, nhưng chỉ hỗ trợ tìm kiếm O(log n).
  • Các cấu trúc hỗ trợ tìm kiếm O(log d) và chèn/xóa O(log d n).
  • Cây tìm kiếm ngón tiêu tốn chèn O(1) trường hợp xấu và xóa O(log d n).
  • Theo giải pháp thay thế tiết kiệm không gian cho level linked (2,4)-trees, cho phép một ngón đơn, có thể di chuyển cùng chi phí hiệu năng như (2,4)-trees. Trong giải pháp không cần level links và con trỏ cha, thay vào đó cấu trúc dữ liệu đặc biệt O(log n) không gian, gọi là "hand", được tạo cho ngón để cho phép ngón được duyệt hiệu quả.
  • Cây Splay được định nghĩa là lớp cây tìm kiếm nhị phân tự điều chỉnh (self-adjusting) hỗ trợ tìm kiếm, chèn, xóa trong O(log n) khấu hao. Cây Splay có thể cài đặt như cây tìm kiếm ngón hiệu quả.
  • Cho chi phí khởi tạo O(n), chi phí khấu hao truy cập ở khoảng cách d từ truy cập trước trong cây splay là O(log d) nơi truy cập bao gồm tìm kiếm, chèn, xóa.
  • Lưu ý tuyên bố chỉ áp dụng khi có một ngón, luôn trỏ đến phần tử truy cập cuối cùng.
  • Tất cả các cấu trúc trên có thể áp dụng trên máy con trỏ (pointer machine) nơi phép toán duy nhất cho phép trên phần tử là so sánh hai phần tử.
  • Đối với mô hình máy truy cập ngẫu nhiên (RAM - Random Access Machine), cây tìm kiếm ngón được phát triển với cập nhật thời gian hằng số và tìm kiếm O(log d). Kết quả này đạt được bằng cách bảng tra cứu (tabulating) các cấu trúc cây nhỏ, nhưng chỉ thực hiện so sánh phần tử.