Phức tạp về Thời gian

Phức tạp về thời gian (Time Complexity) là thước đo đánh giá hiệu suất của một thuật toán, cho biết số lượng thao tác cần thiết để thuật toán hoàn thành, thường được biểu diễn dưới dạng ký hiệu O lớn (Big O notation).

Vòng lặp giảm một nửa

Một số thuật toán có đặc điểm là kích thước dữ liệu hoặc phạm vi tìm kiếm giảm đi một nửa sau mỗi bước lặp. Ví dụ điển hình là thuật toán tìm kiếm nhị phân, nơi mỗi lần so sánh sẽ loại bỏ một nửa không gian tìm kiếm còn lại.

Cách đánh giá nhanh độ phức tạp thời gian

Để đánh giá nhanh độ phức tạp thời gian, chúng ta thường tập trung vào các yếu tố chính sau:

• Hằng số (O(1)): Các thao tác cơ bản, không phụ thuộc vào kích thước dữ liệu đầu vào.
• Logarit (O(log n)): Thuật toán giảm một nửa không gian tìm kiếm sau mỗi bước (ví dụ: tìm kiếm nhị phân).
• Tuyến tính (O(n)): Thuật toán duyệt qua toàn bộ dữ liệu một lần (ví dụ: tìm kiếm tuần tự).
• N log N (O(n log n)): Các thuật toán chia để trị hiệu quả (ví dụ: Merge Sort, Quick Sort).
• Bậc hai (O(n^2)): Các thuật toán có vòng lặp lồng nhau duyệt qua tất cả các cặp phần tử (ví dụ: Bubble Sort, Selection Sort).
• Mũ (O(2^n)): Các thuật toán thường liên quan đến đệ quy vét cạn không hiệu quả.

Phức tạp về Không gian

Phức tạp về không gian (Space Complexity) là thước đo lượng bộ nhớ mà một thuật toán sử dụng để hoàn thành tác vụ của nó. Nó bao gồm không gian được sử dụng cho đầu vào, đầu ra, cũng như không gian phụ trợ (auxiliary space) mà thuật toán cần trong quá trình thực thi.

Đệ quy – Bài toán Tháp Hà Nội

Bài toán Tháp Hà Nội là một ví dụ kinh điển về đệ quy, yêu cầu di chuyển một chồng đĩa từ cột này sang cột khác theo các quy tắc nhất định.

Tư duy giải quyết

Để giải bài toán Tháp Hà Nội với N đĩa từ cột A sang cột C, sử dụng cột B làm trung gian, chúng ta thực hiện theo các bước đệ quy sau:

1. Di chuyển N-1 đĩa từ cột A sang cột B, sử dụng cột C làm trung gian.
2. Di chuyển đĩa thứ N (đĩa lớn nhất) từ cột A sang cột C.
3. Di chuyển N-1 đĩa từ cột B sang cột C, sử dụng cột A làm trung gian.

Mã nguồn

buoc_di = 0

def thap_ha_noi(so_dia, cot_nguon, cot_trung_gian, cot_dich):
    """
    Giải bài toán Tháp Hà Nội bằng đệ quy.
    :param so_dia: Số lượng đĩa cần di chuyển.
    :param cot_nguon: Cột chứa các đĩa ban đầu.
    :param cot_trung_gian: Cột tạm thời.
    :param cot_dich: Cột đích.
    """
    global buoc_di
    if so_dia > 0:
        # 1. Di chuyển N-1 đĩa từ nguồn sang trung gian
        thap_ha_noi(so_dia - 1, cot_nguon, cot_dich, cot_trung_gian)
        
        # 2. Di chuyển đĩa lớn nhất từ nguồn sang đích
        buoc_di += 1
        # print(f"Di chuyển đĩa {so_dia} từ {cot_nguon} sang {cot_dich}")

        # 3. Di chuyển N-1 đĩa từ trung gian sang đích
        thap_ha_noi(so_dia - 1, cot_trung_gian, cot_nguon, cot_dich)

if __name__ == '__main__':
    thap_ha_noi(3, "Cột A", "Cột B", "Cột C")
    print(f"Tổng số bước di chuyển: {buoc_di}")

Tìm kiếm Tuần tự

Tìm kiếm tuần tự (Sequential Search) là phương pháp tìm kiếm đơn giản nhất, duyệt qua từng phần tử của danh sách từ đầu đến cuối cho đến khi tìm thấy phần tử mong muốn hoặc hết danh sách.

Độ phức tạp thời gian: O(n)

def tim_kiem_tuan_tu(danh_sach, gia_tri_tim):
    """
    Thực hiện tìm kiếm tuần tự trong một danh sách.
    :param danh_sach: Danh sách các phần tử.
    :param gia_tri_tim: Giá trị cần tìm.
    :return: Chỉ số của phần tử nếu tìm thấy, ngược lại trả về None.
    """
    for i, phan_tu in enumerate(danh_sach):
        if phan_tu == gia_tri_tim:
            return i
    return None

if __name__ == '__main__':
    ds_so = [1, 2, 3, 4, 5, 111, 222, 333, 8, 11, 22, 33, 9]
    print(f"Tìm 100 trong danh sách: {tim_kiem_tuan_tu(ds_so, 100)}") # None
    print(f"Tìm 222 trong danh sách: {tim_kiem_tuan_tu(ds_so, 222)}") # 6

Tìm kiếm Nhị phân

Tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm hiệu quả, hoạt động trên các danh sách đã được sắp xếp. Nó liên tục chia đôi không gian tìm kiếm cho đến khi tìm thấy phần tử hoặc xác định rằng phần tử không có trong danh sách.

Độ phức tạp thời gian: O(log n) do đặc tính chia đôi.

Điều kiện tiên quyết: Danh sách đầu vào phải được sắp xếp.

def tim_kiem_nhi_phan(danh_sach, gia_tri_tim, chi_so_trai, chi_so_phai):
    """
    Thực hiện tìm kiếm nhị phân đệ quy trong một danh sách đã sắp xếp.
    :param danh_sach: Danh sách các phần tử đã sắp xếp.
    :param gia_tri_tim: Giá trị cần tìm.
    :param chi_so_trai: Chỉ số biên trái của phạm vi tìm kiếm hiện tại.
    :param chi_so_phai: Chỉ số biên phải của phạm vi tìm kiếm hiện tại.
    :return: Chỉ số của phần tử nếu tìm thấy, ngược lại trả về None.
    """
    if chi_so_trai <= chi_so_phai: # Thay đổi điều kiện dừng để xử lý trường hợp chi_so_trai == chi_so_phai
        chi_so_giua = (chi_so_trai + chi_so_phai) // 2
        if danh_sach[chi_so_giua] == gia_tri_tim:
            return chi_so_giua
        elif danh_sach[chi_so_giua] > gia_tri_tim:
            return tim_kiem_nhi_phan(danh_sach, gia_tri_tim, chi_so_trai, chi_so_giua - 1)
        else: # danh_sach[chi_so_giua] < gia_tri_tim
            return tim_kiem_nhi_phan(danh_sach, gia_tri_tim, chi_so_giua + 1, chi_so_phai)
    else:
        return None

