Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Splay trong cây ảo (Virtual Tree) trong Cấu trúc dữ liệu

Trong cây ảo (virtual tree), một số cạnh được coi là rắn (solid) và một số là nét đứt (dashed). Splay thông thường chỉ thực hiện trong các cây rắn (solid trees). Để splay tại nút y trong cây ảo, phương pháp sau được dùng.

Thuật toán nhìn vào cây ba lần, mỗi lần một lượt (pass), và thay đổi nó.

Thuật toán Splay(y)

Lượt 1 (Pass 1) Duyệt lên cây ảo, nhưng splay chỉ thực hiện trong các cây con rắn. Bắt đầu từ nút y, đường đi từ y đến gốc của toàn bộ cây trở thành nét đứt.

Lượt 2 (Pass 2) Duyệt lên từ nút y, ghép nối (splicing) tại mỗi tổ tiên thích hợp của y. Sau bước này, đường đi từ y đến gốc trở thành rắn. Ngoại trừ nút y và tất cả các con của nó trong cây gốc (trước lượt 1) giờ trở thành con trái.

Lượt 3 (Pass 3) Duyệt lên từ nút y đến gốc, splay theo cách thông thường.

Điều này cho phép tận dụng kiến thức trước để cải thiện ước lượng xác suất. Cho tập lá cho trước. Mục tiêu là xây dựng cây với trọng số đường đi bên ngoài tối thiểu.

Một ví dụ cho dưới đây:

Bảng tần suất chữ cái

Chữ cáizkmcudle
Tần suất272432374242120

Mã Huffman

Chữ cáiTần suấtMãBit
e12001
d421013
l421103
u371003
c3211104
m24111115
k71111016
z21111006

Cây Huffman (cho ví dụ trên) cho bên dưới:

Splay trong cây ảo (Virtual Tree) trong Cấu trúc dữ liệu