Mô phỏng thuật toán Cây tiền tố · chèn

Trie · Insert · Nhóm: Cấu trúc dữ liệu

Cây tiền tố (Trie) là cây n nhánh lưu tập hợp từ, mỗi cạnh mang một ký tự và đường đi từ gốc tạo thành một từ; các từ chung phần đầu sẽ dùng chung nhánh.

Ý tưởng

Bắt đầu từ nút gốc, duyệt lần lượt từng ký tự của từ cần chèn.

Với mỗi ký tự, nếu chưa có cạnh tương ứng thì tạo nút con mới, nếu đã có thì đi theo cạnh sẵn.

Sau ký tự cuối, đánh dấu nút hiện tại là nút hết-từ để ghi nhận từ đã tồn tại.

Vì sao đúng

Nhiều từ chung tiền tố sẽ chia sẻ chung nhánh nên tiết kiệm bộ nhớ, đồng thời tra cứu và tìm theo tiền tố chỉ tốn thời gian tỉ lệ với độ dài từ.

Mã Python

def insert(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = Node()
        node = node.children[ch]
    node.is_end = True

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.