Khái niệm cấu trúc dữ liệu dạng cây

Lưu trữ và sắp xếp dữ liệu

Ta có thể chia các cấu trúc dữ liệu ra thành hai loại là tuyến tính và phi tuyến tính.

Cấu trúc dữ liệu tuyến tính bao gồm:

  • Mảng, danh sách liên kết (đơn/kép), vector, ngăn xếp, hàng đợi.

Cấu trúc dữ liệu phí tuyến tính:

  • Trees, đồ thị (graph), mảng đa chiều

Các cấu trúc dữ liệu tuyến tính và phi tuyến tính có sự khác nhau trong cách bố trí, sắp xếp các phần tử dữ liệu trong bộ nhớ.

  • Trong cấu trúc dữ liệu tuyến tính, các phần tử dữ liệu được sắp xếp một cách tuần tự, do vậy chúng dễ dàng thực thi ở bên trong bộ nhớ của máy tính.
  • Với cấu trúc dữ liệu phi tuyến tính. Cách thực hiện chúng trong bộ nhớ phức tạp hơn. Một phần tử dữ liệu có thể gắn tới vài phần tử khác để phản ảnh quan hệ đặc biệt giữa chúng.

Các khái niệm cơ bản về cây

Hình 1: Biểu diễn của một cây

 

Một cây là tập hữu hạn các node và các nhánh nối giữa các node. nếu một cây không rỗng thì các node của nó có đúng duy nhất một nhánh vào (trừ node gốc, không có nhánh đi vào).

Một số khái niệm đặc trưng cho cây:

Nhánh vào (Indegree):

Là nhánh có chiều đi vào một node ( như trong hình trên ta có thấy các nhánh có đánh chiều mũi tên, mũi tên hướng vào node nào thì ta nói nhánh đó là nhánh vào của node).

Ví dụ: Nhánh từ 1 tới 2 là nhánh vào của node số 2.

Nhánh ra (outdegree):

Nhánh đi ra khỏi một node, Nhánh có chiều mũi tên hướng ra khỏi node.

Ví dụ: Nhánh từ 1 tới 2 là nhánh vào của node số 2 nhưng lại là nhánh ra của node số 1.

Bậc (node's degree) của một node:

Số nhánh đi ra từ một node được gọi là bậc của node đó.

Ví dụ: Ở node số 2 có 3 nhánh ra, ta nói node số 2 có bậc là 3.

Bậc (tree's degree) của một cây:

 Là bậc lớn nhất của các node trong cây đó.

Ví dụ: Bậc của cây ở hình 1 là 3, bằng bậc của node số 2, vì node số 2 có bậc lớn nhất trong cây.

Node lá (leaf):

Là node có số nhánh ra bằng 0.

Ví dụ: Trong hính 1 thì các node lá là 4,9,10,6,11,8.

Node gốc:

Là node không có nhánh vào, vì thế nó không phải là node con của bất kỳ node nào khác.

Ví dụ: Trong hình 1, node gốc là node số 1.

Node trong (Internal node):

Là các node nằm giữa node gốc và node lá,có cả các nhánh ra và nhánh vào. Nó không phải node gốc và cũng không phải là các node lá.

Ví dụ: trong hình 1 ở trên thì node trong là các node 2,3,5,7.

Mức của một node (node's level)

Mức của một node bằng mức của node cha công thêm 1. Với mức của node gốc bằng 0.

Ví dụ: Mức của node số 5 sẽ bằng 2 vì,

Mức của node 2 = mức của node 1 (node gốc) + 1 = 1.

Mức của node 5 = mức của node 2 + 1 = 1 + 1 = 2.

Chiều cao của cây (height)

Chiều cao của cây (còn gọi là chiều sâu) là số cạnh từ node gốc tới node lá xa nhất trong cây. Cây chứa duy nhất một node có chiều cao là 0.

(Trong một số tài liệu khác người ta định nghĩa chiều cao của cây nhị phân như sau:

Chiều cao của cây (còn gọi là chiều sâu) là số cạnh từ node gốc tới node lá xa nhất trong cây cộng với 1. Cây chứa duy nhất một node có chiều cao là 1.

Trong khóa học này ta thường áp dụng cách tính chiều cao của cây như ở định nghĩa thứ nhất).

Ví dụ: Chiều cao của cây ở trên hình 1 là 3, bằng số cạnh từ node gốc tới node 9 hoặc 10 hoặc 11.

Đường tới một node (path)

Đường tới một node là đường đi từ node gốc tới node đó, luôn chỉ có duy nhất một đường đi từ gốc tới một node bất kỳ.

Chiều dài đường đi tới một node là số node từ node gốc tới node đó.

Chú ý: Chiều dài đường đi của node gốc luôn bằng 1.

Ví dụ: Trong hình trên, đường đi tới node 11 sẽ là 1 -> 3 -> 7 -> 11, Chiều dài của đường đi là 4

Chiều dài đường đi của một cây

Là tổng tất cả các chiều dài đường đi của tất cả các node trên cây.

Gọi chiều dài tới node bất kỳ trên cây là P(<nodeID>), chiều dài đường đi của cây là P. Ta có, P = P(1) + P(2) + P(3) + P(4) + P(5) + P(6) + P(7) + P(8) + P(9) + P(10) + P(11) = 1 + 2 + 2 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 4 = 32.

Node tiền bối (ancestor) và node hậu bối (descendant)

Node A được gọi là node tiền bối của node B khi trên đường đi từ node gốc tới node B thì phải đi qua node A. Và lúc đó ta gọi node B là hậu bối của node A.

Ví dụ: Trong cây trên có đường đi như sau 1 -> 3 -> 7 -> 11. Ta nói node 3 là tiền bối của 7 và 11. 7 là hậu bối của 3, 11 là hậu bối của 7 và 3.

Node cha và node con

Nếu nhánh ra của node A là nhánh vào của node B thì ta nói node A là cha của node B và node B là con của node A.

Node cha (C) của node A sẽ là node ông của node B, và node B là node cháu của node C.

Kết luận

Có rất nhiều loại cây, và sự phân biệt giữa chúng là dựa vào bậc của từng cây. Trong thực tế cây có rất nhiều ứng dụng, một vài ví dụ tiêu biểu như:

1. Tổ chức file trong máy tính (được tổ chức theo cấu trúc phân cấp).

2. Ứng dụng cho các thuật toán tìm kiếm.

3. Ứng dụng trong cac thuật toán tìm đường.

Trong các loại cây, thì cây nhị phân (cây bậc 2) là cây phổ biến và thông dụng nhất. Chúng thể hiện được những ưu điểm trong việc thực thi tìm kiếm với ốc độ cao, không quá khó để xây dựng. Để tìm hiểu thêm về cây nhị phân, mời các bạn đọc bài sau.

** Nếu bạn muốn viết các nội dung đặt biệt thì hãy làm theo hướng dẫn sau

Xem thêm 10 bình luận
Viết blog mới của bạn
Báo lỗi trang
Đang tải