Cây B trong cấu trúc dữ liệu: Tìm kiếm, chèn, xóa

Cây B là gì?

Cây B Cây B là một cấu trúc dữ liệu tự cân bằng dựa trên một tập hợp các quy tắc cụ thể để tìm kiếm, chèn và xóa dữ liệu một cách nhanh chóng và tiết kiệm bộ nhớ. Để đạt được điều này, các quy tắc sau được tuân thủ để tạo ra một cây B.

Cây B (B-Tree) là một loại cây đặc biệt trong cấu trúc dữ liệu. Phương pháp này được McCreight và Bayer giới thiệu lần đầu tiên vào năm 1972, và họ đặt tên cho nó là Cây tìm kiếm đa chiều cân bằng chiều cao (Height Balanced m-way Search Tree). Nó giúp bạn bảo toàn dữ liệu được sắp xếp và cho phép thực hiện nhiều thao tác như chèn, tìm kiếm và xóa trong thời gian ngắn hơn.

Quy tắc cho cây B

Dưới đây là những quy tắc quan trọng để tạo cây B:

• Tất cả các lá sẽ được tạo ở cùng cấp độ.
• Cây B được xác định bởi số bậc, còn được gọi là "thứ tự" (được chỉ định bởi một tác nhân bên ngoài, chẳng hạn như lập trình viên), được gọi là m trở đi. Giá trị của m phụ thuộc vào kích thước khối trên đĩa nơi chứa dữ liệu chủ yếu.
• Cây con bên trái của nút sẽ có giá trị nhỏ hơn bên phải của cây con. Điều này có nghĩa là các nút cũng được sắp xếp theo thứ tự tăng dần từ trái sang phải.
• Số lượng khóa tối đa mà một nút gốc, cũng như các nút con của nó, có thể chứa được tính bằng công thức sau: m − 1. Ví dụ:

  m = 4
  max keys: 4 − 1 = 3

• Mỗi nút, ngoại trừ nút gốc, phải chứa một số lượng khóa tối thiểu là [m/2] − 1. Ví dụ:

  m = 4
  min keys: 4/2 − 1 = 1

• Số nút con tối đa mà một nút có thể có bằng với bậc của nó, tức là m.
• Số lượng con tối thiểu mà một nút có thể có là một nửa đơn hàng, tức là m/2 (giá trị trần được lấy).
• Tất cả các khóa trong một nút được sắp xếp theo thứ tự tăng dần.

Tại sao nên sử dụng B-Tree

Dưới đây là những lý do nên sử dụng cây B:

• Giảm số lần đọc dữ liệu trên ổ đĩa.
• Cây B có thể dễ dàng được tối ưu hóa để điều chỉnh kích thước của nó (tức là số lượng nút con) sao cho phù hợp với dung lượng ổ đĩa.
• Đây là một kỹ thuật được thiết kế đặc biệt để xử lý một lượng lớn dữ liệu.
• Nó là một thuật toán hữu ích cho cơ sở dữ liệu và hệ thống tập tin.
• Đây là lựa chọn tốt khi cần đọc và ghi các khối dữ liệu lớn.

Lịch sử cây B

• Dữ liệu được lưu trữ trên đĩa theo từng khối. Khi dữ liệu này được đưa vào bộ nhớ chính (hoặc RAM), nó được gọi là cấu trúc dữ liệu.
• Đối với dữ liệu khổng lồ, việc tìm kiếm một bản ghi trên ổ đĩa yêu cầu phải đọc toàn bộ ổ đĩa; điều này làm tăng thời gian và mức tiêu thụ bộ nhớ chính do tần suất truy cập ổ đĩa cao và kích thước dữ liệu lớn.
• Để khắc phục điều này, các bảng chỉ mục được tạo ra để lưu trữ tham chiếu bản ghi dựa trên các khối mà chúng nằm trong đó. Điều này giúp giảm đáng kể thời gian và mức tiêu thụ bộ nhớ.
• Vì có dữ liệu khổng lồ nên chúng ta có thể tạo các bảng chỉ mục nhiều cấp.
• Có thể thiết kế chỉ mục đa cấp bằng cách sử dụng cây B để lưu trữ thông tin.ping Dữ liệu được sắp xếp theo cách tự cân bằng.

Tìm kiếm Operasản xuất

Thao tác tìm kiếm là thao tác đơn giản nhất trên cây B. Thuật toán sau được áp dụng:

• Giả sử khóa (giá trị) cần tìm kiếm là “k”.
• Bắt đầu tìm kiếm từ gốc và duyệt xuống dưới theo cách đệ quy.
• Nếu k nhỏ hơn giá trị gốc, hãy tìm kiếm trong cây con bên trái; nếu k lớn hơn giá trị gốc, hãy tìm kiếm trong cây con bên phải.
• Nếu nút có k tìm thấy, chỉ cần trả lại nút.
• Nếu k không được tìm thấy trong nút, hãy duyệt xuống nút con bằng khóa lớn hơn.
• Nếu không tìm thấy k trong cây, chúng ta trả về NULL.

