Khác biệt giữa bản sửa đổi của “Cây splay”
Nội dung được xóa Nội dung được thêm vào
←Trang mới: “{{Infobox cấu trúc dữ liệu |tên=Cây splay |kiểu=cây |phát minh bởi=Daniel Dominic Sleator và Robert Endre Tarjan |năm phát minh=1985 |kh…” |
Không có tóm lược sửa đổi |
||
Dòng 7:
|không gian xấu nhất=O(n)
|tìm trung bình=O(log n)
|tìm xấu nhất=
|chèn trung bình=O(log n)
|chèn xấu nhất=trừ dần O(log n)
Dòng 17:
Mọi thao tác trên cây đều dựa trên một thao tác cơ bản gọi là ''splay'' (mở rộng). Khi thực hiện thao tác splay trên một nút của cây, cây được sắp xếp lại sao cho nút đó nằm ở gốc của cây. Một cách để thực hiện thao tác đó là trước hết tìm kiếm nút trên cây như cây nhị phân thông thường rồi thực hiện một chuỗi các [[phép quay cây nhị phân|phép quay cây]] theo một cách nhất định để đưa nút đó lên gốc. Thay vào đó, cũng có thể dùng một thuật toán từ trên xuống dưới kết hợp tìm kiếm và quay ngay trong quá trình tìm.
== Ưu điểm ==
Việc cây splay thực hiện nhanh chóng các thao tác là dựa trên tính tự tối ưu hóa của cây theo đó các nút hay được truy cập được di chuyển lại gần với gốc. Chiều cao xấu nhất là O(n) nhưng điều này rất hiếm khi xảy ra, và chiều cao trung bình là O(log ''n'').
Việc các nút hay sử dụng nằm ở gần gốc của cây là một ưu điểm lớn cho nhiều ứng dụng thực tế như các thuật toán cho [[bộ nhớ đệm]] và [[dọn rác (khoa học máy tính)|dọn rác]].
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.{{Citation 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.
== Nhược điểm ==
Một nhược điểm của cây splay là chiều cao của cây có thể là tuyến tính. Chẳng hạn, trường hợp này xảy ra khi truy cập lần lượt ''n'' phần tử của cây theo thứ tự tăng dần. Do chiều cao tương ứng với thời gian tìm kiếm, thời gian tìm kiếm trong trường hợp xấu nhất cũng là tuyến tính. Tuy nhiên cũng cần ghi chú là chi phí [[trừ dần]] trong trường hợp xấu nhất là O(log ''n'').
Cây splay thay đổi cấu trúc rất nhiều ngay cả khi thực hiện thao tác tìm kiếm (trong khi chẳng hạn, [[cây đỏ đen]] không thực hiện thay đổi nào khi tìm kiếm). Điều này khiến việc sử dụng cây splay trong môi trường đa luồng rất phức tạp và kém hiệu quả hơn các cây khác.
==Các thao tác==
===Splay===
Khi truy cập một nút ''x'', ta thực hiện thao tác splay trên nút ''x'' để chuyển nó về vị trí gốc. Thao tác splay bao gồm nhiều ''bước splay'', mỗi bước di chuyển ''x'' về gần gốc hơn. Việc luôn luôn thực hiện splay trên nút vừa được truy cập khiến các nút mới truy cập nằm gần gốc và cây luôn giữ hình dạng gần cân bằng.
Mỗi bước splay phụ thuộc vào ba yếu tố :
* ''x'' là nút con trái hay phải của cha nó là ''p'',
* ''p'' có là nút gốc hay không, và nếu không thì
* ''p'' là nút con trái hay phải của cha nó là ''g''.
Sau mỗi bước splay nút cha của ''g'' là ''gg'' phải cập nhật để trỏ tới ''x''. Nếu ''gg'' không tồn tại thì ''x'' là nút gốc mới.
Mỗi bước splay thuộc một trong ba kiểu sau:
'''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_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">{{Citation |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]]
'''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 [[phép quay cây nhị phân|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''.
[[Image:Zigzag.gif|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 ==
| |||