Cây splay là một cây tìm kiếm nhị phân tự cân bằng. Nó có thực hiện các thao tác cơ bản như chèn, tìm, và xóa trong thời gian trừ dần O(log n). Với nhiều dãy thao tác không ngẫu nhiên, cây splay chạy nhanh hơn các loại cây tìm kiếm nhị phân khác ngay cả khi dãy thao tác không được biết trước. Cây splay được Daniel Dominic Sleator và Robert Endre Tarjan phát minh năm 1985. đã được tìm ra trước cây splay.

center

Bước zig-zag: Thực hiện bước này khi p không là gốc và x là nút con phải và p là nút con trái hoặc ngược lại. Cây quay trên cạnh nối x và p, rồi quay trên cạnh nối x và nút cha mới là g.

center

Chèn

Để chèn x vào cây:

Đầu tiên chèn như cây tìm kiếm nhị phân thông thường.

Thực hiện thao tác splay trên x để đưa nó về gốc.

Xóa

Để xóa x, ta dùng phương pháp như cho cây nhị phân thông thường: nếu x có hai con, đổi chỗ x và nút phải nhất của cây con trái của x hoặc nút trái nhất của cây con phải của x. Sau đó xóa nút x ở vị trí mới. Bằng phương pháp này, ta luôn đưa về trường hợp xóa nút với 0 hoặc 1 nút con.

Không như cây nhị phân thông thường, sau khi xóa xong, ta thực hiện thao tác splay trên nút cha của nút mới được xóa.

HOẶC

Trước tiên thực hiện splay để đưa nút cần xóa về gốc rồi xóa. Sau đó cây bị chia cắt thành hai cây rời nhau. Thực hiện phép splay trên nút phải nhất của cây trái (cách 1), hoặc nút trái nhất của cây phải (cách 2) để đưa nó về gốc. Trong cách 1, nối cây phải vào làm cây con phải của nút gốc mới của cây trái. Nút gốc của cây trái trở thành nút gốc của cây mới hợp lại.

Đảm bảo của cây splay

Có nhiều định lý và giả thuyết về thời gian chạy của cây splay trên dãy S gồm m thao tác tìm kiếm trên cây chứa n phần tử.

;Định lý cân bằng: Thời gian thực hiện dãy S là $O\backslash Bigl(m(1+\backslash log\; n)+n\backslash log\; n\backslash Bigr).$ Nói cách khác, cây splay thực hiện tốt ngang với cây tìm kiếm nhị phân cân bằng tĩnh trên dãy gồm ít nhất n thao tác tìm. ;Định lý tối ưu tĩnh: Thời gian thực hiện S là $O\backslash Bigl(m+n+\backslash sum${j=1}^m \log(|i{j+1}-i_j|+1)\Bigr). ;Định lý quét: Còn gọi là định lý truy cập tuần tự. Tìm kiếm n phần tử của cây splay theo thứ tự tăng dần mất thời gian O(n), bất kể hình dạng ban đầu của cây là thế nào. Chặn trên chặt nhất cho tới nay là $4.5n$.