Giới thiệu về cây nhị phân
Hình 1: Cây nhị phân
Như đã đề cập về khái niệm cây ở bài trước. Thì cây nhị phân (binary tree) chính là cây có bậc là 2. Có nghĩa là bất kỳ node nào trong cây sẽ có bậc tối đa là hai.
Hầu hết cái khái niệm của cây nhị phân giống hoàn toàn với khái niệm chung của cây như (nhánh vào, nhánh ra, node lá, node gốc, node trong, mức của một node, mức của cây, chiều dài đường đi tới một node, chiều dài đường đi của cả cây, node tiền bối, node hậu bối, node cha, node con, chiều cao của một node, chiều cao của cây …)
Một số khái niệm khác chỉ tồn tại với cây nhị phân đó là cây nhị phân đầy đủ (full binary tree) và cây nhị phân hoàn thiện (complete binary tree).
Cây nhị phân đầy đủ là cây nhị phân mà mỗi node trong cây có chính xác hoặc 0 hoăc 2 con.
Hình 2: Cây nhị phân đầy đủ
Gọi N là số node ,H là chiều cao, và E là hệ số cân bằng của một cây nhị phân.
Với chú ý rằng:
- H = -1 trong trường hợp cây rỗng
- H = 0 trong trường hợp cây có duy nhất 1 node
Ta có những kết luận sau:
|
Quan hệ giữa N và H |
Mô tả |
|
Hmax =N– 1 |
Trường hợp này xảy ra khi cây nhị phân suy biến thành cây dạng tuần tự – giống với danh sách liên kết |
|
Hmin =log2(N+ 1) -1 |
Trong trường hợp cây nhị phân hoàn thiện, ở mỗi mức đều có số lượng tối đa các node |
|
Nmin =H+ 1 |
Trường hợp này xảy ra khi cây nhị phân suy biến thành cây dạng tuần tự – giống với danh sách liên kết |
|
Nmax= 2H + 1– 1 |
Trong trường hợp cây nhị phân hoàn thiện, ở mỗi mức đều có số lượng tối đa các node |
|
E = HL– HR |
Là sự chênh lệch chiều cao của cây con trái và cây con phải.
Một cây được coi là cân bằng khi E = 0 hoặc -1 hoặc 1 |
Cây nhị phân hoàn thiện là cây mà mỗi node của nó có đúng 2 con (trừ node lá), và các node lá có cùng mức, Ta cũng sẽ thấy cây này có hệ số E = 0, tức là độ chênh lệch ở mọi node trong cây đều bằng 0.
Hình 3: Cây nhị phân hoàn thiện
Cây nhị phân hoàn thiện là cây rất đặc biệt. Nó cung cấp tỉ lệ tốt nhất có thể cho hai thông số là tổng số node N và chiều cao H của cây.
Chiều cao H của một cây nhị phân hoàn thiện với N node có giá trị lớn nất là O(log N). Ta có thể chứng minh điều này bằng cách tính số node trên mỗi mức bắt đầu từ node gốc. Ta có:
|
N = 1 + 2 + 4 + … + 2H-1 + 2H= 2H+1– 1 |
Tương ứng với:
|
H = log2(N + 1) – 1 |
Duyệt cây (Tree traversal)
Duyệt cây là một thao tác vô cùng quan trọng đối với cấu trức dữ liệu cây. Cách duyệt cây là tiền đề quan trọng cho các thuật toán như tìm kiếm, tìm đường … về sau này.
Duyệt cây là cách đi qua tất cả các node của cây theo một trình tự nhất định. Khi duyệt qua một node ta đánh dấu node đó là đã duyệt và chỉ xử lý chúng một lần duy nhất.
Đối với danh sách liên kết thì ta phải thực hiện việc duyệt từ node đầu tới node cuối cùng. Với cây thì ta có nhiều phương pháp để duyệt hơn.
Có hai cách duyệt cây phổ biến đó là:
- Duyệt cây theo chiều rộng (Breadth-first traversal)
- Duyệt theo mức (level-order)
- Duyệt cây theo chiều sâu (Depth-first traversal)
- Preorder
- Inorder
- Postorder
Để tìm hiểu rõ hơn về các cách duyệt cây bạn có thể click vào các đường dẫn ở trên. Các bài học sẽ bao gồm tổng quát về cách duyệt cây và cách xây dựng thuật toán duyệt cây với ngôn ngữ sử dụng là C/C++.