Đăng nhập để tham gia lộ trình luyện tập

CÂY TÌM KIẾM NHỊ PHÂN

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là cây nhị phân trong đó thứ tự khóa được duy trì theo một bất biến rõ ràng. Với mỗi nút $u$, mọi khóa trong cây con trái nhỏ hơn key(u) và mọi khóa trong cây con phải lớn hơn key(u). Khi bất biến này được giữ đúng cho toàn bộ hậu duệ, nhiều thao tác tìm kiếm, chèn, xóa và truy vấn theo thứ tự chỉ cần đi trên một đường từ gốc xuống cây.

Nếu chiều cao cây là $h$, các thao tác tìm kiếm, chèn, xóa, tìm cực trị, predecessor và successor thường có độ phức tạp:

BST thường không tự bảo đảm cân bằng. Nếu chèn một dãy tăng hoặc giảm, cây có thể suy biến thành một đường thẳng với:

khi đó một thao tác có thể tốn $O(n)$. Cây cân bằng giữ $h=O(\log n)$. Với Treap dùng priority ngẫu nhiên, độ cao và thời gian thao tác là logarithmic theo kỳ vọng.

Trong phần BST thuần dưới đây, mặc định khóa phân biệt. Nếu bài cho phép khóa trùng, phải xác định rõ quy ước lưu trữ trước khi triển khai.

Giai đoạn 1 - Cơ chế BST thuần

Bất biến của BST

Bất biến của BST không chỉ áp dụng cho hai con trực tiếp. Mọi nút trong toàn bộ cây con trái phải nhỏ hơn nút hiện tại, và mọi nút trong toàn bộ cây con phải phải lớn hơn nút hiện tại.

Với nút $u$:

Chỉ kiểm tra left < root < right ở từng cặp cha-con là chưa đủ, vì một nút nằm sâu vẫn có thể vi phạm cận do tổ tiên đặt ra.

Tìm kiếm

Tại nút hiện tại:

• nếu $x=key(u)$, đã tìm thấy;
• nếu $x<key(u)$, chỉ cần đi sang trái;
• nếu $x>key(u)$, chỉ cần đi sang phải.

Không cần duyệt cả hai nhánh.

hàm tim(root, x):
    u = root

    trong khi u khác rỗng:
        nếu x bằng key(u):
            trả về u

        nếu x nhỏ hơn key(u):
            u = con trái của u
        ngược lại:
            u = con phải của u

    trả về không tìm thấy

Độ phức tạp là $O(h)$.

Chèn khóa

Chèn dùng đúng đường đi của tìm kiếm. Nếu khóa chưa tồn tại, ta đi đến vị trí con rỗng đầu tiên mà khóa phải nằm ở đó rồi nối nút mới vào.

hàm chen(root, x):
    nếu root rỗng:
        tạo nút x làm root
        trả về root

    u = root

    lặp:
        nếu x bằng key(u):
            không tạo nút mới
            dừng

        nếu x nhỏ hơn key(u):
            nếu con trái của u rỗng:
                tạo nút x tại con trái
                dừng
            u = con trái
        ngược lại:
            nếu con phải của u rỗng:
                tạo nút x tại con phải
                dừng
            u = con phải

    trả về root

Thứ tự chèn quyết định hình dạng cây. Hai BST chứa cùng một tập khóa có thể có cấu trúc hoàn toàn khác nhau.

Giá trị nhỏ nhất và lớn nhất

Trong BST:

• giá trị nhỏ nhất nằm ở nút trái nhất;
• giá trị lớn nhất nằm ở nút phải nhất.

hàm tim_min(root):
    nếu root rỗng:
        trả về không tồn tại

    u = root
    trong khi con trái của u khác rỗng:
        u = con trái của u

    trả về u

tim_max làm tương tự nhưng luôn đi sang phải.

Độ phức tạp là $O(h)$.

Duyệt cây

Duyệt giữa (Inorder Traversal) theo thứ tự:

duyệt cây con trái
xử lý nút hiện tại
duyệt cây con phải

Với BST khóa phân biệt, inorder tạo ra dãy khóa tăng dần.

Duyệt ngược (Reverse Inorder):

duyệt cây con phải
xử lý nút hiện tại
duyệt cây con trái

sẽ tạo ra dãy giảm dần.

Tiền thứ tự (Preorder Traversal):

xử lý nút hiện tại
duyệt cây con trái
duyệt cây con phải

