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

Danh sách bỏ qua (Skip Lists) trong Cấu trúc dữ liệu

Trong danh sách bỏ qua (skip list), có thể tìm kiếm theo ngón (finger search) phần tử a từ nút chứa phần tử b bằng cách đơn giản tiếp tục tìm kiếm từ điểm a này.

Lưu ý nếu a < b, tìm kiếm tiến theo hướng lùi (backward), nếu a > b, tìm kiếm tiến theo hướng tiến (forward).

Trường hợp lùi đối xứng với tìm kiếm thông thường trong skip list, nhưng trường hợp tiến thực tế phức tạp hơn.

Thông thường, tìm kiếm trong skip list mong đợi nhanh vì sentinel (người gác) ở đầu danh sách được coi là nút cao nhất (tallest node).

Tuy nhiên, ngón của ta có thể gắn với nút chiều cao 1. Vì vậy, đôi khi ta phải leo lên khi tìm kiếm; điều này không bao giờ xảy ra trong trường hợp bình thường.

Các tính chất quan trọng nhất của skip list: cần không gian tuyến tính kỳ vọng, bao gồm O(log n) cấp độ kỳ vọng, hỗ trợ tìm kiếm trong O(log n) kỳ vọng, hỗ trợ chèn và xóa tại vị trí cho trước trong O(1) kỳ vọng.

Đã trình bày chi tiết các tính chất và mở rộng của skip list, bao gồm mã giả cho cách skip list hỗ trợ tìm kiếm ngón trong O(log d) kỳ vọng. Để hỗ trợ tìm kiếm ngón lùi, ngón tới nút V được lưu như cấu trúc dữ liệu ngón O(log n) không gian kỳ vọng, mà với mỗi cấp i lưu con trỏ tới nút bên trái của V nơi con trỏ cấp i hoặc trỏ tới V hoặc nút bên phải V. Di chuyển ngón cần cập nhật danh sách con trỏ này tương ứng.

Tìm kiếm ngón lùi thực hiện bằng cách trước xác định nút thấp nhất trong cấu trúc dữ liệu ngón ở bên trái khóa tìm kiếm y, nơi các nút trong cấu trúc ngón được xét theo thứ tự cấp tăng dần. Sau đó tìm kiếm tiến xuống từ nút đã xác định tương tự tìm kiếm skip list tiêu chuẩn.