Phần trước khen cây tìm kiếm nhị phân (BST) vì giữ thứ tự và tra cứu O(log n). Nhưng chữ "O(log n)" ấy có một giả định ngầm mà nếu bạn tự cài cây, rất dễ phá vỡ: cây phải cân bằng. Một BST "thường" không tự cân bằng, và khi bạn nạp dữ liệu đã sắp xếp — một tình huống cực kỳ phổ biến — cây không còn là cây nữa, nó suy biến thành một danh sách liên kết, và mọi lời hứa O(log n) sụp đổ về O(n). Tôi tự cài một BST thường trong container gcc:13, nạp dữ liệu đã sắp xếp, so với std::map (cây đỏ-đen tự cân bằng), và con số cho thấy "best case" trong đầu bạn chính là "worst case" của cây.
Vì sao dữ liệu sắp xếp giết một BST thường
BST hoạt động bằng quy tắc đơn giản: khóa nhỏ hơn đi sang trái, lớn hơn đi sang phải. Khi cây cân bằng (hai nhánh đều nhau), chiều cao là ~log₂(n), nên tra cứu chỉ ~log₂(n) bước. Đó là lời hứa O(log n).
Nhưng thứ tự chèn quyết định hình dạng cây. Nếu bạn chèn dữ liệu đã sắp xếp — 1, 2, 3, …, N — thì: node 1 làm gốc; node 2 lớn hơn 1 nên sang phải; node 3 lớn hơn 2 nên lại sang phải; … Mỗi node mới đều lớn hơn mọi node đã có, nên luôn đi về nhánh phải. Kết quả: một chuỗi chỉ toàn con phải, chiều cao đúng bằng N — không phải cây nữa, mà là một danh sách liên kết trá hình. Xây cây thành O(N²) (mỗi lần chèn đi hết chuỗi hiện có), tra cứu thành O(N), và mỗi bước đi lại là một cache miss theo con trỏ.
Điều nguy hiểm là dữ liệu sắp xếp cực kỳ hay gặp: đọc từ một file đã sort, id tự tăng, timestamp theo thứ tự thời gian, khóa lấy từ một ORDER BY. Cái mà trực giác coi là "dữ liệu đẹp, đã ngăn nắp" lại chính là đầu vào tệ nhất cho một BST không cân bằng.
Đo: cây lệch cao bằng N, chậm 461 lần
Tôi nạp N = 50.000 khóa đã sắp xếp (1..N) vào BST thường tự cài và vào std::map, đo cả ba mặt:
A. XÂY CÂY (chèn 1,2,...,50.000 đã sắp xếp):
BST thường : 1,188 s | 1.249.975.000 so sánh (~N²/2) -> O(N²)
std::map : 0,002 s | tự cân bằng, giữ O(log N)/chèn
-> BST thường chậm hơn ~594 lần khi xây
B. CHIỀU CAO cây sau khi chèn:
BST thường (lệch) : 50.000 (= N, thoái hóa thành DANH SÁCH!)
cây cân bằng : 16 (= log₂ 50.000)
C. TRA CỨU:
BST thường (lệch) : 25.051 bước/tra cứu (~N/2, O(N)) | 43.789 ns
std::map (cân bằng): 16 bước, O(log N) | 94,9 ns
-> cây lệch chậm hơn ~461 lần
Nhìn B (chiều cao) trước, vì nó là gốc rễ: BST thường sau khi chèn dữ liệu sắp xếp có chiều cao 50.000 = N, đúng bằng số phần tử — cây đã hoàn toàn thoái hóa thành một chuỗi thẳng. Trong khi std::map giữ chiều cao 16 = log₂(50.000). Chênh lệch chiều cao này là nguồn của mọi thảm họa còn lại.
A (xây cây): vì mỗi lần chèn vào cây lệch phải đi hết chuỗi hiện có (dài dần), tổng công là ~N²/2 = 1,25 tỷ so sánh, mất 1,188 giây. std::map chỉ mất 0,002 giây — nhanh hơn 594 lần — vì nó xoay (rotation) sau mỗi lần chèn để giữ cây thấp. C (tra cứu): cây lệch tốn trung bình 25.051 bước mỗi tra cứu (~N/2, đúng nghĩa O(N)), 43.789 ns; std::map chỉ 16 bước, 94,9 ns — cây lệch chậm hơn 461 lần. Cùng gọi là "cây tìm kiếm nhị phân", nhưng một cái là O(log n) và một cái là O(n) trá hình.
Một lần tôi đo hớ: "BST luôn O(log n)" và "dữ liệu sắp xếp thì tốt"
Tôi vào đo với hai niềm tin. Thứ nhất: "BST thì tra cứu O(log n)". Sai khi cây không cân bằng: nạp dữ liệu đã sắp xếp làm cây suy biến thành danh sách, tra cứu O(N) — đo được 25.051 bước, 43.789 ns, chậm 461 lần một cây cân bằng. "O(log n)" là thuộc tính của cây cân bằng, không phải của mọi thứ gọi là BST. Thứ hai, và phản trực giác hơn: "dữ liệu đã sắp xếp thì tốt cho cây". Hoàn toàn sai — với BST thường, dữ liệu sắp xếp là worst case tuyệt đối, vì nó tạo ra cây lệch nhất có thể. Cái mà tôi tưởng là đầu vào lý tưởng lại là đầu vào giết cấu trúc.
Bài học đo lường: "BST O(log n)" chỉ đúng khi cây được giữ CÂN BẰNG — một BST thường nạp dữ liệu đã sắp xếp suy biến thành danh sách (chiều cao = N thay vì log N), xây O(N²) và tra cứu O(N), chậm hàng trăm lần; phải dùng cây TỰ CÂN BẰNG (AVL, đỏ-đen = std::map) xoay sau mỗi chèn để bảo đảm O(log n) dù dữ liệu vào thế nào. Nếu tôi tin "BST luôn O(log n)" và tự cài một cây thường cho dữ liệu đến từ một nguồn đã sort, tôi đã dựng một quả bom O(n) ẩn — chạy nhanh với dữ liệu test ngẫu nhiên (cây tình cờ cân bằng), rồi sập với dữ liệu thật đã sắp xếp, đúng lúc production.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: dùng cây tự cân bằng của thư viện, đừng tự cài BST thường cho dữ liệu thật. std::map/std::set (đỏ-đen), TreeMap của Java, SortedDict — tất cả tự cân bằng và bảo đảm O(log n) dù đầu vào theo thứ tự nào. Cái giá là mỗi lần chèn/xóa làm thêm vài phép xoay, nhưng đó là cái giá rẻ để không bao giờ suy biến. Tự cài BST "cho đơn giản" chỉ an toàn khi bạn chắc chắn dữ liệu vào ngẫu nhiên — mà bạn hiếm khi chắc chắn được điều đó.
Hệ quả thứ hai: cảnh giác với dữ liệu "đã sắp xếp" hoặc "gần sắp xếp" — nó là kẻ thù của nhiều cấu trúc và thuật toán, không riêng BST. Cùng một bẫy này xuất hiện ở quicksort (pivot cố định + dữ liệu đã sort → O(n²)), ở hash table (khóa có cấu trúc + hàm băm xấu → dồn cụm). Khi test hiệu năng, luôn thử cả đầu vào đã sắp xếp và sắp xếp ngược, không chỉ ngẫu nhiên — đó là nơi worst case ẩn nấp.
Hệ quả thứ ba là tinh thần đo lường: một Big-O luôn kèm điều kiện; hỏi "điều kiện nào phá vỡ nó?" trước khi tin. Con số mang theo: "BST O(log n)" đòi cây CÂN BẰNG — chèn dữ liệu ĐÃ SẮP XẾP (1,2,...,N, rất hay gặp: file sort, id tăng, timestamp) vào BST thường làm cây lệch thành chuỗi cao = N (đo: 50.000 = N, thay vì log₂N=16), xây O(N²) (1,25 tỷ so sánh, 1,188s vs std::map 0,002s = 594x), tra cứu O(N) (25.051 bước, 43.789 ns vs 94,9 ns = 461x). Dữ liệu sắp xếp là WORST CASE của BST thường; phải dùng cây tự cân bằng (AVL/đỏ-đen). "Cây tìm kiếm nhị phân" không tự động nghĩa là O(log n) — chỉ cây cân bằng mới thế.
Thử ba mươi giây
Tự cài một BST đơn giản (không cân bằng) và chèn vào nó dãy 1, 2, 3, …, 100.000 theo đúng thứ tự. Rồi in chiều cao cây: bạn sẽ thấy nó bằng đúng 100.000 — cây đã biến thành một danh sách thẳng. Thử tra cứu vài phần tử và bấm giờ: chậm khủng khiếp. Giờ chèn cùng dãy đó vào std::map (hoặc TreeMap, SortedDict) và đo lại: chiều cao ~17, tra cứu nhanh hàng trăm lần. Rồi làm lại thí nghiệm với dữ liệu xáo trộn ngẫu nhiên thay vì sắp xếp — BST thường lúc này lại nhanh, vì cây tình cờ khá cân bằng. Ba mươi giây đó cho bạn thấy điều mà "BST là O(log n)" giấu đi: hình dạng cây phụ thuộc thứ tự chèn, và dữ liệu đã sắp xếp — thứ trông đẹp nhất — lại biến cây thành danh sách. Cân bằng không phải chi tiết nhỏ; nó là thứ duy nhất giữ cho O(log n) thành thật.
