Hình dung bạn xếp một chồng sách để dễ tìm. Nếu xếp khéo, mỗi lần tìm bạn chia đôi chồng — vài bước là ra. Nhưng nếu những cuốn sách tới tay bạn đã được xếp sẵn theo thứ tự và bạn cứ đặt cuốn sau lên trên cuốn trước, bạn không có một kệ chia nhánh, bạn có một cái tháp nghiêng một hàng cao bằng số sách — muốn tìm cuốn cuối phải lật qua tất cả. Nghịch lý là: chính đống sách "đã ngăn nắp sẵn" lại tạo ra cái tháp tệ nhất. Đó đúng là chuyện xảy ra khi bạn nạp dữ liệu đã sắp xếp vào một cây tìm kiếm nhị phân không tự cân bằng.

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, đúng cái tháp nghiêng một hàng. 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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, N=50.000, mỗi số lấy MIN sau warmup. Con số đổi theo máy; cái cần nhìn là chiều cao = N (suy biến) so với log₂N, kéo theo xây O(N²) và tra cứu O(N).)

Hai niềm tin đối nghịch, cùng sai

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, đúng như chồng sách xếp-sẵn biến thành tháp nghiêng.

Về đến code hằng ngày

Điều đầ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 đó.

Điều 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.

Chỗ này đáng nói là các ngôn ngữ cao cấp đã âm thầm bảo vệ bạn khỏi đúng cái bẫy này, và biết họ làm gì rất hữu ích. TreeMap của Java và std::map/std::set của C++ luôn là cây đỏ-đen tự cân bằng — bạn không thể vô tình dựng một cây suy biến bằng chúng, dù nạp dữ liệu sắp xếp cách nào. Python thì không có cây cân bằng trong thư viện chuẩn (người ta dùng sortedcontainers — cài bằng danh sách các khối, tránh vấn đề khác đi). Và ở tầng database, đây chính là lý do chỉ mục là B-tree cân bằng: chèn hàng tỷ khóa theo thứ tự tăng dần (id tự tăng — kịch bản phổ biến nhất đời) mà cây vẫn phải giữ thấp, nên chúng cân bằng bằng cách tách/gộp node. Nếu bạn từng nghe lời khuyên "đừng dùng UUID ngẫu nhiên làm khóa chính vì hại chỉ mục", thì mặt trái của nó chính là: chỉ mục được thiết kế để nuốt trôi khóa tăng dần mà không suy biến.

Muốn tự thấy thì 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. Vài phút đó 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.