Thuật toán đơn giản tự động căn chỉnh cấu trúc cây

Bài toán đặt ra

Giả sử bạn có một cấu trúc dữ liệu dạng cây:

• Một node gốc (root)

• Mỗi node có thể có nhiều node con

• Không tồn tại chu trình

Mục tiêu là: Tự động tính toán tọa độ cho từng node để hiển thị với các yêu cầu quan trọng:

• Node cùng cấp nằm trên cùng một hàng

• Các nhánh không đè lên nhau

• Layout phải cân đối

Thuật toán

Giải pháp gồm 2 pha chính:

1. Duyệt cây để gán chỉ số (index)

2. Tính toán tọa độ dựa trên index và level

Độ phức tạp tổng thể: $O(n)$

Phase 1: Duyệt DFS để gán chỉ số cho node

Ta sử dụng Depth-First Search (DFS) để duyệt toàn bộ cây.

Ý tưởng:

• Mỗi node sẽ được gán một chỉ số duy nhất

• Node con đầu tiên kế thừa chỉ số của cha

• Các node con sau tăng index lên

updateIndex() {
        for (let i = 0; i < this.children.length; i++) {
            // first child has the same index with its parent's
            // then increase from that
            if (i > 0) TreeNode.nIdx++;
            this.children[i].index = TreeNode.nIdx;
            // DFS
            this.children[i].updateIndex(TreeNode.nIdx);
        }
    }

Mục tiêu của bước này là:

• Tạo thứ tự tuyến tính cho các node lá

• Đảm bảo thứ tự phản ánh cấu trúc DFS của cây

• Chuẩn bị dữ liệu cho bước tính tọa độ

Pha 2: Tính toán tọa độ (x, y) cho từng node

Sau khi có index, duyệt DFS rồi tính vị trí từng node dựa vào node index và loại node

• Nếu node ấy là node lá thì:

  • $node.x = node.idx \times v_{\text{margin}}$

  • $node.y = level \times h_{\text{margin}}$

• Nếu không phải node lá thì

  • $node.x = \frac {firstchild.x + lastchild.x} 2 \times v_{\text{margin}}$

  • $y = level \times h_{\text{margin}}$

layout(hMargin = 25, vMargin = 25) {
        this.y = this.level * hMargin;
        if (this.children.length > 0) {
            for (let i = 0; i < this.children.length; i++) {
                this.children[i].layout();
            }
            this.x = (this.children[0].x + this.children[this.children.length - 1].x) / 2;
        } else {
            this.x = this.index * vMargin;
        }
    }

Demo