Trong các ứng dụng xử lý dữ liệu cây (Tree Data), việc sử dụng đệ quy để tính toán độ sâu (Depth) của cây có thể gặp rủi ro gì về mặt bộ nhớ khi cây bị mất cân bằng nghiêm trọng (Skewed Tree)?

Question

Accepted Answer

Khi cây bị mất cân bằng nghiêm trọng (ví dụ: mỗi nút chỉ có một nút con duy nhất), cấu trúc cây sẽ trở thành một danh sách liên kết dài. Nếu sử dụng đệ quy, mỗi lần gọi hàm sẽ tạo một Stack Frame mới trong Call Stack. Với độ sâu lớn, ứng dụng sẽ gặp lỗi Stack Overflow. Giải pháp tối ưu là sử dụng vòng lặp (Iteration) với Stack thủ công hoặc chuyển đổi thuật toán sang duyệt theo chiều rộng (BFS) nếu không cần thiết phải dùng đệ quy.

Trong các ứng dụng xử lý dữ liệu cây (Tree Data), việc sử dụng đệ quy để tính toán độ sâu (Depth) của cây có thể gặp rủi ro gì về mặt bộ nhớ khi cây bị mất cân bằng nghiêm trọng (Skewed Tree)?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi recursion liên quan cùng chủ đề