Computer >> Máy Tính >  >> Lập trình >> Lập trình

Phát cây trong cấu trúc dữ liệu

play tree được định nghĩa là cây tìm kiếm nhị phân tự cân bằng với thuộc tính bổ sung là các phần tử được truy cập gần đây sẽ nhanh chóng truy cập lại. Các thao tác cơ bản như chèn, tra cứu và loại bỏ được thực hiện bởi cây ghép theo thời gian phân bổ O (log n). Đối với nhiều chuỗi hoạt động không ngẫu nhiên, cây splay hoạt động tốt hơn các cây tìm kiếm khác, ngay cả khi mẫu cụ thể của chuỗi không được biết. Tất cả các hoạt động bình thường trên cây tìm kiếm nhị phân được kết hợp với một hoạt động cơ bản, được gọi là ghép nối.

Giả sử rằng đối với mỗi nút a, chúng ta lưu trữ một khóa số thực (a).

Trong bất kỳ cây tìm kiếm nhị phân nào, cây con bên trái của bất kỳ nút nào, a chứa các mục có giá trị "khóa" nhỏ hơn giá trị của khóa (a) và cây con bên phải của nút a chứa các mục có giá trị "khóa" cao hơn giá trị của khóa (a) .

Trong cây splay, trước tiên chúng tôi tìm kiếm mục truy vấn, nói a như trong các cây tìm kiếm nhị phân thông thường— so sánh mục truy vấn với giá trị trong gốc, nếu ít hơn thì tìm kiếm đệ quy trong cây con bên trái, nếu cao hơn thì tìm kiếm đệ quy trong cây con bên phải, và nếu nó bằng nhau thì chúng ta đã hoàn tất. Sau đó, nói một cách chính thống, chúng ta xem xét mọi cặp tổ tiên rời rạc f a, giả sử b =cha (a) và c =cha (b), và thực hiện một số cặp phép quay nhất định. Kết quả của các phép quay này, a thay thế cho c.

Trong trường hợp a có một số lẻ các tổ tiên thích hợp, thì tổ tiên của a (là con của gốc), cũng sẽ phải được xử lý theo cách riêng biệt, trong trường hợp đầu cuối— chúng ta xoay cạnh giữa a và gốc. Bước này được biểu thị là bước zig.

Nếu a và b đều là con trái hoặc đều là con bên phải của cha mẹ tương ứng của chúng, thì trước tiên chúng ta xoay cạnh giữa b và cha c của nó rồi đến cạnh giữa a và cha của nó là b. Bước này được biểu thị là bước zig-zig.

Nếu a là con bên trái (tương ứng bên phải) và b là con bên phải (tương ứng bên trái), thì trước tiên chúng ta xoay cạnh giữa a và b rồi giữa a và c, bước này được ký hiệu là bước zig-zag.