Giới thiệu

Bạn có thể đã nghe nói rằng Splay Tree có hằng số thời gian lớn. Bạn cũng có thể đã nghe nói rằng FHQ-Treap có hằng số thời gian nhỏ. Nhưng bây giờ, tôi muốn nói rằng: bạn nói đúng, nhưng cũng không hoàn toàn đúng.

Khái niệm về "Hằng số"

Thông thường, khi kiểm tra hằng số của một thuật toán, chúng ta sẽ tạo một bộ dữ liệu và chạy thử, sau đó ước lượng thời gian chạy. Dưới đây là một số kết quả kiểm tra (sau này gọi tắt là "kiểm tra").

Có thể thấy, về mặt thời gian chạy, kết quả giống như bạn nghĩ: Treap chạy nhanh hơn Splay. Tôi không phủ nhận điều này, kết quả kiểm tra đã chứng minh điều đó.

Tuy nhiên, bạn có thể thấy rằng chúng ta đã ghi lại một thứ khác: số lần gọi hàm pushup.

Khi đưa số lần gọi pushup lên, kết quả lại khác biệt hoàn toàn. Số lần pushup của Treap lớn hơn gấp đôi so với Splay. Từ góc độ này, hằng số của Treap lại thua xa Splay!

Khi sử dụng cây cân bằng trong thực tế, thao tác pushup của chúng ta thường không chỉ đơn giản là cập nhật kích thước của cây con (dĩ nhiên chúng ta cũng có các thao tác như lazytag và pushdown, nhưng nói chung, số lần gọi pushdown và pushup thường tương đương). Hằng số chính của Splay đến từ cách nó được duy trì: mỗi nút Splay cần quản lý ba con trỏ (con trái, con phải, cha), và các thao tác xoay phức tạp có thể làm chậm tốc độ do truy cập bộ nhớ.

Trong bài kiểm tra này, vì thông tin được duy trì rất đơn giản, điểm nghẽn chính nằm ở việc duy trì cấu trúc cây cân bằng. Nhưng nếu thông tin cần duy trì trở nên phức tạp hơn, độ phức tạp của việc hợp nhất tăng lên (ví dụ, bạn cần duy trì tổng lớn nhất của dãy con, hoặc cần đánh dấu lật khoảng), điểm nghẽn sẽ chuyển sang số lần gọi pushup. Lúc này, Splay sẽ thể hiện ưu thế.

Vậy chúng ta có thể kết luận: Nếu cây cân bằng của bạn chỉ cần duy trì một tập hợp có thứ tự, thì dùng Treap sẽ tốt hơn Splay. Nhưng nếu cần duy trì thông tin khoảng và thực hiện các thao tác trên khoảng, thì Splay vẫn là lựa chọn tốt hơn.

Tối ưu hóa hằng số

Tiếp theo, chúng ta sẽ đề cập đến một số tối ưu hóa hằng số cho Splay Tree.

Cấu trúc lưu trữ

Đầu tiên là lưu trữ con trỏ. Nhiều người sẽ viết `int ch[2], cha;` vì cách này giúp giảm bớt một số điều kiện khi xoay.

Tuy nhiên, tôi đề xuất bạn viết trực tiếp `int conTrai, conPhai, cha;`. Lý do có hai điểm: việc lấy chỉ số lặp đi lặp lại thực sự là một việc lãng phí, làm chậm tốc độ (mặc dù không đo được cụ thể chậm bao nhiêu, nhưng chắc chắn là chậm); và khi thực hiện các thao tác trên cây, chúng ta thường cần truy cập các con trỏ, lúc này `ch[0], ch[1]` sẽ trở nên dài dòng và không trực quan, sử dụng `conTrai, conPhai` sẽ tốt hơn nhiều.

Dưới đây là đoạn mã cho thao tác ROTATE sử dụng `conTrai, conPhai` (sử dụng con trỏ):

inline void xoay(Node* nut)
{
    Node* cha = nut->cha;
    Node* orgCha = cha->cha;
    dayXuong(cha);
    dayXuong(nut);
    if (laConTrai(nut)) {
        cha->conTrai = nut->conPhai;
        nut->conPhai = cha;
        if (cha->conTrai) cha->conTrai->cha = cha;
    } else {
        cha->conPhai = nut->conTrai;
        nut->conTrai = cha;
        if (cha->conPhai) cha->conPhai->cha = cha;
    }
    if (orgCha) {
        if (laConTrai(cha)) orgCha->conTrai = nut;
        else orgCha->conPhai = nut;
    }
    cha->cha = nut;
    nut->cha = orgCha;
    capNhat(cha);
    capNhat(nut);
}

