Cây tìm kiếm nhị phân (BST) với ví dụ

Cây tìm kiếm nhị phân là gì?

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là một thuật toán tiên tiến được sử dụng để phân tích nút, các nhánh trái và phải của nó, được mô hình hóa theo cấu trúc cây, và trả về giá trị. BST được xây dựng trên kiến ​​trúc của thuật toán tìm kiếm nhị phân cơ bản; do đó, nó cho phép tìm kiếm, chèn và xóa nút nhanh hơn. Điều này làm cho chương trình thực sự nhanh và chính xác.

Thuộc tính của cây tìm kiếm nhị phân

BST được tạo thành từ nhiều nút và bao gồm các thuộc tính sau:

• Các nút của cây được biểu diễn dưới dạng mối quan hệ cha-con.
• Mỗi nút cha có thể không có nút con nào hoặc có tối đa hai nút con hoặc cây con ở bên trái và bên phải.
• Mỗi cây con, còn được gọi là cây tìm kiếm nhị phân, đều có các nhánh con ở bên phải và bên trái của chính chúng.
• Tất cả các nút được liên kết với các cặp khóa-giá trị.
• Các khóa của các nút nằm trên cây con bên trái nhỏ hơn các khóa của nút cha của chúng.
• Tương tự, khóa của các nút nằm trên cây con bên phải lớn hơn khóa của nút cha của chúng.

1. Có nút chính hoặc nút cha cấp 11. Bên dưới nó là các nút/nhánh bên trái và bên phải với các giá trị khóa riêng.
2. Nhánh cây con bên phải có các giá trị khóa lớn hơn nút cha.
3. Cây con bên trái có giá trị khóa nhỏ hơn nút cha.

Tại sao chúng ta cần Cây tìm kiếm nhị phân?

• Hai yếu tố chính khiến cây tìm kiếm nhị phân trở thành giải pháp tối ưu cho bất kỳ bài toán thực tế nào là Tốc độ và Độ chính xác.
• Do tìm kiếm nhị phân có định dạng giống nhánh với quan hệ cha-con, nên thuật toán biết các phần tử cần được tìm kiếm ở vị trí nào của cây. Điều này làm giảm số lượng so sánh khóa-giá trị mà chương trình phải thực hiện để xác định vị trí phần tử mong muốn.
• Ngoài ra, trong trường hợp phần tử cần tìm lớn hơn hoặc nhỏ hơn nút cha, nút sẽ biết cần tìm kiếm ở phía nào của cây. Lý do là cây con bên trái luôn có giá trị nhỏ hơn nút cha, và cây con bên phải luôn có giá trị bằng hoặc lớn hơn nút cha.
• BST thường được sử dụng để thực hiện tìm kiếm phức tạp, logic trò chơi mạnh mẽ, hoạt động tự động hoàn thành và đồ họa.
• Thuật toán hỗ trợ hiệu quả các hoạt động như tìm kiếm, chèn và xóa.

Các loại cây nhị phân

Ba loại cây nhị phân là:

• Cây nhị phân hoàn chỉnh: Tất cả các cấp trong cây đều đã đầy, có thể ngoại trừ cấp cuối cùng. Tương tự, tất cả các nút đều đã đầy, hướng về phía cực trái.
• Cây nhị phân đầy đủ: Tất cả các nút đều có 2 nút con, ngoại trừ nút lá.
• Cây nhị phân cân bằng hoặc hoàn hảo: Trong cây, tất cả các nút đều có hai nút con. Ngoài ra, mỗi nút con đều có cùng cấp độ.

Tìm hiểu thêm về Cây nhị phân trong cấu trúc dữ liệu nếu bạn quan tâm đến.

Cây tìm kiếm nhị phân hoạt động như thế nào?

Cây luôn có nút gốc và các nút con khác, dù ở bên trái hay bên phải. Thuật toán thực hiện tất cả các thao tác bằng cách so sánh các giá trị với nút gốc và các nút con tiếp theo của nó trong cây con bên trái hoặc bên phải tương ứng.

Tùy thuộc vào phần tử cần chèn, tìm kiếm hoặc xóa, sau khi so sánh, thuật toán có thể dễ dàng loại bỏ nhánh cây bên trái hoặc bên phải của nút gốc.

BST chủ yếu cung cấp ba loại hoạt động sau để bạn sử dụng:

• Tìm kiếm: Tìm kiếm phần tử từ cây nhị phân.
• Chèn: Thêm một phần tử vào cây nhị phân.
• Xóa bỏ: Xóa phần tử khỏi cây nhị phân.

Mỗi thao tác đều có cấu trúc và phương pháp thực hiện/phân tích riêng, nhưng phức tạp nhất là thao tác Xóa.

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

Luôn bắt đầu phân tích cây từ nút gốc, sau đó di chuyển tiếp sang nhánh con bên phải hoặc bên trái của nút gốc, tùy thuộc vào việc phần tử cần định vị nhỏ hơn hay lớn hơn nút gốc.

1. Phần tử cần tìm là 10.
2. So sánh phần tử với nút gốc 12, 10 < 12, do đó bạn chuyển sang cây con bên trái. Không cần phân tích cây con bên phải.
3. Bây giờ hãy so sánh 10 với nút 7, 10 > 7, vì vậy hãy chuyển sang cây con bên phải.
4. Sau đó so sánh 10 với nút tiếp theo, là 9, 10 > 9, hãy tìm trong nhánh con bên phải của cây con.
5. 10 khớp với giá trị trong nút, 10 = 10, trả về giá trị cho người dùng.

