Cây tìm kiếm nhị phân với thứ tự chèn gây lệch

Cây tìm kiếm nhị phân có thể biến thành một chuỗi liên kết khi các khóa được chèn theo thứ tự tăng dần. Chi phí tìm kiếm phụ thuộc vào chiều cao cây, nên cận O(log n) quen thuộc cần một bảo đảm cân bằng hoặc giả định rõ về đầu vào. Với sinh viên đang so sánh các cấu trúc cây, chèn cùng bảy khóa theo hai thứ tự sẽ làm rõ điều kiện đó.

Dùng các khóa nguyên phân biệt từ một đến bảy. Chèn 1, 2, 3, 4, 5, 6, 7 đặt mỗi khóa mới ở bên phải khóa trước. Chèn 4, 2, 6, 1, 3, 5, 7 tạo cây có gốc là bốn và các tầng đều đầy. Cả hai thỏa quy tắc thứ tự của cây tìm kiếm nhị phân, nhưng độ dài đường đi khác nhau.

Quy tắc thứ tự không ràng buộc hình dạng cây

Tại mỗi nút, mọi khóa trong cây con trái phải nhỏ hơn khóa của nút, còn mọi khóa trong cây con phải phải lớn hơn. Yêu cầu này áp dụng cho toàn bộ cây con. Chỉ kiểm tra hai con trực tiếp có thể bỏ sót một hậu duệ nằm sai chỗ.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None


def insert(root, key):
    if root is None:
        return Node(key)
    node = root
    while True:
        if key == node.key:
            return root
        side = 'left' if key < node.key else 'right'
        child = getattr(node, side)
        if child is None:
            setattr(node, side, Node(key))
            return root
        node = child


def search(root, key):
    visits = 0
    while root is not None:
        visits += 1
        if key == root.key:
            return True, visits
        root = root.left if key < root.key else root.right
    return False, visits

chain = balanced = None
for key in range(1, 8):
    chain = insert(chain, key)
for key in [4, 2, 6, 1, 3, 5, 7]:
    balanced = insert(balanced, key)
assert search(chain, 7) == (True, 7)
assert search(balanced, 7) == (True, 3)
assert search(chain, 8) == (False, 7)
assert search(balanced, 8) == (False, 3)

Chính sách với khóa trùng là giữ một bản duy nhất. Nếu cây đóng vai trò từ điển, ta có thể cập nhật giá trị gắn với khóa đã tồn tại. Một chính sách khác là cho khóa bằng nhau nằm về một phía, nhưng nó làm thay đổi bất biến thứ tự và có thể tạo chuỗi dài gồm các khóa trùng nếu cấu trúc không xử lý riêng.

Bộ đếm ghi số nút được thăm. Một lần thăm có thể thực hiện cả phép kiểm tra bằng nhau lẫn phép so sánh thứ tự, nên đây không phải số lượng mọi phép so sánh cơ bản. Nêu rõ đơn vị đếm giúp tránh so sánh những số liệu đo khác nghĩa.

Mở ảnh kích thước đầy đủ ↗

Ở đây chiều cao được tính bằng số cạnh: một lá có chiều cao bằng không. Chuỗi có chiều cao sáu, còn cây đầy có chiều cao hai. Tìm kiếm thành công trên đường dài nhất từ gốc tới lá thăm số nút bằng chiều cao cộng một. Tìm kiếm không thành công cũng có thể đi theo đường dài tương tự rồi gặp một liên kết con rỗng.

Tìm kiếm đúng chưa có nghĩa là đường đi ngắn

Tại nút có khóa k, khóa cần tìm nhỏ hơn k không thể nằm trong cây con phải nếu bất biến được giữ. Ta có thể bỏ cây con ấy và đi sang trái. Lập luận đối xứng áp dụng khi khóa lớn hơn. Nếu khóa bằng k, nút hiện tại là đáp án; nếu liên kết được chọn rỗng, không còn vị trí hợp lệ nào để tìm tiếp.