`Node*` là con trỏ trỏ đến nút, `laConTrai(nut)` kiểm tra xem nút `nut` có phải là con trái hay không.

Bạn sẽ thấy rằng đoạn mã không phức tạp hơn là mấy! Nếu sử dụng mảng thay vì con trỏ, phần kiểm tra nút rỗng có thể được bỏ qua, thậm chí còn có thể ngắn hơn.

Bạn có thực sự cần pushup?

Đương nhiên là cần.

Tuy nhiên, hãy thử sửa đổi mã như sau:

inline void xoay(Node* nut)
{
    Node* cha = nut->cha;
    Node* orgCha = cha->cha;
    dayXuong(cha);
    dayXuong(nut);
    if (laConTrai(nut)) {
        cha->conTrai = nut->conPhai;
        nut->conPhai = cha;
        if (cha->conTrai) cha->conTrai->cha = cha;
    } else {
        cha->conPhai = nut->conTrai;
        nut->conTrai = cha;
        if (cha->conPhai) cha->conPhai->cha = cha;
    }
    if (orgCha) {
        if (laConTrai(cha)) orgCha->conTrai = nut;
        else orgCha->conPhai = nut;
    }
    cha->cha = nut;
    nut->cha = orgCha;
    capNhat(cha);
}
inline void splay(Node* x, Node* mucTieu = nullptr)
{
    for (Node* f; (f = x->cha) != mucTieu; xoay(x))
        if (f->cha != mucTieu)
            xoay(laConTrai(f) == laConTrai(x) ? f : x);
    capNhat(x);
    if (!mucTieu) goc = x;
}

Số lần gọi pushup trong thao tác ROTATE đã giảm xuống còn một lần, nhưng vẫn đảm bảo tính đúng đắn.

Phân tích kỹ, khi thực hiện ROTATE(x), nút cha của `x` sẽ bị "ném ra" khỏi chuỗi từ `x` đến gốc, trong khi `x` tiếp tục "bò lên". Vì `x` luôn bò lên, chúng ta có thể chờ đến cuối cùng để cập nhật thông tin của `x`, và trong ROTATE chỉ cần pushup nút cha cũ.

Bạn có thực sự cần pushdown?

Không khó để nhận ra rằng các nút cần pushdown chỉ là các nút trên đường đi từ `x` đến gốc.

Có thể nghĩ ra rằng, thực hiện pushdown trước sẽ tiết kiệm được nhiều việc.

inline void xoay(Node* nut)
{
    Node* cha = nut->cha;
    Node* orgCha = cha->cha;
    if (laConTrai(nut)) {
        cha->conTrai = nut->conPhai;
        nut->conPhai = cha;
        if (cha->conTrai) cha->conTrai->cha = cha;
    } else {
        cha->conPhai = nut->conTrai;
        nut->conTrai = cha;
        if (cha->conPhai) cha->conPhai->cha = cha;
    }
    if (orgCha) {
        if (laConTrai(cha)) orgCha->conTrai = nut;
        else orgCha->conPhai = nut;
    }
    cha->cha = nut;
    nut->cha = orgCha;
    capNhat(cha);
}
inline void dayXuongTatCa(Node* x)
{
    if (!x) return;
    dayXuongTatCa(x->cha);
    dayXuong(x);
}
inline void splay(Node* x, Node* mucTieu = nullptr)
{
    dayXuongTatCa(x);
    for (Node* f; (f = x->cha) != mucTieu; xoay(x))
        if (f->cha != mucTieu)
            xoay(laConTrai(f) == laConTrai(x) ? f : x);
    capNhat(x);
    if (!mucTieu) goc = x;
}

Đây cũng là điều chúng ta thường làm khi viết LCT.

Tất nhiên, bạn có thể dùng mảng để mô phỏng ngăn xếp thay cho đệ quy, sẽ nhanh hơn một chút.

Bạn có thực sự cần pushall?

Hỏi như vậy có vẻ hơi kỳ, nhưng bạn vẫn nên kiên nhẫn.

Thao tác SPLAY có tác dụng phân bổ đều thời gian tìm kiếm từ gốc đến `x`.

Hầu hết thời gian, trong quá trình tìm kiếm, bạn đã thực hiện pushdown rồi.

Vậy nên pushall cũng bị loại bỏ! Bây giờ, Splay của bạn không còn một chút pushdown/pushup thừa nào.

