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
• 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

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.