Hậu thứ tự (Postorder Traversal):

duyệt cây con trái
duyệt cây con phải
xử lý nút hiện tại

Duyệt theo mức (Level-order Traversal) dùng Queue để đi lần lượt theo độ sâu.

Duyệt toàn bộ cây tốn:

Chiều cao và cây suy biến

Nếu chiều cao tính theo số cạnh:

và:

hàm chieu_cao(u):
    nếu u rỗng:
        trả về -1

    trái = chieu_cao(con trái)
    phải = chieu_cao(con phải)

    trả về 1 + max(trái, phải)

Dãy chèn tăng dần hoặc giảm dần làm BST thuần suy biến với $h=n-1$.

Với $n$ rất lớn, cây suy biến còn có thể làm đệ quy sâu gây tràn stack. Khi cần, nên chuyển traversal hoặc thao tác sang dạng lặp.

Successor và predecessor

Successor của một nút là khóa lớn hơn gần nhất theo thứ tự inorder. Predecessor là khóa nhỏ hơn gần nhất.

Nếu nút $u$ có cây con phải, successor là phần tử nhỏ nhất của cây con phải.

Nếu không có cây con phải, ta đi ngược qua tổ tiên cho đến khi gặp tổ tiên mà $u$ nằm trong cây con trái của tổ tiên đó.

Predecessor đối xứng.

Với truy vấn quanh một giá trị $x$ bất kỳ, cần phân biệt bốn khái niệm:

Dấu <, <=, >=, > là phần quyết định. Không được dùng lẫn predecessor với floor hoặc successor với ceiling.

Xóa nút

Xóa một khóa có ba trường hợp.

Nếu nút không có con, chỉ cần ngắt liên kết.

Nếu nút có đúng một con, nối trực tiếp nút cha với người con duy nhất.

Nếu nút có hai con, có thể lấy successor là nút nhỏ nhất trong cây con phải, chép khóa successor lên nút cần xóa, rồi xóa successor khỏi cây con phải.

hàm xoa(u, x):
    nếu u rỗng:
        trả về u

    nếu x nhỏ hơn key(u):
        con trái = xoa(con trái, x)
        trả về u

    nếu x lớn hơn key(u):
        con phải = xoa(con phải, x)
        trả về u

    nếu u không có con:
        hủy u
        trả về rỗng

    nếu u chỉ có con phải:
        v = con phải
        hủy u
        trả về v

    nếu u chỉ có con trái:
        v = con trái
        hủy u
        trả về v

    s = nút nhỏ nhất trong cây con phải
    key(u) = key(s)
    con phải = xoa(con phải, key(s))

    trả về u

Sau khi xóa, gốc có thể thay đổi nên kết quả trả về của hàm xóa phải được gán lại cho con tương ứng hoặc cho root.

Kiểm tra một cây có phải BST

Cách chắc chắn là truyền xuống mỗi nút một khoảng hợp lệ mở $(lo,hi)$.

Tại nút $u$ phải có:

Khi đi sang trái, cận trên mới là key(u). Khi đi sang phải, cận dưới mới là key(u).

hàm la_bst(u, lo, hi):
    nếu u rỗng:
        trả về đúng

    nếu key(u) không nằm nghiêm ngặt giữa lo và hi:
        trả về sai

    nếu la_bst(con trái, lo, key(u)) là sai:
        trả về sai

    nếu la_bst(con phải, key(u), hi) là sai:
        trả về sai

    trả về đúng

Khi khóa có thể đạt giới hạn kiểu số nguyên, không nên tạo cận bằng key - 1 hoặc key + 1. Dùng cận rộng hơn hoặc cờ cho biết cận có tồn tại.

Truy vấn theo đoạn và cắt nhánh

Nếu cần liệt kê các khóa trong $[L,R]$, không cần duyệt toàn bộ cây.

• nếu key(u) < L, toàn bộ cây con trái cũng nhỏ hơn L, có thể bỏ;
• nếu key(u) > R, toàn bộ cây con phải cũng lớn hơn R, có thể bỏ;
• nếu khóa nằm trong đoạn, xét trái, nút hiện tại, rồi phải để giữ thứ tự tăng.

hàm liet_ke(u, L, R):
    nếu u rỗng:
        dừng

    nếu key(u) lớn hơn L:
        liet_ke(con trái, L, R)

    nếu L <= key(u) <= R:
        xuất key(u)

    nếu key(u) nhỏ hơn R:
        liet_ke(con phải, L, R)