if __name__ == '__main__':
    ds_sap_xep = [1, 2, 3, 4, 5, 6, 7]
    gt_tim = 6
    idx_trai = 0
    idx_phai = len(ds_sap_xep) - 1 # Thay đổi để phù hợp với chỉ số mảng
    print(f"Tìm {gt_tim} trong danh sách: {tim_kiem_nhi_phan(ds_sap_xep, gt_tim, idx_trai, idx_phai)}") # 5
    print(f"Tìm 10 trong danh sách: {tim_kiem_nhi_phan(ds_sap_xep, 10, idx_trai, idx_phai)}") # None

Các Thuật toán Sắp xếp phổ biến

Có nhiều thuật toán sắp xếp khác nhau, mỗi loại có ưu và nhược điểm riêng về độ phức tạp thời gian và không gian. Một số thuật toán phổ biến bao gồm Sắp xếp nổi bọt (Bubble Sort), Sắp xếp chọn (Selection Sort), Sắp xếp chèn (Insertion Sort), Sắp xếp nhanh (Quick Sort), Sắp xếp trộn (Merge Sort) và Sắp xếp vun đống (Heap Sort).

Cây và Cây nhị phân

Cây

Cấu trúc dữ liệu cây (Tree) là một tập hợp các nút (node) được liên kết với nhau theo một cấu trúc phân cấp, không tuần hoàn. Các thuật ngữ cơ bản:

• Nút gốc (Root Node): Nút nằm ở cấp cao nhất của cây, không có nút cha. (Ví dụ: A)
• Nút lá (Leaf Node): Các nút không có nút con. (Ví dụ: B, C, H, K, L, M, N, P, Q)
• Độ sâu của cây (Tree Depth/Height): Số lượng cấp tối đa từ nút gốc đến nút lá sâu nhất. (Ví dụ: 4)
• Bậc của cây (Tree Degree): Bậc lớn nhất của bất kỳ nút nào trong cây. (Ví dụ: 6, nếu nút A có 6 nhánh con)
• Bậc của nút (Node Degree): Số lượng nút con trực tiếp của một nút. (Ví dụ: Nút F có bậc 3, Nút E có bậc 2)
• Nút cha (Parent Node): Nút có nút con trực tiếp. (Ví dụ: Nút D là cha của nút H)
• Nút con (Child Node): Nút được liên kết trực tiếp dưới một nút khác. (Ví dụ: Nút H là con của nút D)
• Cây con (Subtree): Một phần của cây bắt đầu từ một nút bất kỳ và bao gồm tất cả các nút con cháu của nó. (Ví dụ: cây con bắt đầu từ nút E bao gồm E, I, J, P, Q)

Cây nhị phân

Cây nhị phân (Binary Tree) là một loại cây mà mỗi nút có tối đa hai nút con, thường được gọi là con trái (left child) và con phải (right child).

Mã nguồn minh họa

class NutCayNhiPhan:
    def __init__(self, du_lieu):
        self.du_lieu = du_lieu
        self.con_trai = None  # Con trái của nút
        self.con_phai = None  # Con phải của nút

# Xây dựng một cây nhị phân đơn giản
nut_a = NutCayNhiPhan('A')
nut_b = NutCayNhiPhan('B')
nut_c = NutCayNhiPhan('C')
nut_d = NutCayNhiPhan('D')
nut_e = NutCayNhiPhan('E')
nut_f = NutCayNhiPhan('F')
nut_g = NutCayNhiPhan('G')
nut_h = NutCayNhiPhan('H')
nut_i = NutCayNhiPhan('I')

nut_a.con_phai = nut_c
nut_a.con_trai = nut_b
nut_b.con_phai = nut_e
nut_b.con_trai = nut_d
nut_d.con_phai = nut_g
nut_d.con_trai = nut_f
nut_g.con_phai = nut_i
nut_g.con_trai = nut_h # Sửa lỗi từ original, g.rchild = h sau g.rchild = i

goc_cay = nut_a
print(f"Dữ liệu con trái của con trái của A: {goc_cay.con_trai.con_trai.du_lieu}") # Output: F

Cây nhị phân đầy đủ và Cây nhị phân hoàn chỉnh

• Cây nhị phân đầy đủ (Full Binary Tree): Mỗi nút trong cây có 0 hoặc 2 nút con.
• Cây nhị phân hoàn chỉnh (Complete Binary Tree): Tất cả các cấp ngoại trừ cấp cuối cùng đều được điền đầy đủ, và các nút ở cấp cuối cùng được điền từ trái sang phải.

Duyệt cây nhị phân

Duyệt cây (Tree Traversal) là quá trình truy cập từng nút của cây một cách có hệ thống. Có bốn phương pháp duyệt chính:

from collections import deque

class NutCayNhiPhan:
    def __init__(self, du_lieu):
        self.du_lieu = du_lieu
        self.con_trai = None
        self.con_phai = None

# Xây dựng lại cây ví dụ
nut_a = NutCayNhiPhan('A')
nut_b = NutCayNhiPhan('B')
nut_c = NutCayNhiPhan('C')
nut_d = NutCayNhiPhan('D')
nut_e = NutCayNhiPhan('E')
nut_f = NutCayNhiPhan('F')
nut_g = NutCayNhiPhan('G')
nut_h = NutCayNhiPhan('H')
nut_i = NutCayNhiPhan('I')

nut_a.con_phai = nut_c
nut_a.con_trai = nut_b
nut_b.con_phai = nut_e
nut_b.con_trai = nut_d
nut_d.con_phai = nut_g
nut_d.con_trai = nut_f
nut_g.con_phai = nut_i
nut_g.con_trai = nut_h
goc_cay = nut_a

# Duyệt tiền thứ tự (Pre-order Traversal): Gốc -> Trái -> Phải (ABDFGHIEC)
def duyet_tien_thu_tu(nut_hien_tai):
    if nut_hien_tai:
        print(nut_hien_tai.du_lieu, end='') # Thăm nút gốc
        duyet_tien_thu_tu(nut_hien_tai.con_trai) # Đệ quy con trái
        duyet_tien_thu_tu(nut_hien_tai.con_phai) # Đệ quy con phải