Lập luận đó chứng minh tính đúng bất kể hình dạng cây. Nó không chứng minh mỗi bước loại được một nửa số nút còn lại. Trong chuỗi, đi sang phải chỉ bỏ nút hiện tại cùng cây con trái rỗng. Trong cây đầy, hai cây con có kích thước tương đương nên đường đi ngắn hơn nhiều.

Cây có chiều cao h hỗ trợ tìm kiếm và phép chèn đơn giản này trong O(h + 1) lượt thăm nút. Trường hợp xấu nhất có h = n - 1, khiến mỗi thao tác mất O(n). Chèn một dãy đã sắp vào cây rỗng cần 0 + 1 + ... + (n - 1) lượt thăm các nút đã có, tức tổng công việc xây dựng là Θ(n²).

Nêu rõ cách tạo và giữ cân bằng

Thứ tự chèn thứ hai tạo cây cân bằng trong ví dụ, nhưng cài đặt không duy trì cân bằng sau các lần chèn tiếp theo. Thêm nhiều khóa lớn hơn bảy sẽ tạo một chuỗi mới về bên phải. Hình dạng thuận lợi ban đầu không phải một bất biến được giữ qua mọi thay đổi.

Cây AVL và cây đỏ đen dùng phép xoay cục bộ cùng cập nhật thông tin ở nút để chặn chiều cao sau thay đổi. Cây tìm kiếm ngẫu nhiên dùng cơ chế khác và đưa ra bảo đảm xác suất. Chương cây chưa cân bằng của Open Data Structures tách hành vi thứ tự cơ bản khỏi các kỹ thuật cân bằng ở những chương sau.

Nếu thứ tự chèn là một hoán vị ngẫu nhiên đều của các khóa phân biệt, hành vi kỳ vọng tốt hơn nhiều so với chèn tăng dần. Giả định ấy có thể hỗ trợ chi phí kỳ vọng logarithm cho những thao tác thông thường. Tuy nhiên, dấu thời gian, mã định danh tăng dần hay dữ liệu nhập đã sắp rõ ràng không phải hoán vị ngẫu nhiên đều. Hãy xác định nguồn tạo thứ tự thực tế trước khi dựa vào mô hình đó.

Với tập khóa tĩnh đã sắp, mảng kết hợp tìm kiếm nhị phân có thể đơn giản hơn và cần ít bộ nhớ con trỏ hơn. Cây trở nên hữu ích khi cần cập nhật có thứ tự, duyệt một khoảng khóa, tìm khóa liền trước hoặc liền sau. Tài liệu cây tìm kiếm nhị phân của Princeton mô tả những thao tác đó trên bảng ký hiệu có thứ tự.

Kiểm tra bất biến của toàn bộ cây con

Một hàm kiểm tra có thể truyền cận dưới và cận trên của khóa theo đường đi. Mọi nút trong cây con trái kế thừa cận trên từ tổ tiên; mọi nút trong cây con phải kế thừa cận dưới. Chẳng hạn, khóa mười hai ở con phải của nút năm, bên trong cây con trái của gốc mười, vi phạm cận của gốc dù vẫn lớn hơn cha trực tiếp.

Kiểm thử nên gồm chèn tăng dần, giảm dần, khóa trùng và khóa không tồn tại ở cả hai đầu miền. Xác nhận duyệt trung thứ tự trả về các khóa phân biệt đã chèn theo thứ tự tăng. Kiểm tra riêng bộ đếm lượt thăm để quan sát hình dạng mà không dùng một phép đo thời gian làm bằng chứng cho độ phức tạp.

Cài đặt lặp tránh dùng ngăn xếp lời gọi của ngôn ngữ cho chuỗi dài. Phép chèn hoặc duyệt đệ quy trên cùng đầu vào lệch có thể vượt giới hạn đệ quy trước khi hết bộ nhớ cấp phát thông thường. Hình dạng cây vì vậy ảnh hưởng cả số thao tác lẫn khả năng chạy của cài đặt mô phỏng đường đi bằng lời gọi đệ quy.

