Balanced Binary Tree

Q: Độ phức tạp thời gian của cây nhị phân cân bằng là bao nhiêu?

Một lượt duyệt hậu tự đi qua mỗi nút một lần: thời gian O(n) và bộ nhớ ngăn xếp O(h) với cây có chiều cao h . Tính lại chiều cao ở mỗi nút tốn O(n·h) , con số này trở thành O(n²) khi cây là một chuỗi.

DễDuyệt cây Đệ quy

+10

Mảng root lưu một cây nhị phân. Gốc nằm ở chỉ số 0, các nút con của chỉ số i nằm tại 2*i+1 (bên trái) và 2*i+2 (bên phải), -1 đánh dấu một vị trí trống và có thể có thêm các giá trị -1 ở cuối.

Trả về true nếu cây cân bằng chiều cao, nghĩa là tạ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 chênh lệch không quá 1; nếu không thì trả về false. Chiều cao của một cây con là số nút trên đường đi dài nhất từ trên xuống; cây con rỗng có chiều cao 0.

Hàm

isBalanced(root: integer-array) → boolean

rootinteger-array: cây nhị phân theo thứ tự từng cấp, dùng -1 cho vị trí trống
Trả vềboolean: đúng nếu chiều cao của hai cây con của mọi nút chênh lệch không quá 1, sai trong các trường hợp khác

Ràng buộc

1 ≤ root.length ≤ 32767
Mỗi root[i] là -1 hoặc một giá trị thỏa mãn 0 ≤ root[i] ≤ 10⁵.
root[0] không bao giờ là -1, vì vậy cây có ít nhất một nút.
Mảng (array) có thể kết thúc bằng các phần tử -1 dư ra sau nút cuối cùng.
Cả hai nút con của một vị trí trống cũng đều trống, và độ sâu tối đa là 14.
Giá trị của các nút là khác nhau.

Ví dụ

Đầu vào: root = [5, 2, 9, -1, -1, 7, 11]
Đầu ra: true
Giải thích: Cây con bên trái của nút gốc chỉ có nút 2, chiều cao là 1. Cây con bên phải gồm 9, 7, 11, có chiều cao là 2. Hai cây con này chênh lệch nhau 1, và mọi nút khác đều có hai cây con có chiều cao bằng nhau.

Đầu vào: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Đầu ra: false
Giải thích: Cả hai phía của nút gốc đều có chiều cao 3, nhưng nút 3 không đạt yêu cầu: cây con bên trái gồm 1, 0 có chiều cao 2, còn cây con bên phải thì rỗng.

Đầu vào: root = [4, 2, -1, 1]
Đầu ra: false
Giải thích: Nút gốc có chuỗi 2, 1 ở bên trái, chiều cao 2, và không có gì ở bên phải, chiều cao 0. Chênh lệch 2 là quá lớn.

Câu hỏi mở rộng

Bạn có thể kiểm tra cây mà không dùng đệ quy, bằng một ngăn xếp tường minh không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Quy tắc áp dụng ở mọi nút, nên một cây có nút gốc trông cân bằng vẫn có thể không đạt yêu cầu ở các nút bên dưới, như ví dụ thứ hai tại 3. Một lượt duyệt hậu thứ tự tính chiều cao của mỗi cây con một lần và báo lỗi lên trên ngay khi phát hiện, với độ phức tạp O(n).

Tính lại chiều cao tại mỗi nút

Ý tưởng

Chuyển định nghĩa thành code. height(i) bằng 0 ở vị trí trống và bằng chiều cao của nút con cao hơn cộng thêm 1 ở các vị trí khác. So sánh chiều cao của hai nút con tại mỗi nút thực; nút đầu tiên có độ chênh lệch chiều cao lớn hơn 1 khiến kết quả là false.

Mỗi lần kiểm tra đều duyệt toàn bộ cây con bên dưới nút đó, nên mỗi nút được duyệt một lần cho mỗi nút nằm phía trên nó: O(n·h). Với tối đa 14 tầng, một cây đầy đủ có 16,383 nút cần khoảng 2 × 10^5 bước. Một chuỗi gồm n nút sẽ cần O(n²).

Thuật toán

