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)

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.

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à n₁, n₂,…, n_k lần lượt là gốc của các cây T₁, T₂,…, T_k. 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 n₁, n₂,…, n_k, 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 T₁, T₂,…, T_k 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(T₀)) = 0. T₁, T₂,…, T_n là các cây con của T₀.

Mức(T₁) = Mức(T₂) = … = Mức(T_n) = Mức(T₀) + 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ó 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.

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ó.

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.

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.

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

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

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

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

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