Mở trình đơn chính

Các thay đổi

n
chú thích, replaced: {{Citation → {{chú thích (7)
Các ưu điểm bao gồm:
* Lập trình đơn giản hơn nhiều loại cây nhị phân cân bằng khác như [[cây đỏ đen]] và [[cây AVL]].
* Tốc độ trung bình ngang với các cây khác.{{Citationchú thích needed|date=January 2010}}
* Tốn ít bộ nhớ do không phải lưu trữ thêm thông tin để cân bằng cây.
 
'''Bước zig:''' Thực hiện bước này nếu ''p'' là gốc. Cây được [[phép quay cây nhị phân|quay]] trên cạnh nối ''x'' và ''p''. Chỉ cần thực hiện phép zig khi ''x'' ở độ sâu lẻ khi thao tác splay bắt đầu.
 
[[File:splay_tree_zigsplay tree zig.svg|center]]
 
'''Bước zig-zig:''' Thực hiện bước này khi ''p'' không là gốc và ''x'' và ''p'' đều là nút con trái hoặc đều là nút con phải. Ảnh dưới là cho trường hợp ''x'' và ''p'' đều là nút con trái (trường hợp kia hoàn toàn đối xứng). Cây [[phép quay cây nhị phân|quay]] trên cạnh nối ''p'' và cha nó là ''g'', sau đó quay trên cạnh nối ''x'' và ''p''. Ghi chú đây là bước duy nhất khác với phương pháp ''quay về gốc'' của Allen và Munro<ref name="AllenMunro">{{Citationchú thích |author=Allen, Brian; and Munro, Ian |title=Self-organizing search trees |journal=Journal of the ACM |volume=25 |pages=526–535 |year=1978 |issue=4 |doi=10.1145/322092.322094 }}</ref> đã được tìm ra trước cây splay.
 
[[Image:Zigzig.gif|center]]
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<ref name="SleatorTarjan">{{Citationchú thích |first1=Daniel D. |last1=Sleator |first2=Robert E. |last2=Tarjan |title=Self-Adjusting Binary Search Trees |url=http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf |journal=Journal of the ACM ([[Association for Computing Machinery]]) |volume=32 |issue=3 |pages=652–686 |year= 1985 |doi=10.1145/3828.3835 }}</ref>: Thời gian thực hiện dãy ''S'' là <math>O\Bigl(m(1+\log n)+n\log n\Bigr).</math> 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<ref name="SleatorTarjan" />: Đặt <math>q_i</math> là số lần tìm phần tử ''i'' trong dãy ''S''. Thời gian thực hiện ''S'' là <math>O\left (m+\sum_{i=1}^n q_i\log\frac{m}{q_i}\right).</math> 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 tĩnh tối ưu trên dãy gồm ít nhất ''n'' thao tác tìm.
;Định lý ngón trỏ tĩnh<ref name="SleatorTarjan" />: Đặt <math>i_j</math> là phần tử được tìm ở thao tác thứ <math>j</math> của ''S'' và đặt ''f'' là một phần tử cố định (ngón trỏ). Thời gian thực hiện ''S'' là <math>O\Bigl(m+n\log n+\sum_{j=1}^m \log(|i_j-f|+1)\Bigr).</math>
;Định lý tập hợp đang hoạt động<ref name="SleatorTarjan" />: Đặt <math>t(j)</math> là số phần tử khác nhau được tìm kiếm giữa thao tác thứ ''j'' và lần gần nhất trước đó <math>i_j</math> được tìm. Thời gian thực hiện ''S'' là <math>O\Bigl(m+n\log n+\sum_{j=1}^m \log(t(j)+1)\Bigr).</math>
;Định lý ngón trỏ động<ref name="ColeEtAl">{{Citationchú thích |author=Cole, Richard |coauthors=Mishra, Bud; Schmidt, Jeanette; and Siegel, Alan |title=On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences |journal=SIAM ([[Society for Industrial and Applied Mathematics]]) Journal on Computing |volume=30 |pages=1–43 |year=2000 }}</ref><ref name="Cole">{{Citationchú thích |author=Cole, Richard |title=On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof |journal=SIAM Journal on Computing |volume=30 |pages=44–85 |year=2000 |doi=10.1137/S009753979732699X }}</ref>: Thời gian thực hiện ''S'' là <math>O\Bigl(m+n+\sum_{j=1}^m \log(|i_{j+1}-i_j|+1)\Bigr).</math>
;Định lý quét<ref name="Tarjan">{{Citationchú thích |author=Tarjan, Robert E. |title=Sequential access in splay trees takes linear time |journal=Combinatorica |volume=5 |pages=367–378 |year=1985 |doi=10.1007/BF02579253 |issue=4 }}</ref>: 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à <math>4.5n</math>.<ref name="Elmasry">{{Citationchú thích |author=Elmasry, Amr |title=On the sequential access theorem and Deque conjecture for splay trees |journal=Theoretical Computer Science |volume=314 |pages=459–466 |year=2004 |issue=3 |doi=10.1016/j.tcs.2004.01.019 }}</ref>
 
== Tài liệu tham khảo ==
986.568

lần sửa đổi