Biệt danh Code để tìm kiếm trong BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

Chèn Operasản xuất

Đây là một thao tác rất đơn giản. Đầu tiên, nút gốc được chèn vào, sau đó giá trị tiếp theo được so sánh với nút gốc. Nếu giá trị lớn hơn nút gốc, nó được thêm vào cây con bên phải, và nếu nó nhỏ hơn nút gốc, nó được thêm vào cây con bên trái.

1. Có một danh sách gồm 6 phần tử cần được chèn vào cây tìm kiếm nhị phân (BST) theo thứ tự từ trái sang phải.
2. Chèn 12 làm nút gốc và so sánh các giá trị tiếp theo là 7 và 9 để chèn tương ứng vào cây con bên phải và bên trái.
3. So sánh các giá trị còn lại 19, 5 và 10 với nút gốc 12 và đặt chúng vào vị trí thích hợp. Nếu 19 > 12, hãy đặt nó làm con phải của 12; nếu 5 < 12 và 5 < 7, hãy đặt nó làm con trái của 7. Bây giờ hãy so sánh 10, nếu 10 < 12, 10 > 7 và 10 > 9, hãy đặt 10 làm cây con bên phải của 9.

Mã giả để chèn nút vào BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Xóa bỏ Operations

Để xóa một nút khỏi cây tìm kiếm nhị phân (BST), có một số trường hợp, ví dụ như xóa nút gốc hoặc xóa nút lá. Ngoài ra, sau khi xóa nút gốc, chúng ta cần xem xét đến nút gốc tiếp theo.

Giả sử chúng ta muốn xóa một nút lá, chúng ta có thể chỉ cần xóa nó, nhưng nếu chúng ta muốn xóa một gốc, chúng ta cần thay thế giá trị của gốc bằng một nút khác. Hãy lấy ví dụ sau:

• Trường hợp 1 – Nút không có nút con: Đây là trường hợp đơn giản nhất, bạn chỉ cần xóa nút không có thêm nút con nào ở bên phải hoặc bên trái.
• Trường hợp 2 – Nút có một nút con: Sau khi xóa nút, chỉ cần kết nối nút con của nó với nút cha của giá trị đã bị xóa.
• Trường hợp 3 – Nút có hai nút con: Đây là tình huống khó khăn nhất, và nó hoạt động dựa trên hai quy tắc sau:
  • 3a – Phần tử tiền nhiệm theo thứ tự: Bạn cần xóa nút có hai nút con và thay thế nó bằng giá trị lớn nhất trong cây con bên trái của nút đã xóa.
  • 3b – Người kế nhiệm theo thứ tự: Bạn cần xóa nút có hai nút con và thay thế nó bằng giá trị nhỏ nhất trong cây con bên phải của nút đã xóa.

1. Đây là trường hợp xóa đầu tiên, trong đó bạn xóa một nút không có con. Như bạn có thể thấy trong sơ đồ, 19, 10 và 5 không có con. Nhưng chúng ta sẽ xóa 19.
2. Xóa giá trị 19 và xóa liên kết khỏi nút.
3. Xem cấu trúc mới của cây tìm kiếm nhị phân (BST) mà không có số 19.

1. Đây là trường hợp xóa thứ hai, trong đó bạn xóa một nút có 1 nút con. Như bạn có thể thấy trong sơ đồ, nút số 9 có một nút con.
2. Xóa nút 9 và thay thế nó bằng nút con 10, đồng thời thêm một liên kết từ 7 đến 10.
3. Xem cấu trúc mới của cây tìm kiếm nhị phân (BST) mà không có số 9.

1. Tại đây, bạn sẽ xóa nút 12 có hai nút con.
2. Việc xóa nút sẽ diễn ra dựa trên quy tắc tiền nhiệm theo thứ tự trung tố, có nghĩa là phần tử lớn nhất trong cây con bên trái của 12 phần tử sẽ thay thế nó.
3. Xóa nút 12 và thay thế bằng 10, vì đây là giá trị lớn nhất trên cây con bên trái.
4. Xem cấu trúc mới của cây tìm kiếm nhị phân (BST) sau khi xóa mục 12.

1. Xóa nút 12 có hai nút con.
2. Việc xóa nút sẽ diễn ra dựa trên quy tắc Kế thừa theo thứ tự trung tố, có nghĩa là phần tử nhỏ nhất trong cây con bên phải gồm 12 phần tử sẽ thay thế nó.
3. Xóa nút 12 và thay thế bằng nút 19, vì đây là giá trị nhỏ nhất trên cây con bên phải.
4. Xem cấu trúc mới của cây tìm kiếm nhị phân (BST) sau khi xóa mục 12.

Biệt danh Code Để xóa một nút

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Điều khoản quan trọng

• Chèn: Chèn một phần tử vào cây / tạo cây.
• Tìm kiếm: Tìm kiếm một phần tử trong cây.
• Đặt trước Traversal: Duyệt qua cây theo thứ tự trước.
• Giao dịch đặt hàng: Duyệt qua cây theo thứ tự hợp lệ.
• Duyệt theo thứ tự hậu tố: Duyệt qua cây theo thứ tự hậu kiểm.

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