# Duyệt trung thứ tự (In-order Traversal): Trái -> Gốc -> Phải (FDHGIBEAC)
def duyet_trung_thu_tu(nut_hien_tai):
    if nut_hien_tai:
        duyet_trung_thu_tu(nut_hien_tai.con_trai) # Đệ quy con trái
        print(nut_hien_tai.du_lieu, end='') # Thăm nút gốc
        duyet_trung_thu_tu(nut_hien_tai.con_phai) # Đệ quy con phải

# Duyệt hậu thứ tự (Post-order Traversal): Trái -> Phải -> Gốc (FHIGDEBCA)
def duyet_hau_thu_tu(nut_hien_tai):
    if nut_hien_tai:
        duyet_hau_thu_tu(nut_hien_tai.con_trai) # Đệ quy con trái
        duyet_hau_thu_tu(nut_hien_tai.con_phai) # Đệ quy con phải
        print(nut_hien_tai.du_lieu, end='') # Thăm nút gốc

# Duyệt theo cấp độ (Level-order Traversal): Từng cấp từ trái sang phải (ABCDEFGHI)
def duyet_theo_cap_do(nut_goc):
    if not nut_goc:
        return
    hang_doi = deque()
    hang_doi.append(nut_goc)
    while len(hang_doi) > 0:
        nut = hang_doi.popleft()
        print(nut.du_lieu, end='')
        if nut.con_trai:
            hang_doi.append(nut.con_trai)
        if nut.con_phai:
            hang_doi.append(nut.con_phai)

if __name__ == '__main__':
    print("Duyệt tiền thứ tự: ", end='')
    duyet_tien_thu_tu(goc_cay) # ABDFGHIEC
    print("\nDuyệt trung thứ tự: ", end='')
    duyet_trung_thu_tu(goc_cay) # FDHGIBEAC
    print("\nDuyệt hậu thứ tự: ", end='')
    duyet_hau_thu_tu(goc_cay) # FHIGDEBCA
    print("\nDuyệt theo cấp độ: ", end='')
    duyet_theo_cap_do(goc_cay) # ABCDEFGHI

Cây tìm kiếm nhị phân (BST)

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là một cây nhị phân có thêm thuộc tính: với mỗi nút, tất cả các nút trong cây con bên trái của nó đều có giá trị nhỏ hơn nút đó, và tất cả các nút trong cây con bên phải đều có giá trị lớn hơn nút đó. Điều này cho phép tìm kiếm, chèn và xóa phần tử hiệu quả.

Chèn, truy vấn và duyệt BST

class NutBST:
    def __init__(self, du_lieu):
        self.du_lieu = du_lieu
        self.con_trai = None
        self.con_phai = None
        self.cha = None # Tham chiếu đến nút cha

class CayTimKiemNhiPhan:
    def __init__(self, danh_sach_ban_dau=None):
        self.goc = None
        if danh_sach_ban_dau:
            for gia_tri in danh_sach_ban_dau:
                self.chen_khong_de_quy(gia_tri)

    # Chèn phần tử (đệ quy)
    def chen_de_quy_helper(self, nut_hien_tai, gia_tri_moi):
        if not nut_hien_tai:
            return NutBST(gia_tri_moi)
        elif gia_tri_moi < nut_hien_tai.du_lieu:
            nut_hien_tai.con_trai = self.chen_de_quy_helper(nut_hien_tai.con_trai, gia_tri_moi)
            nut_hien_tai.con_trai.cha = nut_hien_tai
        elif gia_tri_moi > nut_hien_tai.du_lieu:
            nut_hien_tai.con_phai = self.chen_de_quy_helper(nut_hien_tai.con_phai, gia_tri_moi)
            nut_hien_tai.con_phai.cha = nut_hien_tai
        # Nếu giá trị đã tồn tại (gia_tri_moi == nut_hien_tai.du_lieu), không làm gì cả
        return nut_hien_tai

    def chen_de_quy(self, gia_tri_moi):
        self.goc = self.chen_de_quy_helper(self.goc, gia_tri_moi)


    # Chèn phần tử (không đệ quy)
    def chen_khong_de_quy(self, gia_tri_moi):
        if not self.goc: # Cây rỗng
            self.goc = NutBST(gia_tri_moi)
            return

        nut_hien_tai = self.goc
        while True:
            if gia_tri_moi < nut_hien_tai.du_lieu:
                if nut_hien_tai.con_trai:
                    nut_hien_tai = nut_hien_tai.con_trai
                else: # Con trái không tồn tại, chèn vào đây
                    nut_hien_tai.con_trai = NutBST(gia_tri_moi)
                    nut_hien_tai.con_trai.cha = nut_hien_tai
                    return
            elif gia_tri_moi > nut_hien_tai.du_lieu:
                if nut_hien_tai.con_phai:
                    nut_hien_tai = nut_hien_tai.con_phai
                else: # Con phải không tồn tại, chèn vào đây
                    nut_hien_tai.con_phai = NutBST(gia_tri_moi)
                    nut_hien_tai.con_phai.cha = nut_hien_tai
                    return
            else: # Giá trị đã tồn tại
                return

    # Truy vấn phần tử (đệ quy)
    def truy_van_de_quy(self, nut_hien_tai, gia_tri_tim):
        if not nut_hien_tai:
            return None
        if nut_hien_tai.du_lieu < gia_tri_tim:
            return self.truy_van_de_quy(nut_hien_tai.con_phai, gia_tri_tim)
        elif nut_hien_tai.du_lieu > gia_tri_tim:
            return self.truy_van_de_quy(nut_hien_tai.con_trai, gia_tri_tim)
        else:
            return nut_hien_tai # Tìm thấy nút

    # Truy vấn phần tử (không đệ quy)
    def truy_van_khong_de_quy(self, gia_tri_tim):
        nut_hien_tai = self.goc
        while nut_hien_tai:
            if nut_hien_tai.du_lieu < gia_tri_tim:
                nut_hien_tai = nut_hien_tai.con_phai
            elif nut_hien_tai.du_lieu > gia_tri_tim:
                nut_hien_tai = nut_hien_tai.con_trai
            else:
                return nut_hien_tai # Tìm thấy nút
        return None

    # Duyệt tiền thứ tự
    def duyet_tien_thu_tu(self, nut_hien_tai):
        if nut_hien_tai:
            print(nut_hien_tai.du_lieu, end=' ')
            self.duyet_tien_thu_tu(nut_hien_tai.con_trai)
            self.duyet_tien_thu_tu(nut_hien_tai.con_phai)

    # Duyệt trung thứ tự (sẽ cho ra danh sách đã sắp xếp)
    def duyet_trung_thu_tu(self, nut_hien_tai):
        if nut_hien_tai:
            self.duyet_trung_thu_tu(nut_hien_tai.con_trai)
            print(nut_hien_tai.du_lieu, end=' ')
            self.duyet_trung_thu_tu(nut_hien_tai.con_phai)

    # Duyệt hậu thứ tự
    def duyet_hau_thu_tu(self, nut_hien_tai):
        if nut_hien_tai:
            self.duyet_hau_thu_tu(nut_hien_tai.con_trai)
            self.duyet_hau_thu_tu(nut_hien_tai.con_phai)
            print(nut_hien_tai.du_lieu, end=' ')