Giới thiệu Leafy-Splay

Không chắc có ứng dụng rộng rãi, nhưng khá thú vị.

Như tên gọi, đây là Splay, nhưng không hoàn toàn, nó còn là "leafy", nghĩa là thông tin khóa được lưu trữ hoàn toàn trong các nút lá. Để duy trì cấu trúc cây, chúng ta cần thêm `n-1` nút phụ trợ.

Lợi ích rõ ràng là: khi hợp nhất thông tin, chúng ta không cần quan tâm đến thông tin của các nút trung gian, vì các nút này trống, chỉ dùng để chiếm chỗ. Giống như cây phân đoạn.

Một cây cân bằng "leafy" nổi tiếng là WBLT, ở đây không đề cập.

Thao tác chèn

Xét mở rộng Splay thành leafy. Thực ra không khó, khi chèn một giá trị `x`, chúng ta tìm nút tiền nhiệm `y` của `x` (nếu không tồn tại thì tìm hậu nhiệm), đây chắc chắn là một nút lá. Chúng ta thay thế vị trí của lá này bằng một nút phụ trợ, sau đó hai con của nút phụ trợ sẽ chứa `x` và `y`. Cuối cùng, thực hiện thao tác SPLAY trên nút phụ trợ vừa tạo.

Trước hết, hãy chứng minh tính đúng đắn: không khó để nhận thấy SPLAY(x) không ảnh hưởng đến cấu trúc nội bộ của cây con của `x`, chỉ thay đổi vị trí treo của cây con. Nghĩa là, SPLAY một nút phụ trợ sẽ không phá vỡ cấu trúc leafy.

Về độ phức tạp thời gian, chúng ta có thể phân tích cây như thể đã loại bỏ tất cả các nút lá (vì các nút lá đã bị loại bỏ, không cần nhân với hằng số nút của cây leafy, thậm chí còn nhỏ hơn một chút vì số nút phụ trợ là `n-1`), vẫn là O(log n).

Thao tác xóa

Đầu tiên, tìm nút lá cần xóa. Nút cha của nó (nếu có, trường hợp không có là tầm thường) chắc chắn có hai con. Chỉ cần thay thế vị trí của cha bằng con chưa bị xóa, sau đó thực hiện thao tác SPLAY.

Rất đơn giản. Đây cũng là một trong những ưu điểm lớn nhất của Leafy-Splay so với Splay truyền thống. Splay truyền thống cần SPLAY chính nó lên gốc, sau đó tìm tiền nhiệm và SPLAY lên gốc, rồi nối cây con, số lần sử dụng SPLAY nhiều hơn Leafy-Splay một lần.

Từ kết quả kiểm tra, có thể thấy trong trường hợp có thao tác xóa, Leafy-Splay có ưu thế rõ rệt.

Thao tác hợp nhất

Đây là hợp nhất không giao nhau, tức là đảm bảo `max(T1) < min(T2)`. Chỉ cần tạo một nút phụ trợ mới để nối hai cây lại là được, O(1), không làm phá vỡ quá trình phân tích thế năng. Phân tích độ phức tạp O(log) cho phép hợp nhất启发式 của Splay ở đây cũng đúng.

Trích xuất khoảng

Trích xuất khoảng hơi phức tạp hơn một chút.

Để trích xuất khoảng `[l, r]`, cần tìm tiền nhiệm của `l` và hậu nhiệm của `r`, sau đó thực hiện theo cách trích xuất của Splay truyền thống. Nhưng ở đây, tiền nhiệm và hậu nhiệm tìm được không thể là nút lá, mà phải là nút phụ trợ. Có thể thấy rằng nếu tồn tại tiền nhiệm/hậu nhiệm là lá, thì cũng chắc chắn có thể tìm được một tiền nhiệm/hậu nhiệm không phải là lá. Trường hợp không tìm thấy tiền nhiệm/hậu nhiệm, có thể tránh bằng cách thêm các nút gác ( `-vô cực` và `+vô cực`).

Lưu ý rằng không thể đệ quy đến tận lá, vì nút bạn SPLAY có thể không phải là nút cha của lá. Có thể cần duy trì `min, max` trong khoảng để dừng đệ quy kịp thời. Dĩ nhiên, nếu bạn muốn thực hiện nhiều lần SPLAY hơn để đảm bảo độ phức tạp cũng được.

Để biết, vấn đề độ phức tạp này trong việc tìm tiền nhiệm cũng xuất hiện trong trích xuất khoảng của Splay truyền thống, nhưng nhiều người không để ý.