Cây tìm kiếm nhị phân DSA

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

Cây tìm kiếm nhị phân (BST) là một loại cấu trúc dữ liệu Cây nhị phân , trong đó các thuộc tính sau phải đúng với bất kỳ nút "X" nào trong cây:

• Nút con bên trái của nút X và tất cả các nút con cháu của nó (con, nút con, v.v.) có giá trị thấp hơn giá trị của X.
• Con bên phải và tất cả con cháu của nó có giá trị cao hơn giá trị của X.
• Cây con trái và phải cũng phải là Cây tìm kiếm nhị phân.

Các thuộc tính này giúp tìm kiếm, thêm và xóa các giá trị nhanh hơn cây nhị phân thông thường.

Để làm cho điều này dễ hiểu và dễ thực hiện nhất có thể, hãy giả sử rằng tất cả các giá trị trong Cây tìm kiếm nhị phân là duy nhất.

Sử dụng Cây tìm kiếm nhị phân bên dưới để hiểu rõ hơn về các khái niệm này và thuật ngữ liên quan.

Kích thước của cây là số nút trong đó (\(n\)).

Cây con bắt đầu bằng một trong các nút trong cây làm gốc cục bộ và bao gồm nút đó và tất cả các nút con của nó.

Con cháu của một nút là tất cả các nút con của nút đó và tất cả các nút con của chúng, v.v. Chỉ cần bắt đầu với một nút và con cháu sẽ là tất cả các nút được kết nối bên dưới nút đó.

Chiều cao của nút là số cạnh tối đa giữa nút đó và nút lá.

Nút kế tiếp theo thứ tự của nút là nút xuất hiện sau nút đó nếu chúng ta thực hiện truyền tải theo thứ tự. Việc truyền tải BST theo thứ tự ở trên sẽ dẫn đến nút 13 đến trước nút 14 và do đó, nút kế thừa của nút 13 là nút 14.

Truyền tải cây tìm kiếm nhị phân

Chỉ để xác nhận rằng chúng tôi thực sự có cấu trúc dữ liệu Cây tìm kiếm nhị phân trước mặt, chúng tôi có thể kiểm tra xem các thuộc tính ở đầu trang này có đúng hay không. Vì vậy, đối với mỗi nút trong hình trên, hãy kiểm tra xem tất cả các giá trị ở bên trái của nút có thấp hơn và tất cả các giá trị ở bên phải có cao hơn không.

Một cách khác để kiểm tra xem Cây nhị phân có phải là BST hay không là thực hiện duyệt theo thứ tự (như chúng tôi đã làm ở trang trước) và kiểm tra xem danh sách giá trị kết quả có theo thứ tự tăng dần hay không.

Mã bên dưới là cách triển khai Cây tìm kiếm nhị phân trong hình trên, với tính năng truyền tải.

 class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)

root.left = node7
root.right = node15

node7.left = node3
node7.right = node8

node15.left = node14
node15.right = node19

node19.left = node18

# Traverse
inOrderTraversal(root)

Như chúng ta có thể thấy bằng cách chạy ví dụ mã ở trên, việc duyệt theo thứ tự sẽ tạo ra một danh sách các số theo thứ tự tăng dần (tăng dần), có nghĩa là Cây nhị phân này là Cây tìm kiếm nhị phân.

Tìm kiếm giá trị trong BST

Tìm kiếm một giá trị trong BST rất giống với cách chúng tôi tìm thấy một giá trị bằng cách sử dụng Tìm kiếm nhị phân trên một mảng.

Để Tìm kiếm nhị phân hoạt động, mảng phải được sắp xếp sẵn và việc tìm kiếm một giá trị trong mảng có thể được thực hiện rất nhanh.

Tương tự, việc tìm kiếm một giá trị trong BST cũng có thể được thực hiện rất nhanh nhờ cách đặt các nút.

Sử dụng hoạt ảnh bên dưới để xem cách chúng tôi tìm kiếm một giá trị trong Cây tìm kiếm nhị phân.

Thuật toán trên có thể được thực hiện như thế này:

 def search(node, target):
    if node is None:
        return None 
    elif node.data == target:
        return node
    elif target < node.data:
        return search(node.left, target)
    else:
        return search(node.right, target)

Độ phức tạp về thời gian để tìm kiếm BST cho một giá trị là \(O(h)\), trong đó \(h\) là chiều cao của cây.

