Sử dụng Object References để tạo Tree?

Giả sử chúng ta có một cấu trúc dữ liệu dạng tree. Đây là một hệ thống phân cấp tổ chức, phân tích dự án,...

Trong lập trình, các bạn sẽ gặp phổ biến khi lưu trữ thông tin ở dạng object, đặc biệt là có mối quan hệ one-to-many.


const data = [
  { id: 56, parentId: 62 },
  { id: 81, parentId: 80 },
  { id: 74, parentId: null },
  { id: 76, parentId: 80 },
  { id: 63, parentId: 62 },
  { id: 80, parentId: 86 },
  { id: 87, parentId: 86 },
  { id: 62, parentId: 74 },
  { id: 86, parentId: 74 },
];

Ở đây, việc chúng ta muốn chuyển mảng đối tượng này sang dạng tree thì sẽ như thế nào? Chúng ta có cần phải dùng đến đệ quy và O(n) không?

Phân tích chút

Trên đây, mỗi phần tử mảng (Mỗi vòng tròn) là một node. Một node có thể là cha của nhiều node và là con của một node. Như trên thì ta có: node 86 là cha của node 80 và node 87, node 86 là con của node 74 và node 74 chính là gốc.

Phương pháp

Phương pháp để xây dựng tree

Lặp lại mảng data.
Tìm phần tử cha của phần tử hiện tại.
Trong đối tượng của phần tử cha, hãy thêm một tham chiếu đến phần tử con.
Nếu không có phần tử gốc cho một phần tử, thì đó sẽ là phần tử "gốc" của tree.

Chúng ta phải nhận ra rằng các tham chiếu sẽ được duy trì trong object tree, đó là lý do tại sao chúng ta có thể thực hiện điều này trong thời gian O(n)!

Tạo vị trí ID-to-Array

Tạo tham chiếu mỗi ID tới mảng. Sẽ giúp chúng ta tham chiếu đến gốc của phần tử đó.


const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  return acc;
}, {});

Kết quả sẽ thu về được:


{
  56: 0,
  62: 7,
  63: 4,
  74: 2,
  76: 3,
  80: 5,
  81: 1,
  86: 8,
  87: 6,
};

Tạo Tree

Trước hết ta lặp lại các đối tượng và chỉ định tham chiếu cho phần tử gốc. Ở trên đây mình sử dụng idMapping để xác định vị trí gốc.


let root;
data.forEach(el => {
  // Xử lý phần tử gốc
  if (el.parentId === null) {
    root = el;
    return;
  }
  // Sử dụng mapping để xác định vị trí phần tử cha
  const parentEl = data[idMapping[el.parentId]];
  // Thêm `el` hiện tại của chúng ta vào mảng `con` của thèn cha nó
  parentEl.children = [...(parentEl.children || []), el];
});

Và thế là hết...! Gọi console.log của thằng root xem thế nào.


console.log(root);

Tèn ten...! Kết quả là...


{
  id: 74,
  parentId: null,
  children: [
    {
      id: 62,
      parentId: 74,
      children: [{ id: 56, parentId: 62 }, { id: 63, parentId: 62 }],
    },
    {
      id: 86,
      parentId: 74,
      children: [
        {
          id: 80,
          parentId: 86,
          children: [{ id: 81, parentId: 80 }, { id: 76, parentId: 80 }],
        },
        { id: 87, parentId: 86 },
      ],
    },
  ],
};

10 vạn câu hỏi vì sao?

Tại sao nó lại hoạt động?

Haizz! Cách tốt nhất để hiểu tại sao nó lại hoạt động như thế. Bạn chỉ cần nhớ rằng mỗi phần tử của dữ liệu data chúng tham chiếu đến một đối tượng trong bộ nhớ đó. Ở đây biến el trong vòng lặp forEach đang tham chiếu đến một đối tượng trong bộ nhớ (Đối tượng tương ứng trong bộ nhớ mà mảng dữ liệu phần tử đang tham chiếu) và parentEl cũng tham chiếu đến một đối tượng trong bộ nhớ (Một lần nữa, một trong những đối tượng đang được tham chiếu trong mảng dữ liệu).

Nếu một đối tượng trong bộ nhớ có một mảng tham chiếu con, thì những đối tượng con đó có thể có tham chiếu mảng con khác của riêng chúng.

Tác giả: Jos Hoàng Tiên