if __name__ == '__main__':
    cay_bst = CayTimKiemNhiPhan([4, 5, 6, 1, 2, 3, 7, 9, 8])
    
    tim_kiem_val = 3
    ket_qua_non_rec = cay_bst.truy_van_khong_de_quy(tim_kiem_val)
    print(f"Tìm kiếm không đệ quy giá trị {tim_kiem_val}: {ket_qua_non_rec.du_lieu if ket_qua_non_rec else 'Không tìm thấy'}")

    ket_qua_rec = cay_bst.truy_van_de_quy(cay_bst.goc, tim_kiem_val)
    print(f"Tìm kiếm đệ quy giá trị {tim_kiem_val}: {ket_qua_rec.du_lieu if ket_qua_rec else 'Không tìm thấy'}")

    print("\nCác phép duyệt:")
    print("Tiền thứ tự (Root-Left-Right): ", end='')
    cay_bst.duyet_tien_thu_tu(cay_bst.goc) # 4 1 2 3 5 6 7 9 8
    print("\nTrung thứ tự (Left-Root-Right - Sắp xếp): ", end='')
    cay_bst.duyet_trung_thu_tu(cay_bst.goc) # 1 2 3 4 5 6 7 8 9
    print("\nHậu thứ tự (Left-Right-Root): ", end='')
    cay_bst.duyet_hau_thu_tu(cay_bst.goc) # 3 2 1 8 9 7 6 5 4

Hiệu quả tìm kiếm của cây nhị phân

• Trường hợp trung bình: O(log n). Hiệu quả tương tự tìm kiếm nhị phân vì mỗi lần so sánh giúp loại bỏ một nửa số phần tử tiềm năng.
• Trường hợp xấu nhất: O(n). Xảy ra khi cây bị lệch hoàn toàn (ví dụ: chèn các phần tử đã sắp xếp theo thứ tự tăng dần hoặc giảm dần), biến cây thành một danh sách liên kết.

Để khắc phục trường hợp xấu nhất, các giải pháp bao gồm sử dụng cây cân bằng (như cây AVL hoặc Red-Black Tree) hoặc chèn các phần tử theo thứ tự ngẫu nhiên.

Cây AVL

Cây AVL (AVL Tree) là một loại cây tìm kiếm nhị phân tự cân bằng (self-balancing binary search tree). Đặc điểm chính của cây AVL là với mọi nút, chiều cao của cây con bên trái và cây con bên phải của nó chỉ được khác nhau tối đa là 1. Điều này đảm bảo hiệu suất tìm kiếm, chèn và xóa luôn ở mức O(log n).

Để duy trì thuộc tính cân bằng, cây AVL sử dụng các phép quay (rotations) khi có sự mất cân bằng xảy ra sau các thao tác chèn hoặc xóa.

• Chèn AVL - Quay trái (Left Rotation): Được thực hiện khi một nút bị mất cân bằng do cây con bên phải của con phải quá cao.
• Chèn AVL - Quay phải (Right Rotation): Được thực hiện khi một nút bị mất cân bằng do cây con bên trái của con trái quá cao.
• Chèn AVL - Quay phải-trái (Right-Left Rotation): Được thực hiện khi một nút bị mất cân bằng do cây con bên trái của con phải quá cao.
• Chèn AVL - Quay trái-phải (Left-Right Rotation): Được thực hiện khi một nút bị mất cân bằng do cây con bên phải của con trái quá cao.

Cây B

Cây B (B-Tree) là một cấu trúc dữ liệu cây tìm kiếm đa nhánh, tự cân bằng, được tối ưu hóa cho việc lưu trữ và truy xuất dữ liệu trên các thiết bị lưu trữ thứ cấp (như đĩa cứng), nơi chi phí truy cập ngẫu nhiên là rất cao. Cây B giúp giảm thiểu số lần đọc đĩa cần thiết.

Các đặc điểm chính của cây B:

1. Tất cả các khóa và dữ liệu được phân bố trong toàn bộ cây.
2. Tìm kiếm có thể kết thúc ở bất kỳ nút nào, không nhất thiết phải là nút lá. Hiệu quả tìm kiếm gần với tìm kiếm nhị phân.
3. Mỗi nút có thể có tối đa m (bậc của cây) nút con.
4. Nút gốc có ít nhất hai nút con (trừ khi nó là cây rỗng hoặc chỉ có một nút).
5. Các nút nhánh (không phải gốc và không phải lá) phải có ít nhất m/2 nút con.
6. Tất cả các nút lá đều nằm trên cùng một cấp độ.

Nhược điểm: Nếu dữ liệu liên kết với khóa (data) quá lớn và được lưu trữ trực tiếp trong các nút, thì mỗi nút sẽ chứa ít khóa hơn, dẫn đến chiều cao của cây tăng lên và số lần đọc đĩa cần thiết để tìm kiếm cũng tăng.

Cây B+

Cây B+ (B+ Tree) là một biến thể của cây B, được tối ưu hóa hơn nữa cho việc lưu trữ trên đĩa, đặc biệt phổ biến trong các hệ thống cơ sở dữ liệu và hệ thống tệp. Cây B+ kế thừa các ưu điểm của cây B và cải thiện khả năng quét tuần tự.

Các đặc điểm nổi bật của cây B+:

1. Tất cả các giá trị khóa (key) chỉ xuất hiện trong các nút bên trong (internal nodes), không chứa dữ liệu thực tế. Các nút nội bộ này chỉ chứa các con trỏ tới các nút con.
2. Tất cả dữ liệu thực tế (key và bản ghi dữ liệu) chỉ được lưu trữ trong các nút lá (leaf nodes).
3. Các nút lá được liên kết với nhau bằng con trỏ, tạo thành một danh sách liên kết, cho phép quét tuần tự toàn bộ dữ liệu một cách hiệu quả.
4. Mỗi nút có thể chứa nhiều khóa hơn so với cây B vì chúng không phải lưu trữ dữ liệu, dẫn đến chiều cao cây thấp hơn và ít lần truy cập đĩa hơn.