Đây là mẫu tư duy quan trọng: dùng bất biến thứ tự để loại bỏ cả một cây con.

LCA trong BST

Với hai khóa $a<b$:

• nếu cả hai nhỏ hơn key(u), LCA nằm bên trái;
• nếu cả hai lớn hơn key(u), LCA nằm bên phải;
• nếu key(u) nằm giữa $a$ và $b$, hoặc bằng một trong hai, $u$ là tổ tiên chung thấp nhất.

hàm lca_bst(root, a, b):
    nếu a > b:
        đổi chỗ a và b

    u = root

    trong khi u khác rỗng:
        nếu b < key(u):
            u = con trái
        ngược lại nếu a > key(u):
            u = con phải
        ngược lại:
            trả về u

    trả về không tồn tại

Độ phức tạp là $O(h)$.

Giai đoạn 2 - BST trong dữ liệu động và thư viện có thứ tự

Cây thực và tập khóa là hai bài toán khác nhau

Nếu đề yêu cầu hình dạng cây, độ sâu sau từng lần chèn, cha của nút, kết quả tái cấu trúc hoặc traversal của chính cây được tạo ra, phải bảo toàn cấu trúc BST thực.

Nếu đề chỉ yêu cầu:

• thêm hoặc xóa giá trị;
• kiểm tra tồn tại;
• tìm phần tử gần nhất theo thứ tự;
• lấy min, max;
• duy trì một tập có thứ tự;

thì thường không cần tự dựng cây bằng con trỏ. Có thể dùng cấu trúc ordered container của thư viện.

Đây là bước nhận dạng quan trọng: không dùng BST tự cài chỉ vì đề có chữ "sorted", và cũng không thay một bài hỏi hình dạng BST bằng set.

set và multiset

set lưu khóa duy nhất.

multiset cho phép nhiều bản sao của cùng một khóa.

Các thao tác tìm kiếm, chèn, xóa và bound trên các cấu trúc này có độ phức tạp logarithmic theo giao diện chuẩn.

Với multiset, muốn xóa đúng một bản sao của $x$:

tìm iterator p của một bản sao x

nếu p tồn tại:
    erase(p)

Nếu gọi dạng xóa theo khóa, nhiều cài đặt có thể xóa toàn bộ các bản sao bằng khóa đó.

lower_bound và upper_bound

lower_bound(x) tìm phần tử đầu tiên thỏa:

upper_bound(x) tìm phần tử đầu tiên thỏa:

Từ hai thao tác này suy ra bốn truy vấn biên.

Ceiling:

it = lower_bound(x)

nếu it khác end:
    đáp án = *it

Strict successor:

it = upper_bound(x)

nếu it khác end:
    đáp án = *it

Strict predecessor:

it = lower_bound(x)

nếu it khác begin:
    lùi it một bước
    đáp án = *it

Floor:

it = upper_bound(x)

nếu it khác begin:
    lùi it một bước
    đáp án = *it

Phải kiểm tra begin và end trước khi lùi hoặc giải tham chiếu iterator.

map và ánh xạ có thứ tự

map dùng khi dữ liệu có dạng key -> value và ta đồng thời cần duy trì khóa theo thứ tự.

Nếu chỉ cần ánh xạ khóa sang giá trị và không cần thứ tự, cấu trúc băm có thể phù hợp hơn.

Nếu cần xuất dữ liệu theo khóa tăng, duyệt map theo iterator sẽ cho đúng thứ tự khóa.

Dựng BST cân bằng từ dãy đã sắp xếp

Nếu có một dãy tăng và muốn tạo BST có chiều cao nhỏ, chọn phần tử giữa làm gốc rồi đệ quy với hai nửa.

hàm dung_can_bang(a, l, r):
    nếu l > r:
        trả về rỗng

    mid = vị trí giữa của l và r

    tạo u với key = a[mid]

    con trái của u = dung_can_bang(a, l, mid - 1)
    con phải của u = dung_can_bang(a, mid + 1, r)

    trả về u

Nếu chọn giữa đều, chiều cao thu được ở mức $O(\log n)$.

Dựng BST từ preorder bằng cận

Không nên chèn lại từng phần tử nếu muốn khai thác trực tiếp cấu trúc của preorder. Có thể duyệt preorder một lần và dùng cận hợp lệ.

i = 0

