Tree Datastructure

Dữ liệu dạng cây là dạng dữ liệu thường được thấy ở các ứng dụng như:

• cấu trúc sơ đồ phòng ban, bộ phận của một doanh nghiệp
• danh sách các chuyên mục
• bình luận theo dạng thread-based (vd: fb, tiktok, …)

Điểm chung của cấu trúc dạng cây là mỗi node trên cây thường có một node cha và có từ 0-n node con, các node con cũng có thể có rất nhiều các node con khác tuỳ vào độ sâu của cây. Các node ban đầu (root node) thì không có node cha.

Các khái niệm cơ bản:

• Nút gốc : Là nút trên cùng của cây, nút duy nhất không có nút cha.
• Nút lá : Là các nút có 0 nút con.
• Nút nhánh : Là các nút có cả nút cha và nút con.
• Mức của nút : Là các số nguyên đếm từ 0. Các nút ngang hàng có cùng mức với nhau. Nút gốc có mức là 0, các nút con trực tiếp của gốc có mức là 1 …
• Chiều cao của cây : Là mức của nút là lớn nhất.

Adjacency List (Danh sách kề):

• vd với tính năng comments facebook theo dạng thread-based (người dùng có thể trả lời lẫn nhau vô hạn), tức là mỗi bình luận có thể được trả lời bởi nhiều bình luận khác, tạo ra nhiều các phân lớp khác nhau. Mỗi bình luận (ngoại trừ bình luận gốc) sẽ có duy nhất một bình luận cha.
• theo cách Adjacency List, với mỗi bản ghi của một bình luận sẽ lưu thêm một trường parent_id để trỏ đến bình luận cha của bình luận hiện tại. Nếu bình luận đã là bình luận gốc thì parent_id sẽ được đặt là null.

CREATE TABLE comments (
    comment_id primary key,
    parent_id bigint unsigned,
    comment_date datetime not null,
    comment text not null,
    foreign key (parent_id) references comments(comment_id)
);

• với adjacency list để query node cha hoặc node con trực tiếp khá dễ dàng

select c1.*, c2.*
from comments c1 left join comments c2
on c2.parent_id = c1.comment_id;

• Tuy nhiên để query lấy hết mọi con cháu của một node cha không hề đơn giản.

WITH RECURSIVE menu_tree
    (id, parent_id, level)
AS (
SELECT
    comment_id,
    parent_id,
    0
FROM comments
WHERE parent_id is null

UNION ALL
SELECT
    mn.comment_id,
    mn.parent_id,
    mt.level + 1
FROM comments mn, menu_tree mt
WHERE mn.parent_id = mt.comment_id
)
SELECT * FROM menu_tree
ORDER BY level, parent_id, comment_id;

• Để loại bỏ một node bất kỳ ra khỏi tree, bằng cách thực hiện query như bảng trên và thay parent_id is null thành giá trị muốn loại bỏ để lấy hết con cháu của node đó. Hoặc có thể sử dụng đệ quy để vét cạn.
• Để thêm một node vào vị trí bất kỳ chỉ cần xác định node cha.

Closure Table:

• closure table là cách thêm một bảng phụ làm bảng tham chiếu mối quan hệ ancestor-descendant. Điểm mấu chốt là mối quan hệ ancestor-descendant sẽ lưu lại mọi quan hệ (cha-cha, cha-con, cha-cháu, …) chứ không chỉ lưu mỗi mối quan hệ cha-con trực tiếp.
• Bên cạnh bảng comments, với cách này chỉ cần tạo thêm một bảng phụ TreePaths với các trường ancestor-descendant và lưu lại ở đó các quan cặp quan hệ.

CREATE TABLE comments (
    comment_id primary key,
    comment_date datetime not null,
    comment text not null
);

CREATE TABLE TreePaths (
    ancestor bigint unsigned not null, 
    descendant bigint unsigned not null,
    primary key(ancestor, descendant),
    foreign key (ancestor) references comments(comment_id),
    foreign key (descendant) references comments(comment_id)
);

• Tương ứng với mỗi node, thì ở bảng TreePaths sẽ có một bản ghi chỉ mối quan hệ lên chính node hiện tại, và nhiều bản ghi chỉ mối quan hệ đến mọi descendant của node hiện tại đó. Nhờ đó mà việc truy vấn query node cha, node con trực tiếp sẽ dễ dàng hơn. Ngay cả query lấy hết mọi con cháu cũng đơn giản hơn Adjacency List nhiều.
• vd để tìm các ancestor của comment_id = 6:

select c.*
from comments as c
join TreePaths as t on c.comment_id = t.ancestor
where t.descendant = 6;

• vd để tìm các descendant của comment_id = 4;

select c.*
from comments as c
join TreePaths as t on c.comment_id = t.descendant
where t.ancestor = 4;

• Việc thêm các node cũng dễ dàng hơn. Chỉ có một điều phải lưu ý là khi dữ liệu cây nhiều và sâu hơn thì số lượng bản ghi của TreePath cũng tăng lên rất nhanh, đánh đổi lại việc truy xuất dễ dàng hơn.
• Để loại bỏ một node bất kỳ ra khỏi tree, bằng cách thực hiện query như bảng trên và thay c1.ancestor = 1 thành giá trị muốn loại bỏ để lấy hết con cháu của node đó.

select c1.descendant, c2.descendant
from tree_datastructure.TreePaths c1 left join tree_datastructure.TreePaths c2
on c2.ancestor = c1.descendant 
where c1.ancestor = 1

Hoặc để loại bỏ tất cả row liên quan đến node cần xoá

select *
from tree_datastructure.TreePaths where `descendant = 4` and descendant != ancestor
UNION ALL

select c2.*
from tree_datastructure.TreePaths c1 left join tree_datastructure.TreePaths c2
on c2.ancestor = c1.descendant 
where `c1.ancestor = 4`
order by ancestor, descendant