Ví dụ: đối với BST có hầu hết các nút ở phía bên phải, chiều cao của cây sẽ trở nên lớn hơn mức cần thiết và việc tìm kiếm trong trường hợp xấu nhất sẽ mất nhiều thời gian hơn. Những cây như vậy được gọi là không cân bằng.

Cả hai Cây tìm kiếm nhị phân ở trên đều có cùng một nút và việc duyệt theo thứ tự của cả hai cây đều cho chúng ta cùng một kết quả nhưng chiều cao rất khác nhau. Việc tìm kiếm cây không cân bằng ở trên mất nhiều thời gian hơn vì nó cao hơn.

Chúng ta sẽ sử dụng trang tiếp theo để mô tả một loại Cây nhị phân được gọi là Cây AVL. Cây AVL có khả năng tự cân bằng, nghĩa là chiều cao của cây được giữ ở mức tối thiểu để các thao tác như tìm kiếm, chèn và xóa mất ít thời gian hơn.

Chèn một nút vào BST

Chèn một nút vào BST tương tự như tìm kiếm một giá trị.

Việc chèn các nút như mô tả ở trên có nghĩa là nút được chèn sẽ luôn trở thành nút lá mới.

Sử dụng mô phỏng bên dưới để xem các nút mới được chèn như thế nào.

Tất cả các nút trong BST là duy nhất, vì vậy trong trường hợp chúng tôi tìm thấy giá trị giống với giá trị chúng tôi muốn chèn, chúng tôi sẽ không làm gì cả.

Đây là cách chèn nút trong BST có thể được thực hiện:

 def insert(node, data):
    if node is None:
        return TreeNode(data)
    else:
        if data < node.data:
            node.left = insert(node.left, data)
        elif data > node.data:
            node.right = insert(node.right, data)
    return node

Tìm giá trị thấp nhất trong cây con BST

Phần tiếp theo sẽ giải thích cách chúng ta có thể xóa một nút trong BST, nhưng để làm được điều đó, chúng ta cần một hàm tìm giá trị thấp nhất trong cây con của nút đó.

Trong hình bên dưới, nếu chúng ta bắt đầu ở nút 13 và tiếp tục đi sang trái, chúng ta sẽ đến nút 3, đây là giá trị thấp nhất, phải không?

Và nếu chúng ta bắt đầu ở nút 15 và tiếp tục đi sang trái, chúng ta sẽ đến nút 14, đây là giá trị thấp nhất trong cây con của nút 15.

Đây là cách hàm tìm giá trị thấp nhất trong cây con của nút BST trông như thế nào:

 def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

Chúng ta sẽ sử dụng hàm minValueNode() này trong phần bên dưới để tìm nút kế thừa theo thứ tự của nút và sử dụng hàm đó để xóa nút.

Xóa một nút trong BST

Để xóa một nút, trước tiên hàm của chúng ta phải tìm kiếm BST để tìm nó.

Sau khi tìm thấy nút, có ba trường hợp khác nhau trong đó việc xóa nút phải được thực hiện khác nhau.

Ở bước 3 ở trên, nút kế tiếp mà chúng tôi tìm thấy sẽ luôn là nút lá và vì đó là nút xuất hiện ngay sau nút mà chúng tôi muốn xóa nên chúng tôi có thể hoán đổi giá trị với nút đó và xóa nó.

Sử dụng hình ảnh động bên dưới để xem các nút khác nhau bị xóa như thế nào.

Nút 8 là nút lá (trường hợp 1) nên sau khi tìm thấy, chúng ta có thể xóa nó đi.

Nút 19 chỉ có một nút con (trường hợp 2). Để xóa nút 19, nút cha 15 được kết nối trực tiếp với nút 18 và sau đó có thể xóa nút 19.

Nút 13 có hai nút con (trường hợp 3). Chúng ta tìm nút kế thừa, nút xuất hiện ngay sau trong quá trình truyền tải theo thứ tự, bằng cách tìm nút thấp nhất trong cây con bên phải của nút 13, tức là nút 14. Giá trị 14 được đưa vào nút 13 và sau đó chúng ta có thể xóa nút 14.

Đây là cách BST có thể được triển khai với chức năng xóa nút:

 def delete(node, data):
    if not node:
        return None

    if data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    else:
        # Node with only one child or no child
        if not node.left:
            temp = node.right
            node = None
            return temp
        elif not node.right:
            temp = node.left
            node = None
            return temp

        # Node with two children, get the in-order successor
        node.data = minValueNode(node.right).data
        node.right = delete(node.right, node.data)

    return node

