Cấu trúc dữ liệu n phần tử với các thao tác O(1)

Chúng ta sẽ xem một cấu trúc dữ liệu chứa n phần tử (từ 0 đến n-1) với các thao tác chèn, xóa, tìm kiếm đều có độ phức tạp O(1) - thời gian hằng số.

Giải pháp: Sử dụng mảng Boolean để đánh dấu sự hiện diện của phần tử tại vị trí i. Nếu phần tử tồn tại thì giá trị 1, ngược lại là 0.

Thuật toán

Khởi tạo (initialization)

begin
    điền 0 cho tất cả phần tử mảng Boolean
end

Chèn (insert)

begin
    gán phần tử tại chỉ số i = 1 (true)
end

Xóa (delete)

begin
    gán phần tử tại chỉ số i = 0 (false)
end

Tìm kiếm (search)

begin
    trả về giá trị tại vị trí i
end

Ví dụ code

// Khởi tạo
void init(int n) {
    bool dataStructure[n];
    for (int i = 0; i < n; i++)
        dataStructure[i] = 0;
}

// Chèn
void insert(unsigned i) {
    dataStructure[i] = 1;
}

// Xóa
void delete(unsigned i) {
    dataStructure[i] = 0;
}

// Tìm kiếm
bool search(unsigned i) {
    return dataStructure[i];
}