JavaScript is required

Khi thực hiện việc thêm một node x vào cây nhị phân tìm kiếm ta chỉ cần:

A.

Tìm vị trí thích hợp cho nhánh cây con bên phải.

B.

Tìm vị trí thích hợp cho x trên toàn bộ cây.

C.

Tìm vị trí thích hợp cho nhánh cây con ở bên trái.

D.

Không ý nào đúng.

Trả lời:

Đáp án đúng: B


Trong cây nhị phân tìm kiếm (Binary Search Tree - BST), việc thêm một node mới (x) đòi hỏi phải tìm vị trí thích hợp cho node đó trên toàn bộ cây, sao cho vẫn đảm bảo tính chất của BST: tất cả các node con bên trái của một node đều có giá trị nhỏ hơn node đó, và tất cả các node con bên phải đều có giá trị lớn hơn node đó. Do đó, ta cần duyệt cây từ gốc xuống dưới để tìm vị trí phù hợp cho x. Phương án A, C chỉ xét một nhánh (trái hoặc phải) là không đủ. Phương án D sai vì có một đáp án đúng. Do đó, đáp án đúng là B.

Câu hỏi liên quan