hàm dung_preorder(lo, hi):
    nếu i đã hết dãy:
        trả về rỗng

    x = preorder[i]

    nếu x không nằm trong khoảng (lo, hi):
        trả về rỗng

    tăng i

    tạo nút u mang x
    con trái = dung_preorder(lo, x)
    con phải = dung_preorder(x, hi)

    trả về u

Nếu mỗi phần tử được dùng đúng một lần, thời gian là $O(n)$.

Cắt cây theo một đoạn giá trị

Khi cần giữ lại các khóa trong $[L,R]$:

• nếu key(u) < L, toàn bộ cây con trái bị loại, tiếp tục với cây con phải;
• nếu key(u) > R, toàn bộ cây con phải bị loại, tiếp tục với cây con trái;
• nếu khóa nằm trong đoạn, cắt tiếp cả hai con.

hàm trim(u, L, R):
    nếu u rỗng:
        trả về rỗng

    nếu key(u) < L:
        trả về trim(con phải, L, R)

    nếu key(u) > R:
        trả về trim(con trái, L, R)

    con trái = trim(con trái, L, R)
    con phải = trim(con phải, L, R)

    trả về u

Giai đoạn 3 - Khai thác thứ tự inorder và tăng cường BST

Inorder như một dãy đã sắp xếp

Rất nhiều bài BST trở nên đơn giản khi chuyển cách nhìn từ cây sang dãy inorder.

Nếu khóa phân biệt, inorder là dãy tăng. Vì vậy có thể:

• tìm chênh lệch nhỏ nhất bằng cách so các phần tử kề nhau;
• gộp hai BST bằng cách gộp hai dãy inorder tăng;
• phát hiện hai nút bị đổi chỗ bằng các nghịch thế trong inorder;
• đếm tần suất hoặc mode nếu quy ước cho phép khóa trùng;
• tạo cây cân bằng mới từ dãy inorder đã lấy ra.

Mẫu duyệt giữ một biến prev:

prev = chưa có

duyệt inorder:
    nếu prev đã tồn tại:
        dùng prev và key hiện tại để cập nhật đáp án

    prev = key hiện tại

Iterator inorder bằng Stack

Có thể tạo iterator trả lần lượt các khóa nhỏ nhất tiếp theo mà không cần lưu toàn bộ inorder.

Ý tưởng là luôn giữ trên Stack đường đi tới nút nhỏ nhất chưa trả.

hàm day_nhanh_trai(u):
    trong khi u khác rỗng:
        đưa u vào Stack
        u = con trái

khởi tạo:
    tạo Stack rỗng
    day_nhanh_trai(root)

hàm next():
    lấy và xóa nút u ở đỉnh Stack
    day_nhanh_trai(con phải của u)
    trả về key(u)

Mỗi nút được đưa vào và lấy khỏi Stack đúng một lần, nên chi phí trung bình cho mỗi lần next là $O(1)$ theo phân tích khấu hao, còn bộ nhớ là $O(h)$.

Tổng tích lũy theo thứ tự ngược

Nếu cần thay mỗi khóa bằng tổng của nó và các khóa lớn hơn, reverse inorder cho phép duyệt từ lớn xuống nhỏ.

sum = 0

duyệt reverse inorder:
    sum = sum + key(u)
    key(u) = sum

Thời gian là $O(n)$.

Khôi phục hai nút bị đổi chỗ

Một BST đúng có inorder tăng. Nếu hai khóa bị đổi chỗ, dãy inorder xuất hiện một hoặc hai vị trí nghịch:

Khi duyệt inorder, lưu nút trước đó. Ở lần nghịch đầu tiên, ứng viên thứ nhất là nút trước, ứng viên thứ hai là nút hiện tại. Nếu có lần nghịch thứ hai, cập nhật ứng viên thứ hai. Cuối cùng đổi lại hai khóa.

Hai con trỏ trên thứ tự BST

Một số bài cần tìm hai khóa có tổng bằng mục tiêu. Có thể:

• lấy inorder thành dãy tăng rồi dùng hai con trỏ;
• hoặc dùng hai iterator, một tăng và một giảm.

Nếu đã tạo dãy inorder, phần hai con trỏ tốn $O(n)$ và toàn bộ thuật toán cũng $O(n)$.

Kích thước cây con

BST tăng cường (Augmented BST) lưu thêm metadata tại mỗi nút. Metadata quan trọng nhất cho rank/select là kích thước cây con.

