Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKTREE - Cây nhị phân tìm kiếm

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nktree


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á 231.

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

Được gửi lên bởi:Jimmy
Ngày:2008-12-09
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:PTNK Team Selection 2008

hide comments
2021-05-27 18:03:11
Tham khảo: https://vnspoj.github.io/problems/NKTREE
2017-11-15 17:52:52
In ra YES đc 70 ms vl
2017-11-13 11:32:54
bài này dễ O(n) full dk
2016-07-19 07:47:09
tên đề gợi ý cách làm
2016-07-19 07:45:58
BST AC
2016-05-14 11:52:07
Dùng cây BST AC
2015-10-23 03:39:49
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/10/23/cay-nhi-phan-tim-kiem-nktree/
2015-03-09 08:21:48 Bee
Binary Search Tree
2014-06-20 14:40:55 Nguyễn Tùng Dương
làm mãi mới được 70d. Sao thế nhỉ?
2014-03-18 08:51:40 xxx
procedure nhap;
var i,X:longint;
begin
for i:=1 to maxN do a[i]:=high(longint);
for i:=1 to maxN do read(a[i]);
for i:=1 to maxN do if a[i]=v then break;
n:=i-1
end;

procedure sol: O(n), ăn 70test!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.