Đặc tính liên kết giữa các nút lá của B+ Tree rất phù hợp với đặc điểm đọc trước của đĩa (disk pre-reading), giúp tăng hiệu suất khi cần truy vấn dữ liệu theo dải hoặc quét toàn bộ bảng.

Cấu trúc dữ liệu index của MySQL

Hầu hết các hệ quản trị cơ sở dữ liệu quan hệ (RDBMS) như MySQL đều sử dụng cấu trúc cây B+ cho các chỉ mục (index) của mình.

B+ Tree trong InnoDB của MySQL

Cơ chế lưu trữ InnoDB trong MySQL sử dụng B+ Tree cho các chỉ mục theo cách đặc biệt:

1. Chỉ mục chính (Primary Key Index): InnoDB xây dựng một B+ Tree cho khóa chính (primary key). Trong B+ Tree này, các nút lá chứa toàn bộ bản ghi dữ liệu. Đây được gọi là chỉ mục cụm (clustered index). Nếu không có khóa chính được định nghĩa, InnoDB sẽ chọn một khóa DUY NHẤT không NULL làm khóa chính; nếu không có, nó sẽ tự động tạo một khóa ẩn 6 byte gọi là ROW_ID làm khóa chính.
2. Chỉ mục phụ (Secondary Index): Đối với các chỉ mục được tạo trên các cột khác không phải khóa chính, InnoDB cũng sử dụng B+ Tree. Tuy nhiên, các nút lá của B+ Tree này không chứa toàn bộ bản ghi dữ liệu mà chỉ chứa giá trị của cột được lập chỉ mục và giá trị của khóa chính tương ứng. Khi một truy vấn sử dụng chỉ mục phụ, sau khi tìm thấy khóa chính trong chỉ mục phụ, hệ thống phải thực hiện một thao tác tìm kiếm thứ hai trên chỉ mục chính để truy xuất toàn bộ bản ghi. Quá trình này được gọi là "Hồi bảng" (Covering Index / Index Lookup).

Việc hiểu rõ cách B+ Tree hoạt động trong InnoDB là rất quan trọng để tối ưu hóa hiệu suất truy vấn cơ sở dữ liệu.

Heap (Đống)

Heap (Đống) là một cấu trúc dữ liệu cây đặc biệt thỏa mãn tính chất heap: nếu P là nút cha của C, thì giá trị của P phải lớn hơn hoặc bằng (max-heap) hoặc nhỏ hơn hoặc bằng (min-heap) giá trị của C. Heap thường được cài đặt dưới dạng mảng để tận dụng tính chất liên tục của bộ nhớ.

Heap được ứng dụng rộng rãi trong các thuật toán sắp xếp (Heap Sort), hàng đợi ưu tiên (Priority Queue) và các thuật toán tìm đường đi ngắn nhất.

Stack – Bài toán Mê cung

Ngăn xếp (Stack) là một cấu trúc dữ liệu tuân theo nguyên tắc LIFO (Last In, First Out – vào sau ra trước). Ngăn xếp thường được sử dụng trong các bài toán tìm đường, như giải mê cung, để lưu trữ các con đường đã đi qua và quay lại khi gặp ngõ cụt.

me_cung = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 1, 1, 0, 0, 0, 1, 1],
    [1, 1, 0, 0, 0, 0, 1, 0, 1, 1],
    [1, 1, 0, 0, 1, 0, 1, 1, 1, 1],
    [1, 1, 1, 0, 1, 0, 1, 1, 1, 1],
    [1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
]

# Các hướng di chuyển: phải, xuống, trái, lên
huong_di_chuyen = [
    lambda x, y: (x, y + 1),  # Phải
    lambda x, y: (x + 1, y),  # Xuống
    lambda x, y: (x, y - 1),  # Trái
    lambda x, y: (x - 1, y),  # Lên
]

def tim_duong_me_cung(x_bat_dau, y_bat_dau, x_ket_thuc, y_ket_thuc):
    """
    Tìm đường trong mê cung sử dụng ngăn xếp.
    :param x_bat_dau: Tọa độ x của điểm bắt đầu.
    :param y_bat_dau: Tọa độ y của điểm bắt đầu.
    :param x_ket_thuc: Tọa độ x của điểm kết thúc.
    :param y_ket_thuc: Tọa độ y của điểm kết thúc.
    :return: In ra đường đi nếu tìm thấy, ngược lại thông báo không có đường.
    """
    duong_di_stack = []
    # Thêm điểm bắt đầu vào stack
    duong_di_stack.append((x_bat_dau, y_bat_dau))
    # Đánh dấu điểm bắt đầu đã đi qua
    temp_me_cung = [row[:] for row in me_cung] # Tạo bản sao để không ảnh hưởng mê cung gốc
    temp_me_cung[x_bat_dau][y_bat_dau] = 2 

    while duong_di_stack:
        vi_tri_hien_tai = duong_di_stack[-1] # Lấy vị trí hiện tại từ đỉnh stack

        # Nếu đã đến đích
        if vi_tri_hien_tai[0] == x_ket_thuc and vi_tri_hien_tai[1] == y_ket_thuc:
            print("Đường đi tìm thấy:")
            for p in duong_di_stack:
                print(p)
            return

        co_the_di_tiep = False
        for huong_func in huong_di_chuyen:
            x_tiep_theo, y_tiep_theo = huong_func(vi_tri_hien_tai[0], vi_tri_hien_tai[1])

            # Kiểm tra xem ô tiếp theo có hợp lệ và chưa đi qua không
            if (0 <= x_tiep_theo < len(temp_me_cung) and
                0 <= y_tiep_theo < len(temp_me_cung[0]) and
                temp_me_cung[x_tiep_theo][y_tiep_theo] == 0):
                
                duong_di_stack.append((x_tiep_theo, y_tiep_theo))
                temp_me_cung[x_tiep_theo][y_tiep_theo] = 2 # Đánh dấu đã đi qua
                co_the_di_tiep = True
                break # Di chuyển sang ô tiếp theo và tiếp tục vòng lặp chính

        if not co_the_di_tiep:
            # Nếu không tìm thấy đường đi tiếp, quay lại (pop khỏi stack)
            duong_di_stack.pop()

    print('Không có đường đi nào trong mê cung.')
    return False


