Cây SPLAY trong cấu trúc dữ liệu và giải thuật

Cây SPLAY là gì ?

Là cây tìm kiếm nhị phân

- Mỗi khi truy cập vào mộ nút trên cây( thêm hoặc xoá) thì nút mới truy nhập sẽ được tự động chuyển thành gốc của cây mới - Các nút được truy cập thường xuyên sẽ ở gần gốc - Để dịch chuyển nút ta dung các phép xoay giống với trong AVL tree - Các nút nằm trên đường đi từ gốc tới nút mới truy cập sẽ chịu ảnh hưởng của các phép xoay

Kỹ thuật quay cây SPLAY

Có 2 phép quay trong cây SPLAY , đó là :

Kỹ thuật xoay đơn cây SPLAY

xoay đơn : Nút cha xuống thấp 1 mức và nút con lên 1 mức, chúng ta có thể thực hiện kỹ thuật xoay đơn như sau:

Kỹ thuật xoay kép cây SPLAY

Xoay kép : gồm 2 phép xoay đơn lien tiếp. Nút tang lên 1 mức và các nút còn lại lên hoặc giảm xuống nhiều nhất 1 mức , chúng ta thực hiện kỹ thuật xoay kép như sau:

Ý tưởng mới :tại mỗi bước ta di chuyển nút liền 2 mức Xét các nút trên đường đi từ gốc đến nút mới truy nhập - nếu ta di chuyển trái gọi là Zig - Ngược lại, di chuyển phải gọi là Zag

Dịch chuyển : Nếu nút đang xét nằm ở mức sâu hơn hoặc bằng 2 ta dịch chuyển 2 mức mỗi lần

Nếu nút ở mức 1: ta chỉ dịch chuyển 1 mức

Nhận xét cây splay:

- Cây không cân bằng (thường bị lệch) - Các thao tác có thời gian thực hiện khác nhau từ O(1) tới O(n) - Thời gian thực hiện trung bình của 1 thao tác là O(logn) - Thực hiện giống như cây AVL nhưng không cần quản lý thong tin về trạng thái cân bằng của các nút