Bài trước để lại một vết thương: một cây tìm kiếm nhị phân thường, khi nhận khóa đã sắp tăng dần, thoái hóa thành một cái xâu — cao 40.000 thay vì 34, tra một khóa mất 32.672 nano giây thay vì 51. Bài này đo cách chữa: cây tự cân bằng (AVL, đỏ-đen), loại cây tự xoay lại sau mỗi lần chèn để giữ chiều cao luôn quanh log n. Nó chữa được thật — nhưng khi đo cả cái giá phải trả, tôi vấp hai điều đi ngược trực giác, và điều thứ hai thì bất ngờ tới mức phải đo một đường cong mới tin.
Xoay để giữ cây thấp
Ý tưởng của cây tự cân bằng đơn giản: sau mỗi lần chèn (hay xóa), cây kiểm tra xem có nhánh nào lệch quá không, và nếu có thì thực hiện vài phép xoay — thao tác cục bộ đổi chỗ vài node để hạ chiều cao mà vẫn giữ đúng thứ tự tìm kiếm. Nhờ vậy chiều cao luôn bị ép về cỡ log n, nên tra, chèn, xóa đều bảo đảm O(log n) — kể cả với đầu vào tệ nhất, đúng cái đầu vào đã sắp làm sụp BST thường.
Có nhiều dòng cây cân bằng, khác nhau ở chỗ ép cân chặt tới đâu. AVL giữ rất chặt: chênh lệch chiều cao hai nhánh của mọi node không quá 1, nên cây thấp nhất có thể và tra nhanh nhất — đổi lại phải xoay nhiều hơn mỗi khi chèn/xóa. Đỏ-đen giữ lỏng hơn (cây có thể cao gấp tối đa khoảng hai lần AVL), xoay ít hơn nên ghi rẻ hơn; đây là loại cây mà std::map của C++, TreeMap của Java, và nhiều cấu trúc trong nhân Linux dùng. Tôi cài AVL để đo, vì nó dễ đo chiều cao và cho thấy hiệu ứng cân bằng rõ nhất.
Đo: AVL chữa được suy biến, nhưng có giá
Tôi cài AVL và BST thường trong C (gcc -O2), rồi cho cùng một tập 40.000 khóa vào theo hai kịch bản: đã sắp (tăng dần) và ngẫu nhiên. Với mỗi cây đo chiều cao, thời gian dựng, thời gian tra trung bình, và với AVL đếm luôn số phép xoay.
Kịch bản khóa đã sắp — nơi BST thường chết:
BST thường : cao 40000 tra 32538 ns dựng 644 ms
AVL : cao 16 tra 215 ns dựng 1,6 ms (39984 phép xoay)
AVL sửa hẳn: chiều cao từ 40.000 xuống 16, tra từ 32.538 xuống 215 nano giây — nhanh 151 lần. Và một điều tôi không ngờ: AVL còn dựng nhanh hơn 400 lần (1,6 ms so với 644 ms). Lý do là dựng BST thường từ khóa đã sắp tốn O(n²) — mỗi lần chèn phải lê xuống hết cái xâu — còn AVL luôn thấp nên mỗi lần chèn chỉ đi log n bước. Cân bằng không chỉ cứu lúc tra, nó cứu luôn lúc xây.
Kịch bản khóa ngẫu nhiên:
BST thường : cao 34 tra 49 ns
AVL : cao 18 tra 37 ns dựng 3,9 ms (27906 phép xoay) [BST dựng 2,7 ms]
Ở đây câu chuyện khác hẳn, và đó là cú hớ đầu tiên của tôi.
Một lần tôi đo hớ: cân bằng là bảo hiểm, không phải quà miễn phí
Tôi vào bài với niềm tin gọn gàng: AVL là "phiên bản tốt hơn" của BST, luôn hơn, nên cứ dùng AVL ở mọi nơi cho chắc. Nhưng nhìn kịch bản ngẫu nhiên: BST thường đã tự cao 34 (cỡ 2·log n) mà không cần cân bằng gì, tra 49 nano giây. AVL tra 37 — nhanh hơn, nhưng chỉ hơn một phần tư, không phải một trời một vực. Đổi lại cái hơn nhỏ đó, AVL phải làm 27.906 phép xoay trong lúc chèn, và dựng cây chậm hơn (3,9 so với 2,7 ms). Với dữ liệu đến ngẫu nhiên, một BST thường đã gần đủ tốt, và công cân bằng gần như là lãng phí.
Đây là bài học đặt cân bằng vào đúng chỗ: cây tự cân bằng là một hợp đồng bảo hiểm, không phải một món quà miễn phí. Bạn trả phí đều đặn (xoay mỗi lần ghi) để mua sự bảo đảm rằng ca xấu nhất — khóa đã sắp, hoặc một kẻ tấn công cố tình đưa khóa để làm cây lệch — sẽ không bao giờ xảy ra. Trên đầu vào đã sắp, khoản bảo hiểm đó trả gấp 151 lần. Trên đầu vào ngẫu nhiên hiền lành, nó gần như không trả gì, và bạn vẫn phải đóng phí. Đáng hay không tùy bạn có kiểm soát được đầu vào không — và đó là câu hỏi phải đo, không phải mặc định chọn cái "xịn hơn".
Bất ngờ thứ hai: cùng cây cân bằng, bố cục bộ nhớ đổi tốc độ 6 lần
Rồi tôi vấp một điều lạ khiến phải dừng lại. Hai con số mâu thuẫn nhau: AVL dựng từ khóa đã sắp tra mất 215 nano giây, nhưng AVL dựng từ khóa ngẫu nhiên chỉ 37 nano giây — chậm gần 6 lần — dù cả hai cây đều đã cân bằng, cùng chiều cao 16-18 và cùng độ sâu trung bình 14,4. Cùng số node đi qua mỗi lần tra, mà thời gian chênh 6 lần. Theo đúng kỷ luật của sê-ri, hai số mâu thuẫn nghĩa là có một biến ẩn tôi chưa đo. Tôi đi tìm nó.
Biến ẩn là bố cục bộ nhớ, và cách chắc chắn nhất để lộ nó là đo một đường cong theo kích thước, chứ không đo một điểm:
n = 1000 (31 KB) : dựng-tăng-dần 12 ns dựng-ngẫu-nhiên 26 ns
n = 16000 (500 KB) : dựng-tăng-dần 142 ns dựng-ngẫu-nhiên 29 ns
n = 40000 (1,2 MB) : dựng-tăng-dần 211 ns dựng-ngẫu-nhiên 38 ns
Đường cong nói rõ. Khi cây đủ nhỏ để nằm gọn trong cache (31 KB), bố cục không quan trọng — thậm chí cây dựng tăng dần còn nhanh hơn (12 so với 26). Nhưng khi cây vượt cache, cây dựng-tăng-dần bung ra (142, rồi 211 nano giây) trong khi cây dựng-ngẫu-nhiên vẫn thấp. Vì sao? Vì node được cấp phát theo thứ tự chèn. Chèn ngẫu nhiên thì các node được chèn sớm — vốn nằm gần gốc, được mọi lượt tra đi qua — tình cờ dồn vào vùng địa chỉ thấp liền nhau, nên tầng trên "nóng" của cây gói gọn trong một khối cache nhỏ. Chèn tăng dần thì node được xếp theo khóa, nên các node tầng trên (gốc là khóa ở giữa, con là khóa một phần tư và ba phần tư...) rải khắp mảng — tầng nóng trải rộng cả 1,2 MB, quá cache, và mỗi lượt tra là một chuỗi trượt cache. Cùng một cây cân bằng hoàn hảo, hai cách xây cho hai tốc độ khác hẳn. Big-O nhìn cả hai là O(log n) và mù hoàn toàn trước chuyện này — đúng như bài về cache và bài BST đã cho thấy ở dạng khác.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: chọn cây cân bằng theo việc bạn có kiểm soát đầu vào hay không, đừng chọn theo "cái nào xịn hơn". Nếu khóa đến từ nguồn bạn không tin (người dùng, mạng, dữ liệu đã sort), cây tự cân bằng đáng từng phép xoay vì nó chặn ca xấu O(n). Nếu khóa đến ngẫu nhiên và bạn kiểm soát được, một BST thường — hay tốt hơn nữa là một bảng băm — thường đủ và rẻ hơn. Và giữa các cây cân bằng: cần đọc nhiều thì nghiêng AVL (cây thấp hơn), cần ghi nhiều thì nghiêng đỏ-đen (xoay ít hơn). Đây là những đánh đổi đo được, không phải thứ hạng cố định.
Hệ quả thứ hai, sâu hơn: "cùng độ phức tạp" không có nghĩa là "cùng tốc độ". Hai cây AVL cùng chiều cao, cùng O(log n), mà tra chênh 6 lần chỉ vì thứ tự các node nằm trong bộ nhớ. Đây là lý do các cấu trúc đọc-nhiều hiệu năng cao thường không dùng cây con trỏ rải rác mà dùng cây gói trong mảng liền (B-tree, cây Eytzinger) — để tầng nóng luôn ở cạnh nhau trong cache. Bài sau về B-tree sẽ đo chính điều đó.
Hệ quả thứ ba là bài học đo lường của cả sê-ri, lần này hiện ra hai tầng. Con số mang theo: AVL sửa BST suy biến triệt để (khóa đã sắp: cao 40000 xuống 16, tra 32538ns xuống 215ns, nhanh 151 lần) nhưng trên khóa ngẫu nhiên chỉ hơn một phần tư mà tốn 27906 phép xoay — cân bằng là bảo hiểm cho ca xấu; và ngay cả một cây đã cân bằng hoàn hảo, tra vẫn chênh 6 lần tùy bố cục bộ nhớ, thứ mà O(log n) không nhìn thấy. Đừng dừng ở nhãn độ phức tạp; đo cả giá lúc ghi lẫn lợi lúc đọc, và đo cả một đường cong theo n để bắt những biến ẩn như cache.
Thử ba mươi giây
Nếu bạn đang dùng một cây cân bằng trong hệ thống thật, hỏi hai câu. Thứ nhất: đầu vào của tôi có thật sự cần bảo hiểm không? Nếu khóa đến ngẫu nhiên và bạn chỉ tra là chính, thử thay bằng một bảng băm và đo — rất có thể nó nhanh hơn và đơn giản hơn cái cây. Thứ hai: cây của tôi có lớn hơn cache không? Nếu có, thứ tự bạn nạp dữ liệu vào (và loại cây bạn chọn) sẽ đổi tốc độ tra theo bội số, dù big-O không đổi. Cách thử nhanh: đo thời gian tra ở vài kích thước n tăng dần và vẽ ra — nếu thấy một bậc thang nhảy vọt ở đâu đó, bạn vừa tìm thấy đúng chỗ cây tràn khỏi cache, và đó là ranh giới thật sự quyết định hiệu năng của bạn, không phải cái log n trên giấy.