Chuyển các cận kế thừa thành phép kiểm tra chạy được

Hàm kiểm tra toàn cây có thể mang theo khoảng khóa được phép cho mỗi nút đang chờ. Khoảng mở ở cả hai đầu vì cây lưu các khóa nguyên phân biệt. Con trái giữ cận dưới của cha và lấy khóa cha làm cận trên; con phải nhận khoảng đối xứng.

Cài đặt dưới đây còn theo dõi danh tính đối tượng nút. Trong một cây, mỗi nút tới được phải có đúng một vị trí. Chu trình hoặc một nút được dùng làm con ở nhiều vị trí là lỗi cấu trúc, trước cả khi xét chi phí tìm kiếm. Danh sách chờ tường minh tránh đệ quy trên chính những chuỗi dài mà bài đang khảo sát.

def valid_bst(root):
    pending = [(root, None, None)]
    seen = set()
    while pending:
        node, low, high = pending.pop()
        if node is None:
            continue
        if id(node) in seen:
            return False
        seen.add(id(node))
        if low is not None and node.key <= low:
            return False
        if high is not None and node.key >= high:
            return False
        pending.append((node.right, node.key, high))
        pending.append((node.left, low, node.key))
    return True

assert valid_bst(chain)
assert valid_bst(balanced)
assert valid_bst(None)

misplaced = Node(10)
misplaced.left = Node(5)
misplaced.left.right = Node(12)
assert misplaced.left.key < misplaced.key
assert misplaced.left.right.key > misplaced.left.key
assert not valid_bst(misplaced)

cycle = Node(1)
cycle.right = cycle
assert not valid_bst(cycle)

Hai so sánh cục bộ trong ví dụ sai đều đúng: năm nhỏ hơn mười và mười hai lớn hơn năm. Nhưng khoảng kế thừa tại mười hai là (5, 10), nên nó vi phạm cận trên từ gốc. Không chuỗi quyết định tìm kiếm đúng nào bù được cho hậu duệ đặt sai chỗ. Tìm mười hai sẽ đi sang phải tại mười và bỏ lỡ nút bị giấu bên trái.

Mở ảnh kích thước đầy đủ ↗

Hàm chấp nhận cả chuỗi bảy nút lẫn cây cân bằng vì cả hai giữ đúng thứ tự và cấu trúc sở hữu nút. Đó là chủ ý: nó kiểm tra cây tìm kiếm nhị phân hợp lệ, không kiểm tra bất biến AVL hay đỏ đen. Cây đúng nhưng chậm và cây trông cân bằng nhưng sai thứ tự là hai lỗi khác nhau; kiểm thử cần phân biệt chúng.

Trên cây hợp lệ có n nút, phép kiểm tra thăm mỗi nút một lần. Tập danh tính dùng O(n) bộ nhớ, còn danh sách chờ chứa nhiều nhất O(h + 1) mục với chiều cao h. Tổng bộ nhớ phụ do đó là O(n). Bỏ tập danh tính sẽ giảm bộ nhớ cho cấu trúc đã được tin cậy, nhưng cũng bỏ cơ chế phát hiện tường minh danh tính nút lặp lại. Các cận None đánh dấu khoảng số nguyên không bị chặn; hàm này không nhận None làm khóa.

Để luyện tập, kiểm tra một chuỗi dài tạo bằng chèn tăng dần, rồi chuyển một hậu duệ qua cận kế thừa trong khi vẫn giữ đúng quan hệ với cha trực tiếp. Trường hợp đầu phải được chấp nhận, trường hợp sau phải bị từ chối. Cuối cùng, đếm lượt thăm khi tìm thành công từng khóa trong hai cây bảy nút: chuỗi có tổng hai mươi tám, cây cân bằng có tổng mười bảy. Chọn đều một khóa đang có sẽ cho trung bình lần lượt là bốn và mười bảy phần bảy lượt thăm. Đó là trung bình của tải tìm kiếm cụ thể, khác với đường dài nhất trong hình đầu.