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
- Kỹ thuật xoay kép
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.