Nếu nút $u$ lưu số bản sao cnt(u):

Với khóa phân biệt thì cnt(u)=1.

Sau mọi thay đổi con trái hoặc con phải phải cập nhật lại sz(u).

hàm pull(u):
    nếu u rỗng:
        dừng

    sz(u) = sz(con trái) + cnt(u) + sz(con phải)

Select - phần tử nhỏ thứ k

Giả sử $k$ đánh số từ 1 và $L=sz(left(u))$.

• nếu $k\le L$, đáp án nằm bên trái;
• nếu $L<k\le L+cnt(u)$, đáp án là key(u);
• nếu $k>L+cnt(u)$, đi sang phải với $k$ mới bằng $k-L-cnt(u)$.

hàm select(u, k):
    nếu u rỗng hoặc k ngoài [1, sz(u)]:
        trả về không tồn tại

    L = sz(con trái)

    nếu k <= L:
        trả về select(con trái, k)

    nếu k <= L + cnt(u):
        trả về key(u)

    trả về select(con phải, k - L - cnt(u))

Rank - số phần tử nhỏ hơn x

Định nghĩa:

hàm rank(u, x):
    nếu u rỗng:
        trả về 0

    nếu x <= key(u):
        trả về rank(con trái, x)

    trả về sz(con trái) + cnt(u) + rank(con phải, x)

Nếu cây được giữ cân bằng, rank và select có thể chạy trong $O(\log n)$.