Chèn Operasản xuất

Vì cây B là một cây tự cân bằng, bạn không thể ép buộc chèn một khóa vào bất kỳ nút nào. Thuật toán sau đây được áp dụng:

• Chạy thao tác tìm kiếm và tìm vị trí chèn thích hợp.
• Chèn khóa mới vào vị trí thích hợp, nhưng nếu nút đã có số lượng khóa tối đa:
• Nút cùng với khóa mới được chèn sẽ tách ra khỏi phần tử ở giữa.
• Phần tử ở giữa sẽ trở thành nút cha của hai nút con còn lại.
• Các nút phải sắp xếp lại các khóa theo thứ tự tăng dần.

Trong ví dụ trên:

• Tìm kiếm vị trí thích hợp trong nút đó để lấy khóa.
• Chèn khóa vào nút đích và kiểm tra các quy tắc.
• Sau khi chèn, nút đó có nhiều hơn hoặc bằng số lượng khóa tối thiểu là 1 không? Trong trường hợp này, câu trả lời là có. Hãy kiểm tra quy tắc tiếp theo.
• Sau khi chèn, nút đó có nhiều hơn số lượng khóa tối đa là 3 không? Trong trường hợp này, câu trả lời là không. Điều này có nghĩa là cây B không vi phạm bất kỳ quy tắc nào và quá trình chèn đã hoàn tất.

Trong ví dụ trên:

• Nút này đã đạt đến số lượng khóa tối đa.
• Nút sẽ tách ra, và khóa ở giữa sẽ trở thành nút gốc của hai nút còn lại.
• Trong trường hợp số lượng khóa là số chẵn, nút giữa sẽ được chọn bằng độ lệch trái hoặc độ lệch phải.

Trong ví dụ trên:

• Nút này có ít hơn số khóa tối đa.
• Số 1 được chèn cạnh số 3, nhưng quy tắc sắp xếp tăng dần bị vi phạm.
• Để khắc phục điều này, các khóa đã được sắp xếp lại.

Tương tự, 13 và 2 có thể dễ dàng được chèn vào nút vì chúng đáp ứng quy tắc "số lượng khóa ít hơn số khóa tối đa" cho các nút.

Trong ví dụ trên:

• Nút có các khóa bằng với các khóa tối đa.
• Khóa được chèn vào nút đích, nhưng nó vi phạm quy tắc về số lượng khóa tối đa.
• Nút mục tiêu được phân chia và khóa giữa theo độ lệch trái hiện là nút cha của các nút con mới.
• Các nút mới được sắp xếp theo thứ tự tăng dần.

Tương tự, dựa trên các quy tắc và trường hợp trên, các giá trị còn lại có thể được chèn dễ dàng vào Cây B.

Xóa bỏ Operasản xuất

Thao tác xóa có nhiều quy tắc hơn so với thao tác chèn và tìm kiếm. Thuật toán sau đây được áp dụng:

• Thực hiện thao tác tìm kiếm và tìm khóa mục tiêu trong các nút.
• Ba điều kiện được áp dụng dựa trên vị trí của khóa mục tiêu, như được giải thích trong các phần sau.

Nếu khóa mục tiêu nằm ở nút lá

• Target Nằm ở nút lá, nhiều hơn số khóa tối thiểu. Việc xóa nút này sẽ không vi phạm thuộc tính của cây B.
• Target Nó nằm ở nút lá và có số nút khóa tối thiểu. Việc xóa nó sẽ vi phạm thuộc tính của cây B.
• Nút đích có thể mượn khóa từ nút ngay bên trái hoặc nút ngay bên phải (nút anh em).
• Anh chị em sẽ nói Vâng nếu nó có nhiều hơn số lượng khóa tối thiểu.
• Khóa sẽ được mượn từ nút cha, giá trị lớn nhất sẽ được chuyển về nút cha, giá trị lớn nhất của nút cha sẽ được chuyển về nút đích, và giá trị đích sẽ bị xóa.
• Target nằm ở nút lá, nhưng không có nút anh em nào có số lượng khóa nhiều hơn số lượng khóa tối thiểu: tìm kiếm khóa, hợp nhất với các nút anh em và số lượng khóa tối thiểu của các nút cha, tổng số khóa bây giờ sẽ nhiều hơn số lượng khóa tối thiểu, và khóa mục tiêu sẽ được thay thế bằng số lượng khóa tối thiểu của một nút cha.

