An và Hòa cùng tham gia một hoạt động về bài toán trên dãy số. Giả sử các phần từ 45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58 của tập số An giữ được biểu diễn dưới dạng cây nhị phân trong Hình 2...

Hướng dẫn các bước xây dựng cây BST từ dãy số [45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58]:

1. Bắt đầu với 45 là gốc.

2. Chèn 35: 35 < 45, nên 35 là con trái của 45.

3. Chèn 60: 60 > 45, nên 60 là con phải của 45.

4. Chèn 30: 30 < 45 và 30 < 35, nên 30 là con trái của 35.

5. Chèn 46: 46 > 45 và 46 < 60, nên 46 là con trái của 60.

6. Chèn 75: 75 > 45 và 75 > 60, nên 75 là con phải của 60.

7. Chèn 11: 11 < 45 và 11 < 35 và 11 < 30, nên 11 là con trái của 30.

8. Chèn 55: 55 > 45 và 55 < 60 và 55 > 46, nên 55 là con phải của 46.

9. Chèn 65: 65 > 45 và 65 > 60 và 65 < 75, nên 65 là con trái của 75.

10. Chèn 96: 96 > 45 và 96 > 60 và 96 > 75, nên 96 là con phải của 75.

11. Chèn 12: 12 < 45 và 12 < 35 và 12 < 30 và 12 > 11, nên 12 là con phải của 11.

12. Chèn 58: 58 > 45 và 58 < 60 và 58 > 46 và 58 > 55, nên 58 là con phải của 55.

Cây BST sẽ có cấu trúc như sau:

         45

        / \

     35    60

    /     /  \

  30    46    75

 /  \     \  /  \

11  12   55  65  96

              \

              58

Để tìm giá trị khóa 55, ta sẽ làm theo các bước sau:

1. So sánh với nút gốc (45):
   • 55 > 45: đi tới cây con phải (60).
2. So sánh với nút 60:
   • 55 < 60: đi tới cây con trái (46).
3. So sánh với nút 46:
   • 55 > 46: đi tới cây con phải (55).
4. So sánh với nút 55:
   • 55 = 55: tìm thấy giá trị khóa.

Vậy, chỉ cần 4 bước so sánh để tìm ra nút có giá trị khóa 55 trong cây này.