Định nghĩa height(i) là 0 nếu chỉ số nằm sau vị trí cuối cùng hoặc là -1, và là 1 + max(height(2*i+1), height(2*i+2)) với một nút thực.
Duyệt qua từng chỉ số i chứa một nút thực.
Nếu height(2*i+1) và height(2*i+2) chênh lệch nhau hơn 1, trả về false.
Nếu vòng lặp kết thúc mà không gặp lỗi, trả về true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Một lượt duyệt hậu thứ tự để trả về chiều cao hoặc báo lỗi

Ý tưởng

Việc kiểm tra tại một nút cần chiều cao của hai cây con, và nút cũng cần những chiều cao đó để báo chiều cao của chính nó. Vì vậy, hãy lấy cả hai trong một lượt duyệt hậu thứ tự: mỗi lời gọi trả về chiều cao cây con sau khi cả hai nút con đã trả về.

Lỗi ở phía dưới cũng phải truyền lên trên. Chiều cao thực không bao giờ âm, vì vậy hãy dùng -1 để biểu thị lỗi: một lời gọi trả về -1 khi một nút con trả về -1 hoặc chiều cao của hai nút con chênh lệch hơn 1. Trong ví dụ thứ hai, nút 3 thấy chiều cao là 2 và 0 rồi trả về -1, nút gốc truyền tiếp giá trị đó mà không duyệt nhánh phải.

Không có nút nào được truy cập hai lần, nên độ phức tạp thời gian là O(n), với O(h) lời gọi trên ngăn xếp.

Thuật toán

Viết check(i). Nếu chỉ số vượt quá cuối mảng hoặc là -1, hãy trả về 0.
Tính left = check(2*i+1). Nếu giá trị này là -1, hãy trả về -1.
Tính right = check(2*i+2). Nếu giá trị này là -1, hoặc left và right chênh lệch hơn 1, hãy trả về -1.
Nếu không, hãy trả về 1 + max(left, right).
Trả về kết quả cho biết check(0) có khác -1 hay không.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Lỗi thường gặp và trường hợp biên

Chỉ kiểm tra nút gốc. Trong ví dụ thứ hai, hai phía của nút gốc đều có chiều cao 3, nhưng nút 3 lại lệch 2.
So sánh lá nông nhất và lá sâu nhất. Cây cân bằng nhỏ nhất có chiều cao 6 có các lá ở độ sâu 4 và 6, và mọi nút trong cây đều đạt yêu cầu.
Làm mất trạng thái thất bại khi đi ngược lên. Nếu một nút con trả về -1 và nút cha tính 1 + max(-1, 2), trạng thái thất bại sẽ biến trở lại thành chiều cao.
Dùng độ dài mảng làm chiều cao. Các phần tử -1 ở cuối khiến mảng dài hơn độ sâu của cây.
Trong Lua và R, mảng bắt đầu từ chỉ số 1. Hãy giữ chỉ số nút bắt đầu từ 0 để dùng 2*i+1, và đọc root[i + 1].

Câu hỏi thường gặp3

Độ phức tạp thời gian của cây nhị phân cân bằng là bao nhiêu?

Một lượt duyệt hậu tự đi qua mỗi nút một lần: thời gian O(n) và bộ nhớ ngăn xếp O(h) với cây có chiều cao h. Tính lại chiều cao ở mỗi nút tốn O(n·h), con số này trở thành O(n²) khi cây là một chuỗi.

Chiều cao cân bằng của cây nhị phân có nghĩa là gì?

Ở mỗi nút, chiều cao của cây con bên trái và bên phải chênh lệch tối đa 1. Cây AVL khôi phục tính chất này sau mỗi lần thêm và xóa, nhờ đó giữ cho chiều cao ở mức O(log n).

Cây nhị phân đầy đủ có phải lúc nào cũng cân bằng không?

Đúng. Mọi tầng của cây hoàn chỉnh đều đầy, ngoại trừ tầng cuối có thể chưa đầy và được lấp từ trái sang, vì vậy tại mọi nút, chiều cao của hai cây con chênh lệch không quá 1. Chiều ngược lại không đúng: cây cân bằng có thể có các vị trí trống ở bên trái của tầng cuối.

def isBalanced(root):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

root = [5, 2, 9, -1, -1, 7, 11]

Đầu ra mong đợi

true