if __name__ == '__main__':
    # (x1, y1) là (hàng, cột)
    # Maze đã cho có kích thước 9x10 (hàng x cột)
    # Start: (0, 1) - End: (7, 8)
    tim_duong_me_cung(0, 1, 7, 8)

Danh sách liên kết – Chèn đầu/Chèn đuôi

Danh sách liên kết (Linked List) là một cấu trúc dữ liệu tuyến tính, trong đó các phần tử không được lưu trữ ở các vị trí bộ nhớ liền kề. Mỗi phần tử (gọi là nút) chứa dữ liệu và một con trỏ (hoặc tham chiếu) đến nút tiếp theo trong chuỗi.

Chèn đầu (Head Insertion)

Chèn đầu là phương pháp thêm một nút mới vào đầu danh sách liên kết. Nút mới trở thành nút đầu tiên và con trỏ của nó sẽ trỏ đến nút mà trước đó là đầu danh sách.

Chèn đuôi (Tail Insertion)

Chèn đuôi là phương pháp thêm một nút mới vào cuối danh sách liên kết. Nút cuối cùng hiện tại sẽ trỏ đến nút mới, và nút mới trở thành nút cuối cùng.

class NutDon:
    def __init__(self, du_lieu):
        self.du_lieu = du_lieu
        self.tiep_theo = None # Con trỏ đến nút kế tiếp

# 1. Tạo danh sách liên kết bằng phương pháp chèn đầu
def tao_danh_sach_chen_dau(danh_sach_input):
    if not danh_sach_input:
        return None
    dau_ds = NutDon(danh_sach_input[0]) # Khởi tạo nút đầu tiên
    for du_lieu_moi in danh_sach_input[1:]:
        nut_moi = NutDon(du_lieu_moi) # Tạo nút mới
        nut_moi.tiep_theo = dau_ds  # Nút mới trỏ đến nút đầu hiện tại
        dau_ds = nut_moi             # Cập nhật nút đầu thành nút mới
    return dau_ds

# 2. Tạo danh sách liên kết bằng phương pháp chèn đuôi
def tao_danh_sach_chen_duoi(danh_sach_input):
    if not danh_sach_input:
        return None
    dau_ds = NutDon(danh_sach_input[0])
    duoi_ds = dau_ds # Giữ tham chiếu đến nút cuối cùng hiện tại
    for du_lieu_moi in danh_sach_input[1:]:
        nut_moi = NutDon(du_lieu_moi)
        duoi_ds.tiep_theo = nut_moi # Nút cuối cùng trỏ đến nút mới
        duoi_ds = nut_moi           # Cập nhật nút cuối thành nút mới
    return dau_ds

# Duyệt và in danh sách liên kết
def in_danh_sach_lien_ket(dau_ds):
    hien_tai = dau_ds
    while hien_tai:
        print(hien_tai.du_lieu, end=" -> ")
        hien_tai = hien_tai.tiep_theo
    print("None")

if __name__ == '__main__':
    cac_phan_tu = [10, 20, 30, 40]

    print("--- Chèn đầu ---")
    dau_ds_chen_dau = tao_danh_sach_chen_dau(cac_phan_tu)
    in_danh_sach_lien_ket(dau_ds_chen_dau) # Output: 40 -> 30 -> 20 -> 10 -> None
    print(f"Giá trị nút thứ 3 (từ đầu): {dau_ds_chen_dau.tiep_theo.tiep_theo.du_lieu}") # 20

    print("\n--- Chèn đuôi ---")
    dau_ds_chen_duoi = tao_danh_sach_chen_duoi(cac_phan_tu)
    in_danh_sach_lien_ket(dau_ds_chen_duoi) # Output: 10 -> 20 -> 30 -> 40 -> None
    print(f"Giá trị nút thứ 3 (từ đầu): {dau_ds_chen_duoi.tiep_theo.tiep_theo.du_lieu}") # 30

Chèn/Xóa nút trong danh sách liên kết đơn

Danh sách liên kết đơn (Singly Linked List) chỉ cho phép duyệt từ đầu đến cuối vì mỗi nút chỉ có con trỏ tiep_theo (next). Để chèn hoặc xóa, chúng ta cần tìm nút trước đó.

Chèn nút

Để chèn một nút mới vào sau một nút cụ thể, chúng ta cần cập nhật con trỏ tiep_theo của nút đó để trỏ đến nút mới, và con trỏ tiep_theo của nút mới sẽ trỏ đến nút mà trước đó được trỏ bởi nút cụ thể. Độ phức tạp O(1) nếu đã có tham chiếu đến nút trước đó.

Xóa nút

Để xóa một nút, chúng ta cần cập nhật con trỏ tiep_theo của nút trước đó để bỏ qua nút cần xóa và trỏ trực tiếp đến nút sau nút bị xóa. Độ phức tạp O(1) nếu đã có tham chiếu đến nút trước đó.

class NutDon:
    def __init__(self, du_lieu):
        self.du_lieu = du_lieu
        self.tiep_theo = None

def tao_danh_sach_lien_ket_tu_list(danh_sach_input):
    if not danh_sach_input:
        return None
    dau_ds = NutDon(danh_sach_input[0])
    duoi_ds = dau_ds
    for du_lieu_moi in danh_sach_input[1:]:
        nut_moi = NutDon(du_lieu_moi)
        duoi_ds.tiep_theo = nut_moi
        duoi_ds = nut_moi
    return dau_ds

def in_danh_sach_lien_ket(dau_ds):
    hien_tai = dau_ds
    while hien_tai:
        print(hien_tai.du_lieu, end=" -> ")
        hien_tai = hien_tai.tiep_theo
    print("None")

# Chèn một nút vào sau một nút đã cho (ví dụ: sau nút đầu tiên)
def chen_nut_sau(dau_ds, nut_truoc, du_lieu_moi):
    if not nut_truoc:
        print("Nút trước không thể là None.")
        return dau_ds
    
    nut_moi = NutDon(du_lieu_moi)
    nut_moi.tiep_theo = nut_truoc.tiep_theo
    nut_truoc.tiep_theo = nut_moi
    return dau_ds

# Xóa một nút sau một nút đã cho (ví dụ: xóa nút thứ hai)
def xoa_nut_sau(dau_ds, nut_truoc):
    if not nut_truoc or not nut_truoc.tiep_theo:
        print("Không thể xóa nút sau nút đã cho hoặc danh sách không đủ phần tử.")
        return dau_ds
    
    nut_can_xoa = nut_truoc.tiep_theo
    nut_truoc.tiep_theo = nut_can_xoa.tiep_theo
    del nut_can_xoa # Giải phóng bộ nhớ (tùy chọn trong Python do GC)
    return dau_ds


