Biểu diễn Con trái - Anh em phải (Left-Child Right-Sibling) của cây

Khái niệm

Biểu diễn Con trái - Anh em phải là một cách biểu diễn khác của cây n-ary, thay vì giữ con trỏ tới từng nút con, một nút chỉ giữ hai con trỏ: con trỏ đầu tiên tới nút con đầu tiên (left child), con trỏ thứ hai tới anh em kề tiếp ngay (right sibling). Chuyển đổi này không chỉ loại bỏ nhu cầu biết trước số lượng con của một nút, mà còn giới hạn tối đa hai con trỏ mỗi nút, làm cho việc viết code đơn giản hơn nhiều.

Tại mỗi nút, liên kết các con của cùng một cha từ trái sang phải. Cha chỉ liên kết với con đầu tiên.

Ví dụ

Biểu diễn cây Left Child Right Sibling:

10 | 2 -> 3 -> 4 -> 5 | | 6 7 -> 8 -> 9

Ưu điểm

• Tiết kiệm bộ nhớ bằng cách giới hạn tối đa hai con trỏ mỗi nút.
• Đơn giản hơn để viết code.

Nhược điểm

• Các thao tác cơ bản như tìm kiếm/chèn/xóa tốn thời gian dài hơn vì để chọn vị trí chính xác, phải duyệt qua tất cả anh em của nút cần tìm/chèn/xóa (theo trường hợp xấu nhất).