set và multiset thông thường không cung cấp trực tiếp phần tử thứ $k$ trong $O(\log n)`. Đi `k` bước từ `begin` vẫn có thể là tuyến tính theo$k$.

Khóa trùng bằng multiplicity

Một cách chuẩn để hỗ trợ duplicate là mỗi nút đại diện cho một giá trị và lưu số lần xuất hiện cnt.

Khi chèn khóa đã tồn tại:

cnt(u) tăng 1
pull(u)

Khi xóa một bản sao:

nếu cnt(u) > 1:
    cnt(u) giảm 1
    pull(u)
ngược lại:
    xóa nút khỏi cây

Nhờ đó inorder theo bội số vẫn đúng và rank/select dùng công thức sz ở trên.

Giai đoạn 4 - Cây cân bằng, phép quay và Treap

Vì sao cần cây cân bằng

BST thuần chỉ nhanh khi chiều cao nhỏ. Không thể kết luận một thao tác là $O(\log n)$ chỉ vì cấu trúc có tên BST.

Muốn bảo đảm hoặc duy trì độ cao nhỏ, cần một cơ chế cân bằng. Trong lập trình thi đấu, ngoài set/map có sẵn, Treap là lựa chọn tự cài phổ biến vì code ngắn và hỗ trợ split/merge tự nhiên.

Phép quay

Phép quay trái và quay phải thay đổi hình dạng cây nhưng giữ nguyên thứ tự inorder.

Quay phải quanh nút $y$:

x = con trái của y
T = con phải của x

con phải của x = y
con trái của y = T

cập nhật metadata của y
cập nhật metadata của x

x trở thành gốc mới của cây con

Quay trái là thao tác đối xứng.

Điểm quan trọng là phép quay không phá thứ tự khóa của BST.

Treap với khóa tường minh

Treap đồng thời giữ hai bất biến:

• theo key: là BST;
• theo priority: là heap.

Priority thường được sinh ngẫu nhiên. Vì vậy độ cao và độ phức tạp thao tác là logarithmic theo kỳ vọng, không phải bảo đảm tuyệt đối.

Mỗi nút thường chứa:

key
priority
cnt
size
left
right

split theo khóa

Một quy ước thuận tiện:

split(T, x) tách cây thành:

• $A$: mọi khóa < x;
• $B$: mọi khóa >= x.

hàm split(t, x):
    nếu t rỗng:
        trả về (rỗng, rỗng)

    nếu key(t) < x:
        (A2, B) = split(con phải của t, x)
        con phải của t = A2
        pull(t)
        trả về (t, B)

    ngược lại:
        (A, B2) = split(con trái của t, x)
        con trái của t = B2
        pull(t)
        trả về (A, t)

merge

merge(A,B) chỉ hợp lệ khi mọi khóa trong $A$ nhỏ hơn mọi khóa trong $B$.

Treap chọn gốc theo priority.

hàm merge(A, B):
    nếu A rỗng:
        trả về B

    nếu B rỗng:
        trả về A

    nếu priority(A) tốt hơn priority(B):
        con phải của A = merge(con phải của A, B)
        pull(A)
        trả về A

    ngược lại:
        con trái của B = merge(A, con trái của B)
        pull(B)
        trả về B

Một thao tác tổ hợp từ số lượng hằng số lần split và merge có độ phức tạp kỳ vọng:

Chèn bằng split/merge

hàm chen(t, node_moi):
    (A, B) = split(t, key(node_moi))

    nếu quy ước không cho duplicate:
        xử lý để không tạo thêm nút nếu khóa đã tồn tại

    trả về merge(merge(A, node_moi), B)

Trong cài đặt thực tế, cách xử lý duplicate phải nhất quán với định nghĩa split.

Xóa bằng split/merge

Có thể tách cây thành ba miền: nhỏ hơn $x$, bằng $x$, lớn hơn $x$, xử lý miền bằng $x$, rồi ghép lại.

(A, B) = split(t, x)
(M, C) = split(B, giá trị ngay sau x theo quy ước khóa)

xóa hoặc giảm cnt trong M

t = merge(A, merge(M, C))

Với số nguyên, không nên phụ thuộc mù quáng vào x + 1 nếu có nguy cơ tràn. Có thể viết một phiên bản split theo điều kiện <= x để tránh thủ thuật này.

Metadata và thứ tự push - pull

Khi Treap có metadata hoặc lazy propagation:

• push(u) đẩy thông tin lazy xuống con trước khi đi sâu hoặc tách cây;
• pull(u) tính lại metadata từ hai con sau khi thay đổi liên kết.

Mẫu chung:

trước khi dùng cấu trúc bên dưới u:
    push(u)

sau khi thay đổi con trái hoặc con phải của u:
    pull(u)

Quên một trong hai bước là nguồn lỗi rất thường gặp.

Implicit Treap

Implicit Treap không dùng giá trị phần tử làm khóa. Khóa ngầm là vị trí trong dãy.

Vị trí của một nút được suy ra từ:

Vì vậy split_pos(t,k) tách thành:

• cây $A$ chứa đúng $k$ phần tử đầu;
• cây $B$ chứa phần còn lại.

hàm split_pos(t, k):
    nếu t rỗng:
        trả về (rỗng, rỗng)

    push(t)

    L = sz(con trái)

    nếu k <= L:
        (A, B2) = split_pos(con trái, k)
        con trái của t = B2
        pull(t)
        trả về (A, t)

    ngược lại:
        (A2, B) = split_pos(con phải, k - L - 1)
        con phải của t = A2
        pull(t)
        trả về (t, B)

Đảo một đoạn bằng lazy reverse

Muốn đảo đoạn $[l,r]$ theo chỉ số 1-based:

• tách $l-1$ phần tử đầu;
• tách tiếp $r-l+1$ phần tử;
• bật cờ đảo ở phần giữa;
• merge ba phần lại.

(A, BC) = split_pos(root, l - 1)
(B, C) = split_pos(BC, r - l + 1)

rev(B) = rev(B) xor 1

root = merge(A, merge(B, C))

Khi push(u) gặp cờ rev:

đổi chỗ con trái và con phải

nếu con trái tồn tại:
    đảo cờ rev của con trái

nếu con phải tồn tại:
    đảo cờ rev của con phải

xóa cờ rev ở u

Đây là mẫu cơ bản để phát triển sang các thao tác đoạn phức tạp hơn.

Giai đoạn 5 - Tổng hợp, nhận dạng cấu trúc và giới hạn của BST

Chọn đúng cấu trúc trước khi code

Nếu dữ liệu tĩnh và chỉ cần sắp xếp hoặc loại trùng, sort và unique thường đơn giản hơn BST.

Nếu chỉ cần kiểm tra tồn tại và không cần thứ tự, cấu trúc băm thường phù hợp hơn.

Nếu cần thêm/xóa online và tìm láng giềng theo giá trị, set hoặc multiset là lựa chọn tự nhiên.

Nếu cần key -> value kèm thứ tự khóa, dùng map.

Nếu chỉ cần lấy min hoặc max một phía, priority_queue có thể đơn giản hơn.

Nếu cần rank, select, phần tử thứ $k$ hoặc đếm theo thứ hạng động, cần cấu trúc có order statistics như BST tăng cường, Treap tăng cường hoặc một cấu trúc khác phù hợp với tính offline của dữ liệu.

Nếu dữ liệu thực chất là một dãy động và cần cắt, ghép, đảo đoạn theo vị trí, implicit Treap phù hợp hơn BST theo khóa.

Inorder biến bài cây thành bài dãy

Một nguyên tắc mạnh của BST là:

Mỗi cây con BST tương ứng với một đoạn liên tiếp trong thứ tự inorder.

Nhờ đó một số bài nâng cao có thể chuyển từ cấu trúc cây sang bài trên đoạn.

Nếu thứ tự khóa đã cố định và ta đang xét một cây con, tập nút của cây con đó nằm trên một đoạn $[l,r]$ trong inorder. Khi thử một vị trí $k$ làm gốc:

• đoạn $[l,k-1]$ là cây con trái;
• đoạn $[k+1,r]$ là cây con phải.

Đây là nền tảng cho các mô hình quy hoạch động đoạn (Interval DP) trên BST.

dp(l, r):
    thử từng k trong [l, r] làm gốc

    kiểm tra điều kiện để k nối hợp lệ
    với cây con bên trái và bên phải

    nếu hai phía đều xây được:
        trạng thái [l, r] hợp lệ

Số trạng thái thường là $O(n^2)$, còn nếu thử mọi gốc cho mỗi đoạn thì có thể đạt $O(n^3)$. Phải căn cứ ràng buộc cụ thể để tối ưu hoặc quyết định cách tiếp cận.

Đếm hình dạng BST

Với $n$ khóa phân biệt đã có thứ tự, nếu chọn khóa thứ $k$ làm gốc thì:

• bên trái có $k-1$ khóa;
• bên phải có $n-k$ khóa.

Số BST khác nhau thỏa thứ tự khóa tuân theo:

với:

Đây là dãy Catalan.

Công thức này xuất hiện khi bài hỏi số hình dạng BST chứ không hỏi cách chèn một dãy cụ thể.

Số cách tạo cùng một hình dạng BST

Nếu một BST có cây con trái chứa $L$ khóa và cây con phải chứa $R$ khóa, sau khi khóa gốc đứng trước, các phần tử của hai cây con có thể đan xen với nhau nhưng phải giữ thứ tự nội bộ của từng phía.

Hệ số trộn là:

Nếu ways(left) và ways(right) là số cách bên trong hai cây con, dạng công thức điển hình là:

Cách dùng cụ thể còn phụ thuộc việc bài có tính thứ tự chèn ban đầu, có trừ trường hợp gốc hay lấy modulo hay không.

BST trong bài tổng hợp không nhất thiết cần tự cài cây

Ở mức nâng cao, chữ "BST" trong đề có thể chỉ cung cấp một tính chất thứ tự để biến đổi bài toán.

Các hướng thường gặp:

• dùng inorder để tạo dãy đơn điệu;
• dùng một đoạn inorder làm trạng thái;
• dùng giới hạn giá trị của tổ tiên để kiểm định;
• dùng subtree metadata để gộp thông tin;
• dùng tổ hợp để đếm hình dạng hoặc thứ tự chèn;
• dùng DP khi điều kiện của cây con phụ thuộc vào cách chọn gốc.

Điểm quan trọng là xác định đúng vai trò của BST: cấu trúc dữ liệu cần duy trì, cấu trúc cây cần bảo toàn, hay chỉ là một bất biến thứ tự phục vụ cho một thuật toán khác.

Độ phức tạp phải đi theo cấu trúc thật sự

Không nên viết "BST nên $O(\log n)$" một cách mặc định.

BST thuần:

và xấu nhất:

Cây cân bằng:

Treap ngẫu nhiên:

theo kỳ vọng.

Duyệt toàn cây:

rank/select chỉ đạt logarithmic nếu cấu trúc được cân bằng và metadata được cập nhật đúng.

Implicit Treap với một số hằng số lần split/merge cho mỗi thao tác đoạn cũng có độ phức tạp kỳ vọng $O(\log n)$ mỗi thao tác.

Khi gặp một bài mới, trước hết xác định dữ liệu là cây, tập khóa hay dãy; sau đó xác định truy vấn có cần thứ tự, duplicate, rank/select hay thao tác đoạn hay không. Chọn cấu trúc sau bước nhận dạng này sẽ tránh phần lớn các lời giải quá phức tạp hoặc sai bản chất.