if __name__ == '__main__':
    phan_tu_goc = [1, 2, 3, 5]
    ds_lien_ket = tao_danh_sach_lien_ket_tu_list(phan_tu_goc)
    print("Danh sách gốc:")
    in_danh_sach_lien_ket(ds_lien_ket) # 1 -> 2 -> 3 -> 5 -> None

    # Chèn 4 sau nút có giá trị 3
    # Tìm nút có giá trị 3 (nút trước)
    nut_truoc_khi_chen = ds_lien_ket.tiep_theo.tiep_theo # Nút có giá trị 3
    ds_lien_ket = chen_nut_sau(ds_lien_ket, nut_truoc_khi_chen, 4)
    print("\nSau khi chèn 4 sau 3:")
    in_danh_sach_lien_ket(ds_lien_ket) # 1 -> 2 -> 3 -> 4 -> 5 -> None

    # Xóa nút sau nút có giá trị 2 (xóa nút có giá trị 3)
    # Tìm nút có giá trị 2 (nút trước)
    nut_truoc_khi_xoa = ds_lien_ket.tiep_theo # Nút có giá trị 2
    ds_lien_ket = xoa_nut_sau(ds_lien_ket, nut_truoc_khi_xoa)
    print("\nSau khi xóa nút sau 2 (xóa 3):")
    in_danh_sach_lien_ket(ds_lien_ket) # 1 -> 2 -> 4 -> 5 -> None

Danh sách liên kết đôi

Danh sách liên kết đôi (Doubly Linked List) là một cấu trúc dữ liệu tuyến tính trong đó mỗi nút không chỉ chứa dữ liệu và con trỏ đến nút kế tiếp (tiep_theo) mà còn chứa một con trỏ đến nút trước đó (truoc_do). Điều này cho phép duyệt danh sách theo cả hai chiều: tiến và lùi.

Tạo danh sách liên kết đôi

class NutDoi:
    def __init__(self, du_lieu):
        self.du_lieu = du_lieu
        self.tiep_theo = None # Con trỏ đến nút kế tiếp
        self.truoc_do = None  # Con trỏ đến nút trước đó


if __name__ == '__main__':
    nut_1 = NutDoi(10)
    nut_2 = NutDoi(20)
    nut_3 = NutDoi(30)

    nut_1.tiep_theo = nut_2
    nut_2.truoc_do = nut_1
    
    nut_2.tiep_theo = nut_3
    nut_3.truoc_do = nut_2

    # Truy cập từ nút 1 -> 2 -> 3, rồi quay lại 2
    print(f"Giá trị nút trước của nút kế tiếp của nút kế tiếp của nút 1: {nut_1.tiep_theo.tiep_theo.truoc_do.du_lieu}") # Output: 20

Chèn đầu/Chèn đuôi/Xóa/Chèn trong danh sách liên kết đôi

class NutDoi:
    def __init__(self, du_lieu):
        self.du_lieu = du_lieu
        self.tiep_theo = None
        self.truoc_do = None

# 1. Tạo danh sách liên kết đôi bằng phương pháp chèn đuôi
def tao_ds_doi_chen_duoi(danh_sach_input):
    if not danh_sach_input:
        return None
    
    dau_ds = NutDoi(danh_sach_input[0])
    hien_tai = dau_ds
    for du_lieu_moi in danh_sach_input[1:]:
        nut_moi = NutDoi(du_lieu_moi)
        nut_moi.truoc_do = hien_tai # Nút mới trỏ ngược về nút hiện tại
        hien_tai.tiep_theo = nut_moi # Nút hiện tại trỏ tới nút mới
        hien_tai = nut_moi           # Cập nhật nút hiện tại
    return dau_ds

# 2. Tạo danh sách liên kết đôi bằng phương pháp chèn đầu
def tao_ds_doi_chen_dau(danh_sach_input):
    if not danh_sach_input:
        return None
    
    dau_ds = NutDoi(danh_sach_input[0])
    for du_lieu_moi in danh_sach_input[1:]:
        nut_moi = NutDoi(du_lieu_moi)
        nut_moi.tiep_theo = dau_ds # Nút mới trỏ tới nút đầu hiện tại
        dau_ds.truoc_do = nut_moi  # Nút đầu hiện tại trỏ ngược về nút mới
        dau_ds = nut_moi           # Cập nhật nút đầu thành nút mới
    return dau_ds

# 3. Chèn một nút vào sau một nút đã cho trong danh sách liên kết đôi
def chen_nut_sau_ds_doi(dau_ds, nut_truoc, du_lieu_moi):
    if not nut_truoc:
        print("Nút trước không thể là None.")
        return dau_ds

    nut_moi = NutDoi(du_lieu_moi)
    nut_moi.tiep_theo = nut_truoc.tiep_theo
    if nut_truoc.tiep_theo: # Nếu nút trước không phải là cuối cùng
        nut_truoc.tiep_theo.truoc_do = nut_moi
    nut_moi.truoc_do = nut_truoc
    nut_truoc.tiep_theo = nut_moi
    return dau_ds

# 4. Xóa một nút đã cho (nếu có tham chiếu đến nút đó)
def xoa_nut_ds_doi(dau_ds, nut_can_xoa):
    if not nut_can_xoa:
        print("Nút cần xóa không thể là None.")
        return dau_ds

    if nut_can_xoa.truoc_do: # Nếu không phải nút đầu tiên
        nut_can_xoa.truoc_do.tiep_theo = nut_can_xoa.tiep_theo
    else: # Là nút đầu tiên
        dau_ds = nut_can_xoa.tiep_theo

    if nut_can_xoa.tiep_theo: # Nếu không phải nút cuối cùng
        nut_can_xoa.tiep_theo.truoc_do = nut_can_xoa.truoc_do
    
    del nut_can_xoa # Giải phóng bộ nhớ
    return dau_ds


# Duyệt và in danh sách liên kết
def in_ds_doi_lien_ket(dau_ds):
    hien_tai = dau_ds
    while hien_tai:
        print(hien_tai.du_lieu, end=" <-> ")
        hien_tai = hien_tai.tiep_theo
    print("None")


