NKTREE - Cây nhị phân tìm kiếm
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một trong những cấu trúc dữ liệu nổi tiếng để lưu trữ dữ liệu là cây nhị phân tìm kiếm. Mỗi nút trên cây có nhiều nhất là hai nút con và nhiều nhất là một nút cha. Các nút con được chia thành hai loại: nút con trái và nút con phải. Mỗi cây tìm kiếm có một nút không có nút cha gọi là nút gốc, và có ít nhất một nút không có nút con gọi là nút lá. Mỗi một nút có gắn một giá trị nào đó thỏa điều kiện sau: Tại một nút v bất kỳ tất cả các giá trị thuộc cây con trái với gốc v nhỏ hơn giá trị tại nút v, và tất cả các giá trị ở các nút thuộc cây con bên phải với gốc v lớn hơn giá trị tại nút v.
Hình bên dưới mô tả một cây nhị phân tìm kiếm trong đó nút có giá trị 5 là gốc, các nút với giá trị 2, 4 và 8 là các nút lá.
Đường đi trên cây là dãy các giá trị tại các nút liên tiếp, trong đó mỗi nút sau là nút con trực tiếp của nút trước đó.
Yêu cầu: Cho một dãy gồm các giá trị đôi một khác nhau. Hãy cho biết tồn tại hay không cây tìm kiếm nhị phân, mà trên đó tồn tại một đường đi với dãy giá trị tương ứng là dãy đã cho.
Ví dụ, tồn tại cây nhị phân tìm kiếm với dãy 5 1 3 2, còn không tồn tại cây nhị phân tìm kiếm với dãy 5 2 3 1.
Dữ liệu
Lần lượt liệt kê các giá trị của dãy đã cho. Hai phân tử được ghi cách nhau bởi khoảng trắng hoặc dấu xuống dòng. Số lượng phần tử của dãy không vượt quá 50 000 và mỗi phần tử của dãy có giá trị tuyệt đối không vượt quá 2 31 .
Kết quả
Ghi ra từ “YES”, nếu tồn tại cây, tương ứng dãy đã cho hoặc từ “NO” trong trường hợp ngược lại.
Ví dụ
Dữ liệu 5 1 3 2 Kết quả YES Dữ liệu 5 2 3 1 Kết quả NO
- Người up: paulmcvn
- Nguồn bài: PTNK Team Selection 2008