Nếu khóa mục tiêu nằm trong một nút bên trong

• Chọn một phần tử tiền nhiệm theo thứ tự hoặc một phần tử kế nhiệm theo thứ tự.
• Trong trường hợp có phần tử tiền nhiệm theo thứ tự trung tố, khóa lớn nhất từ ​​cây con bên trái của nó sẽ được chọn.
• Trong trường hợp phần tử kế tiếp được sắp xếp theo thứ tự trung tố, khóa nhỏ nhất từ ​​cây con bên phải của nó sẽ được chọn.
• Nếu phần tử tiền nhiệm theo thứ tự của khóa mục tiêu có số lượng khóa nhiều hơn số lượng khóa tối thiểu, thì chỉ khi đó nó mới có thể thay thế khóa mục tiêu bằng phần tử lớn nhất trong số các phần tử tiền nhiệm theo thứ tự.
• Nếu phần tử tiền nhiệm theo thứ tự của khóa mục tiêu không có nhiều hơn số lượng khóa tối thiểu, hãy tìm khóa tối thiểu của phần tử kế nhiệm theo thứ tự.
• Nếu cả khóa trước và khóa kế tiếp theo thứ tự của khóa mục tiêu đều có ít hơn khóa tối thiểu thì hãy hợp nhất khóa trước và khóa kế tiếp.

Nếu khóa mục tiêu nằm ở nút gốc

• Thay thế bằng phần tử lớn nhất của cây con tiền nhiệm theo thứ tự trung tố.
• Nếu sau khi xóa, nút đích có ít hơn số khóa tối thiểu, thì nút đích sẽ mượn giá trị tối đa từ nút anh em của nó thông qua nút cha của nút anh em đó.
• Giá trị lớn nhất của phần tử cha sẽ được phần tử đích lấy, nhưng với các nút có giá trị lớn nhất của phần tử anh em.

Bây giờ, hãy hiểu thao tác xóa bằng một ví dụ.

Sơ đồ trên hiển thị các trường hợp khác nhau của thao tác xóa trong cây B. Cây B này có bậc 5, nghĩa là số lượng nút con tối thiểu mà bất kỳ nút nào có thể có là 3, và số lượng nút con tối đa mà bất kỳ nút nào có thể có là 5. Trong khi đó, số lượng khóa tối thiểu và tối đa mà bất kỳ nút nào có thể có lần lượt là 2 và 4.

Trong ví dụ trên:

• Nút đích có khóa đích cần xóa.
• Nút mục tiêu có số khóa nhiều hơn số khóa tối thiểu.
• Chỉ cần xóa khóa đó đi.

Trong ví dụ trên:

• Nút mục tiêu có số khóa bằng với số khóa tối thiểu, vì vậy chúng ta không thể xóa trực tiếp nó vì điều đó sẽ vi phạm các điều kiện.

Bây giờ, sơ đồ sau đây giải thích cách xóa khóa này:

• Nút đích sẽ mượn khóa từ một nút anh em trực tiếp, trong trường hợp này là nút tiền nhiệm theo thứ tự trung tố (nút anh em bên trái), vì nó không có bất kỳ nút kế nhiệm theo thứ tự trung tố nào (nút anh em bên phải).
• Giá trị lớn nhất của nút tiền nhiệm theo thứ tự sẽ được chuyển đến nút cha, và nút cha sẽ chuyển giá trị lớn nhất đến nút đích (xem sơ đồ bên dưới).

Ví dụ sau đây minh họa cách xóa khóa cần có giá trị từ khóa kế nhiệm theo thứ tự của nó.

• Nút đích sẽ mượn một khóa từ một nút anh em trực tiếp, trong trường hợp này là nút kế tiếp theo thứ tự (nút anh em bên phải), bởi vì nút tiền nhiệm theo thứ tự của nó (nút anh em bên trái) có các khóa bằng với số khóa tối thiểu.
• Giá trị tối thiểu của nút kế thừa theo thứ tự sẽ được chuyển cho nút cha và nút cha sẽ chuyển giá trị tối đa cho nút mục tiêu.

Trong ví dụ bên dưới, nút đích không có bất kỳ nút anh em nào có thể cung cấp khóa của nó cho nút đích. Do đó, cần phải hợp nhất. Xem quy trình xóa khóa như vậy:

• Hợp nhất nút mục tiêu với bất kỳ nút anh em trực tiếp nào của nó cùng với khóa cha.
• Khóa từ nút cha nằm giữa hai nút đang hợp nhất được chọn.
• Xóa khóa mục tiêu khỏi nút đã hợp nhất.

Xóa bỏ OperaGiả thuyết Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Đầu ra: Phần tử lớn nhất bị xóa khỏi B-Tree.

Câu Hỏi Thường Gặp