if __name__ == '__main__':
    cac_phan_tu = [1, 2, 3]

    print("--- Tạo DS đôi bằng chèn đuôi ---")
    ds_doi_duoi = tao_ds_doi_chen_duoi(cac_phan_tu)
    in_ds_doi_lien_ket(ds_doi_duoi) # 1 <-> 2 <-> 3 <-> None

    # Chèn 4 sau nút có giá trị 2
    nut_giua = ds_doi_duoi.tiep_theo # Nút có giá trị 2
    ds_doi_duoi = chen_nut_sau_ds_doi(ds_doi_duoi, nut_giua, 4)
    print("\nSau khi chèn 4 sau 2:")
    in_ds_doi_lien_ket(ds_doi_duoi) # 1 <-> 2 <-> 4 <-> 3 <-> None

    # Xóa nút có giá trị 4
    nut_xoa = ds_doi_duoi.tiep_theo.tiep_theo # Nút có giá trị 4
    ds_doi_duoi = xoa_nut_ds_doi(ds_doi_duoi, nut_xoa)
    print("\nSau khi xóa nút 4:")
    in_ds_doi_lien_ket(ds_doi_duoi) # 1 <-> 2 <-> 3 <-> None

    print("\n--- Tạo DS đôi bằng chèn đầu ---")
    ds_doi_dau = tao_ds_doi_chen_dau(cac_phan_tu)
    in_ds_doi_lien_ket(ds_doi_dau) # 3 <-> 2 <-> 1 <-> None

Tổng kết về Danh sách liên kết

Danh sách liên kết mang lại những lợi thế đáng kể so với mảng (hoặc danh sách tuần tự) trong một số tình huống nhất định.

• Ưu điểm:
  1. Chèn và xóa hiệu quả: Các thao tác chèn và xóa nút thường nhanh hơn đáng kể (O(1)) so với danh sách tuần tự, đặc biệt khi vị trí chèn/xóa đã được biết hoặc ở gần nút đầu/cuối.
  2. Phân bổ bộ nhớ linh hoạt: Các nút có thể được lưu trữ ở các vị trí bộ nhớ không liền kề, giúp sử dụng bộ nhớ linh hoạt và hiệu quả hơn, không cần cấp phát trước một khối bộ nhớ lớn.
• Nhược điểm:
  1. Truy cập ngẫu nhiên chậm: Không thể truy cập trực tiếp một phần tử bằng chỉ số (như list[i]), mà phải duyệt tuần tự từ đầu danh sách (O(n)).
  2. Tốn bộ nhớ hơn: Mỗi nút cần thêm không gian để lưu trữ con trỏ (hoặc nhiều con trỏ đối với danh sách liên kết đôi).

So sánh độ phức tạp của các thao tác cơ bản:

Thao tác	Danh sách liên kết	Mảng / Danh sách tuần tự
Tìm kiếm theo giá trị	O(n)	O(n)
Tìm kiếm theo chỉ số	O(n)	O(1)
Chèn sau một phần tử đã biết	O(1)	O(n)
Xóa một phần tử đã biết	O(1)	O(n)

Bảng băm

Bảng băm (Hash Table), hay còn gọi là bản đồ băm hoặc từ điển, là một cấu trúc dữ liệu cho phép lưu trữ và truy xuất dữ liệu một cách hiệu quả, thường với độ phức tạp thời gian trung bình là O(1). Nó hoạt động bằng cách sử dụng một hàm băm (hash function) để ánh xạ các khóa (key) đến các vị trí (chỉ số) trong một mảng.

Xung đột băm

Xung đột băm (Hash Collision) xảy ra khi hàm băm tạo ra cùng một giá trị chỉ số (hash value) cho hai hoặc nhiều khóa khác nhau. Đây là một vấn đề phổ biến và cần được xử lý để đảm bảo bảng băm hoạt động đúng.

Các phương pháp giải quyết xung đột băm:

• Địa chỉ mở (Open Addressing): Khi xảy ra xung đột, hệ thống tìm kiếm một vị trí trống khác trong bảng bằng cách thăm dò (probing) các vị trí tiếp theo theo một quy tắc nhất định (ví dụ: thăm dò tuyến tính, thăm dò bậc hai, băm kép).
• Chuỗi liên kết (Chaining): Mỗi vị trí trong mảng băm được liên kết với một danh sách liên kết (hoặc một cấu trúc dữ liệu khác như cây). Khi có xung đột, các khóa có cùng giá trị băm sẽ được thêm vào danh sách liên kết tại vị trí đó.

Bảng địa chỉ trực tiếp

Bảng địa chỉ trực tiếp (Direct Addressing Table) là một trường hợp đặc biệt của bảng băm mà không sử dụng hàm băm. Nó được dùng khi các khóa là các số nguyên nhỏ và liên tục, và có thể dùng trực tiếp làm chỉ số của mảng để lưu trữ dữ liệu.

Ưu và nhược điểm:

• Ưu điểm: Tìm kiếm, chèn, xóa đều có độ phức tạp O(1) trong mọi trường hợp.
• Nhược điểm:
  1. Tiêu tốn bộ nhớ: Khi tập hợp các khóa tiềm năng (tập hợp U) rất lớn nhưng số lượng khóa thực tế được sử dụng lại ít, thì phần lớn không gian bộ nhớ sẽ bị lãng phí.
  2. Giới hạn kiểu khóa: Chỉ hoạt động hiệu quả với các khóa là số nguyên hoặc có thể ánh xạ một cách đơn giản sang số nguyên.

Các hàm băm phổ biến

Hàm băm lý tưởng nên có các đặc tính như phân phối đều các khóa trên bảng băm và giảm thiểu xung đột. Có nhiều loại hàm băm khác nhau, từ các hàm băm đơn giản (phép chia, phép nhân) đến các hàm băm phức tạp hơn được thiết kế cho các mục đích cụ thể.

Ứng dụng bảng băm - Thuật toán MD5

MD5 (Message-Digest Algorithm 5) là một hàm băm mật mã (cryptographic hash function) tạo ra một giá trị băm 128 bit. Mặc dù MD5 có nhiều lỗ hổng bảo mật và không còn được khuyến nghị cho các mục đích bảo mật cao (như chứng thực chữ ký số), nó vẫn được sử dụng rộng rãi cho việc kiểm tra tính toàn vẹn dữ liệu (ví dụ: xác minh tải xuống tệp).

Ứng dụng bảng băm - Thuật toán SHA2

SHA2 (Secure Hash Algorithm 2) là một họ các hàm băm mật mã được thiết kế bởi NSA, bao gồm SHA-256, SHA-384, SHA-512, v.v. SHA2 tạo ra các giá trị băm dài hơn MD5 và được coi là an toàn hơn nhiều cho các ứng dụng mật mã, bao gồm bảo mật dữ liệu, chứng thực và chữ ký số.