Splay Tree: 40 Năm Không Ai Chứng Minh Nổi | Bước tiến tháng 7/2026 của Tarjan

Năm 1985, Daniel Sleator và Robert Tarjan tạo ra splay tree — cái cây tự sắp xếp lại sau mỗi lần bạn tra cứu — rồi đưa ra một phỏng đoán táo bạo: cây này TỐI ƯU. Không phải nhanh nhất trong trường hợp xấu nhất, mà bám sát được cả một cái cây được phép biết trước toàn bộ tương lai. Bốn mươi năm không ai chứng minh được. Cũng không ai bác bỏ được. Ngày 20/7/2026, một bài báo lên arXiv với tám tác giả — tên cuối cùng là Robert Tarjan. Nhưng câu chuyện thú vị hơn con số. Suốt 20 năm, mọi tiến triển đều đo bằng CÙNG MỘT CÁI THƯỚC: chặn dưới interleave của Wilber. Vấn đề là người ta đã chứng minh được cái thước ấy có thể cách chính cây tối ưu một khoảng cỡ log log n — nghĩa là cả dòng công trình đó, dù phân tích khéo đến đâu, cũng KHÔNG BAO GIỜ chạm tới hằng số. Cả ngành đã leo rất giỏi, nhưng leo lên một vách núi thấp hơn hẳn cái đỉnh cần tới. Bài báo mới vứt bỏ cái thước đó và tính công thẳng với cây tối ưu. ⚠️ NÓI CHO THẬT RÕ — video có hẳn một chương dành cho việc này: • Đây CHƯA phải dynamic optimality. Phỏng đoán đòi một hằng số; kết quả này vẫn còn log log n. • Bài báo vừa lên arXiv, CHƯA qua phản biện. • Về con số thuần tuý, cây Tango đã đạt log log n từ năm 2007 — bài này KHÔNG phá kỷ lục đó. • Cái mới nằm ở PHƯƠNG PHÁP: lần đầu tiên một cái cây thật sự được tin là tối ưu vượt qua được log n, bằng con đường không bị vách núi cũ chặn lại. ⏱ Nội dung 0:00 1985, một phỏng đoán táo bạo 0:35 Cây tìm kiếm nhị phân và log n 1:02 Truy vấn thật không rải đều 1:31 Quy tắc splay: zig-zig và zig-zag 2:02 Xoay từng bước vs splay — cùng đường đi, khác hẳn kết quả 2:32 Đối thủ không tưởng: cây biết trước tương lai 3:08 Vách núi Wilber — vì sao 20 năm không ai tới đỉnh 4:00 Hướng ngược lại: bỏ thước, đo thẳng 4:53 Nói cho thật rõ: cái gì đã và chưa được chứng minh 5:37 Kết 📄 Nguồn gốc: Chmel, Haeupler, Hladík, Koucký, Roeyskoe, Rozhoň, Sladký, Tarjan — "Splay trees are almost dynamically optimal", arXiv:2607.18498 (20/7/2026): https://arxiv.org/abs/2607.18498 Kết quả chính: splay tree là O(log log n · log² log log n)-cạnh tranh. Bài cũng chứng minh split conjecture tới thừa số Õ(log log n). Phỏng đoán gốc: Sleator & Tarjan, "Self-adjusting binary search trees", JACM 1985. Cây Tango: Demaine, Harmon, Iacono, Pătraşcu (2007). Bạn đã từng cài splay tree chưa? Để lại bình luận nhé! #splaytree #thuattoan #cautrucdulieu #toanhoc #khoahocmaytinh #tarjan #thelanmath ☕ ỦNG HỘ KÊNH — nếu video hữu ích, hãy mời mình một ly cà phê. MSB: 7703021983. Cảm ơn bạn!