JavaScript is required

Khi loại bỏ node x ở cây nhị phân tìm kiếm ta chỉ cần kiểm tra xem:

A.

x có phải là node lá trái của cây nhị phân tìm kiếm hay không.

B.

x có phải là node lá phải của cây nhị phân tìm kiếm hay không.

C.

Sự tồn tại của x trên cây.

D.

Cả 3 phương án a, b, c đều sai.

Trả lời:

Đáp án đúng: D


Khi loại bỏ một node x khỏi cây nhị phân tìm kiếm, ta cần kiểm tra sự tồn tại của x trên cây trước. Nếu x không tồn tại, việc loại bỏ là vô nghĩa. Nếu x tồn tại, các trường hợp sau cần được xem xét: * **x là node lá:** Đơn giản chỉ cần loại bỏ x khỏi cây. * **x có một con:** Thay x bằng con của nó. * **x có hai con:** Tìm node kế cận (in-order successor) của x (node nhỏ nhất lớn hơn x) hoặc node tiền nhiệm (in-order predecessor) của x (node lớn nhất nhỏ hơn x), thay giá trị của x bằng giá trị của node này, và sau đó loại bỏ node kế cận hoặc node tiền nhiệm này. (Lưu ý rằng node kế cận và node tiền nhiệm chắc chắn có tối đa một con).

Câu hỏi liên quan