Dòng 1 : Đối số node ở đây giúp hàm có thể tự gọi đệ quy trên các cây con ngày càng nhỏ hơn trong quá trình tìm kiếm nút có data mà chúng ta muốn xóa.

Dòng 2-8 : Đây là tìm kiếm nút có data chính xác mà chúng tôi muốn xóa.

Dòng 9-22 : Nút chúng ta muốn xóa đã được tìm thấy. Có ba trường hợp như vậy:

1. Trường hợp 1 : Nút không có nút con (nút lá). None được trả về và giá trị đó trở thành giá trị bên trái hoặc bên phải mới của nút cha bằng cách đệ quy (dòng 6 hoặc 8).
2. Trường hợp 2 : Nút có nút con trái hoặc nút con phải. Nút con trái hoặc phải đó trở thành nút con trái hoặc phải mới của cha mẹ thông qua đệ quy (dòng 7 hoặc 9).
3. Trường hợp 3 : Nút có cả nút con trái và nút con phải. Người kế nhiệm theo thứ tự được tìm thấy bằng hàm minValueNode() . Chúng tôi giữ giá trị của nút kế tiếp bằng cách đặt nó làm giá trị của nút mà chúng tôi muốn xóa và sau đó chúng tôi có thể xóa nút kế tiếp.

Dòng 24 : node được trả về để duy trì chức năng đệ quy.

BST so với các cấu trúc dữ liệu khác

Cây tìm kiếm nhị phân tận dụng tốt nhất hai cấu trúc dữ liệu khác: Mảng và Danh sách liên kết.

Tìm kiếm BST cũng nhanh như Tìm kiếm nhị phân trên một mảng, với cùng độ phức tạp về thời gian \(O(\log n)\).

Và việc xóa và chèn các giá trị mới có thể được thực hiện mà không cần dịch chuyển các phần tử trong bộ nhớ, giống như với Danh sách được liên kết.

Cân bằng BST và độ phức tạp thời gian

Trên Cây tìm kiếm nhị phân, các thao tác như chèn nút mới, xóa nút hoặc tìm kiếm nút thực chất là \(O(h)\). Điều đó có nghĩa là cây càng cao (\(h\)) thì thao tác sẽ càng mất nhiều thời gian.

Lý do chúng tôi viết rằng việc tìm kiếm giá trị \(O(\log n)\) trong bảng trên là vì điều đó đúng nếu cây "cân bằng", như trong hình bên dưới.

Chúng ta gọi cây này là cân bằng vì có số lượng nút ở bên trái và bên phải của cây gần như bằng nhau.

Cách chính xác để biết rằng Cây nhị phân được cân bằng là chiều cao của cây con bên trái và bên phải của bất kỳ nút nào chỉ khác nhau một. Trong hình ảnh trên, cây con bên trái của nút gốc có chiều cao \(h=2\) và cây con bên phải có chiều cao \(h=3\).

Đối với BST cân bằng, với số lượng lớn nút (lớn \(n\)), chúng tôi nhận được chiều cao \(h \approx \log_2 n\) và do đó, độ phức tạp về thời gian để tìm kiếm, xóa hoặc chèn nút có thể là được viết là \(O(h) = O(\log n)\).

Tuy nhiên, trong trường hợp BST hoàn toàn không cân bằng, như trong hình bên dưới, chiều cao của cây xấp xỉ bằng số nút, \(h \approx n\) và chúng ta có độ phức tạp về thời gian \(O(h ) = O(n)\) để tìm kiếm, xóa hoặc chèn nút.

Vì vậy, để tối ưu hóa các hoạt động trên BST, chiều cao phải được giảm thiểu và để làm được điều đó, cây phải được cân bằng.

Và việc giữ cho Cây tìm kiếm nhị phân được cân bằng chính xác là những gì Cây AVL làm, đó là cấu trúc dữ liệu được giải thích ở trang tiếp theo.

Bài tập DSA

Kiểm tra bản thân bằng các bài tập

Bài tập:

Chèn một nút có giá trị 6 vào Cây tìm kiếm nhị phân này:

Nút mới được chèn vào đâu?

Nút có giá trị 6 
trở thành nút con bên phải
của nút có giá trị .

Cung cấp câu trả lời "

Bắt đầu bài tập