Splay tree: moi truy van dua node duoc truy cap len gan root qua cac phep xoay (rotation). Muc tieu: splay node 1 (hien dang o do sau 3, tren truc trai). Ta can mot zig-zig vi 1 la con trai cua 2, va 2 la con trai cua 4 — hai canh cung huong. Chi phi thuc = do sau = 3. Hamm the nang (phi) se giam sau khi cay can bang hon.
Zig-zig phase A, buoc 1: nang cha (p=2) len vi tri cua ong (g=4) duoi root. Dung reparent{node=2, parent=7} — 2 tro thanh con truc tiep cua 7. Toan bo subtree cua 2 (gom 1 va 3) duoc mang theo — reparent dich chuyen ca cum.
Zig-zig phase A, buoc 2: day ong (g=4) xuong thanh con cua p=2. reparent{node=4, parent=2}. Kiem tra cycle: 2 khong con la hau due cua 4 (vua duoc tach o buoc truoc), nen phep chuyen an toan. Reingold-Tilford tinh lai layout — do sau cua 1 giam tu 3 xuong 2.
Zig-zig phase A, buoc 3: chuyen C (=3, ban chat la sub-tree giua cua p) sang lam con trai moi cua g=4. reparent{node=3, parent=4}. Sau buoc nay cay da hoan thanh phase A cua zig-zig: p=2 ngoi tren, g=4 la con phai cua p, va node 1 da san sang tro len lop cao hon.
Zig-zig phase B, buoc 1: nang x=1 len vi tri cua p=2 duoi root. reparent{node=1, parent=7}. Tu do sau 4 (tinh ca root), node 1 da nhay len do sau 1 — day chinh la tac dung rut ngan cua splay.
Zig-zig phase B, buoc 2: day p=2 xuong thanh con phai cua x=1. reparent{node=2, parent=1}. Layout cuoi cung: 1 sat root 7, va toan bo chuoi 2 → 4 → (3,5) tro thanh subtree cua 1. Do sau cua 1 = 1 (thay vi 3 ban dau).
Ket thuc splay(1). Tong chi phi thuc = 3 (ngang voi do sau ban dau). Theo phan tich khau hao, moi truy van splay co chi phi khau hao O(logn) — phi giam bu tru cho cac lan truy van tuong lai. MetricPlot cho thay phi giam tu 8.5 → 5.8, xac nhan hieu ung can bang hoa cua splay. Luu y: moi reparent goi Reingold-Tilford tinh lai toa do, nen vi tri cac node thuc su dich chuyen giua cac frame — day la rotation that, khong phai to mau gia.