Cây nhị phân tìm kiếm (Binary Search Tree – BST) trên tập $n$ khóa số nguyên là một cây nhị phân thỏa mãn: Mỗi nút chứa đúng một khóa và khóa trong một nút lớn hơn mọi khóa trong nhánh con trái và nhỏ hơn mọi khóa trong nhánh con phải. Có nhiều cấu trúc BST để biểu diễn một tập các khóa. Như hình dưới đây là hai BST biểu diễn tập các khóa $\{1,2,3,4,5,6\}$.

Quá trình tìm kiếm một giá trị $x$ trên BST thực hiện như sau: Bắt đầu từ nút gốc, tại mỗi bước, $x$ được so sánh với khóa tại nút đang đứng ($y$):

• Nếu $x=y$, quá trình tìm kiếm kết thúc, kết luận $x$ có trong BST
• Nếu $x<y$, đi sang nhánh con trái và quá trình tìm kiếm tiếp tục trong cây con trái bằng cách tương tự
• Nếu $x>y$, đi sang nhánh con phải và quá trình tìm kiếm tiếp tục trong cây con phải bằng cách tương tự

Nếu tại một bước nào đó, thuật toán không thể đi tiếp được theo luật trên, quá trình tìm kiếm dừng và kết luận $x$ không có trong BST.
Chi phí một phép tìm kiếm giá trị $x$ bằng số phép so sánh khóa được thực hiện trong thuật toán. Như ở hình trên, để tìm khóa $3$ trong cây (a) ta cần $3$ phép so sánh trong khi đó để tìm khóa $3$ trong cây (b) ta chỉ cần $2$ phép so sánh.
Yêu cầu: Cho $n$ khóa đánh số từ $1$ tới $n$ theo thứ tự tăng dần của các khóa, biết rằng người ta thực hiện $c_i$ lần phép tìm kiếm khóa $i$ trên cấu trúc BST biểu diễn tập khóa này ($\forall i = 1,2,...,n$). Hãy tìm cấu trúc BST sao cho tổng chi phí các phép tìm kiếm là nhỏ nhất.

6
4 9 5 1 3 2 

48