Cấu trúc dữ liệu dạng cây là gì? Đặc điểm của cây nhị phân (Binary Tree)

Đây là bài 16/18 bài của series môn học Cấu trúc dữ liệu và giải thuật

1. Cấu trúc dữ liệu dạng cây là gì?

Cây (tree) là một cấu trúc dữ liệu gồm một tập hữu hạn các nút, giữa các nút có một quan hệ phân cấp, gọi là quan hệ “cha – con”. Trong cây, có một nút đặc biệt, không có nút cha, gọi là gốc nút (root) của cây.

Minh họa tree

Nếu cây mà không có nút nào thì ta gọi là cây rỗng (null tree).

Có thể định nghĩa cây (tree) như sau:

Ta xem mỗi nút là một cây và là gốc của cây đó.

Giả sử, ta có một nút n và n1, n2,…, nk lần lượt là gốc của các cây T1, T2,…, Tk. Các cây này đôi một không có nút chung. Nếu cho nút n trở thành cha của các nút n1, n2,…, nk, ta sẽ được một cây mới T. Cây này có nút n là gốc còn các cây T1, T2,…, Tk trở thành các cây con (subtree) của gốc.

Tại sao cần sử dụng cấu trúc dữ liệu cây

Array, linked list, stack và queue đều là cấu trúc dữ liệu tuyến tính, lưu trữ dữ liệu tuần tự. Thời gian xử lý trên các cấu trúc dữ liệu này sẽ tăng lên nhiều khi kích thước dữ liệu tăng lên. Còn các cấu trúc dữ liệu dạng cây khác nhau cho phép truy cập dữ liệu nhanh hơn và dễ dàng hơn vì nó là cấu trúc dữ liệu phi tuyến tính.

Một số khái niệm cơ bản về cây

Bậc của một nút: là số cây con của nút đó.

Bậc của một cây: là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây).

Nút gốc: là nút không có nút cha.

Nút lá: là nút không có nút con (có bậc bằng 0).

Nút nhánh (nút trong): là nút không phải nút gốc cũng không phải nút lá.

Mức của một nút:

Quy định mức (nút gốc(T0)) = 0. T1, T2,…, Tn là các cây con của T0.

Mức(T1) = Mức(T2) = … = Mức(Tn) = Mức(T0) + 1.

Chiều cao của cây: h = mức lớn nhất của một nút trong cây + 1.

Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ nút gốc đến x.

Các khái niệm của tree

Có nhiều cấu trúc dữ liệu dạng cây như cây nhị phân tìm kiếm (Binary Search Tree), AVL Tree, B Tree,…

2. Đặc điểm của cây nhị phân

Cây nhị phân là cây có đặc điểm:

    • Mọi nút trên cây chỉ có tối đa 2 nhánh con
    • Với mỗi nút, phân biệt cây con trái và cây con phải của nút đó

Một số dạng đặc biệt của cây nhị phân

Cây nhị phân đầy đủ (full binary tree): tất cả các nút đều có 0 nút con hoặc 2 nút con.

Full binary tree

Cây nhị phân hoàn chỉnh (complete binary tree): giống cây nhị phân đầy đủ nhưng nút cha của các nút lá có ít nhất 1 nút con (1 nút con cũng được hoặc có 2 nút con). Nếu nút cha của nút lá chỉ có 1 nút lá thì nút lá này phải nằm bên trái của nó.

Complete binary tree

Cây nhị phân hoàn hảo (perfect binary tree): mỗi nút nhánh đều có đúng hai nút con và tất cả các nút lá đều ở cùng một mức.

Perfect binary tree

Cây nhị phân suy biến (degenerate binary tree): các nút không phải là nút lá chỉ có một nhánh con.

Degenerate binary tree

Một số tính chất của cây nhị phân

Số nút nằm ở mức i <= 2i.

Số nút lá <=  2h-1 (với h là chiều cao của cây).

Chiều cao của cây h >=  log2(n) + 1 với n là số nút trong cây.

Số nút trong cây <=  2h-1.

5/5 - (1 bình chọn)
Bài trước và bài sau trong môn học<< Hàng đợi (queue) là gì? Cách xây dựng hàng đợiCác thao tác cơ bản trên cây nhị phân (Binary Tree) >>
Chia sẻ trên mạng xã hội:

Tác giả Vinh Lê

Vinh Lê hiện đang là biên tập viên tại Góc Học IT.

Bài viết của Vinh Lê

Trả lời

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.