Chào ace, bài này chúng ta sẽ tìm hiểu về Các loại Binary Trees trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Trong phần 1 và phần 2 của series bài học về Tree, chúng ta đã được giới thiệu về Binary Tree và các tính chất của nó. Trong bài học mới này, chúng ta sẽ tìm hiểu về các kiểu Binary Trees phổ biến.
Nội dung chính
1. Full Binary Tree – Cây nhị phân đầy đủ
Một Binary Tree được coi là một Full Binary Tree khi mọi node của nó để có 0 hoặc 2 node con. Ta cũng có thể nói, Full Binary Tree là một Binary Tree mà trong đó tất cả các nodes ngoại trừ các nodes lá (leaf nodes) đều có hai node con. Sau đây là các ví dụ về Full Binary Tree.
18
/ \
15 30
/ \ / \
40 50 100 40
18
/ \
15 20
/ \
40 50
/ \
30 50
18
/ \
40 30
/ \
100 40
Trong một Full Binary Tree, số lượng các nodes lá (leaf nodes) bằng với số lượng các nodes bên trong (internal nodes) + 1
L = I + 1
Trong đó L = Số lượng các nodes lá, I = Số lượng các node bên trong
Xem hình sau để hiểu rõ hơn về: root node, internal nodes, và leaf nodes của Binary Tree:
2. Complete Binary Tree – Cây nhị phân hoàn chỉnh
Một Binary Tree được coi là một Complete Binary Tree nếu tất cả các level (cấp) của nó đều được lấp đầy hoàn toàn bởi các nodes, nhưng có thể ngoại trừ level cuối cùng và level cuối cùng có tất cả các nodes càng nằm ở bên trái càng tốt.
Sau đây là các ví dụ về Complete Binary Trees:
18
/ \
15 30
/ \ / \
40 50 100 40
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
Ví dụ thực tế của Complete Binary Tree chính là Binary Heap.
3. Perfect Binary Tree – Cây nhị phân hoàn hảo
Một Binary Tree được coi là một Perfect Binary Tree khi tất cả các internal nodes (các node bên trong) của nó đều có đủ cả hai nodes con và tất cả các node lá (leaf nodes) đều ở cùng một level (cấp).
Sau đây là các ví dụ về Perfect Binary Tree.
18
/ \
15 30
/ \ / \
40 50 100 40
18
/ \
15 30
Một Perfect Binary Tree có chiều cao h (trong đó chiều cao của một Binary Tree được tính bằng con đường dài nhất từ node root đến bất kỳ node lá nào trong Binary Tree) sẽ có 2^(h+1) – 1 nodes.
Một ví dụ về Perfect Binary Tree trong thực tế chính là về các tổ tiên trong gia đình. Giữ một người làm root (gốc), cha mẹ của một gia đình làm một cặp node con, cha mẹ của cha mẹ này lại được coi là các cặp node con, cứ như vậy…
4. Balanced Binary Tree – Cây nhị phân cân bằng
Một Binary Tree được coi là balanced – cân bằng nếu chiều cao của nó là O(Log n) trong đó n là số lượng nodes bên trong Binary Tree. Ví dụ, AVL tree duy trì chiều cao O(Log n) bằng cách đảm bảo rằng sự khác biệt giữa chiều cao của phần cây con bên trái và phần cây con bên phải gần như bằng 1. Red-Black tree duy trì chiều cao O(Log n) bằng cách đảm bảo rằng số lượng các Black nodes (node đen) trên mọi con đường từ node root đến các node lá khác đều bằng nhau, và không có các Red nodes (node đỏ) ở liền kề. Việc sử dụng Balanced Binary Search Tree giúp mang lại ưu điểm rất lớn về hiệu suất, vì chúng cung cấp thời gian O(Log n) cho các tác vụ tìm kiếm, chèn node, và xóa node.
5. Degenerate Tree – Cây nhị phân thoái hóa
Degenerate Tree là một loại cây nhị phân mà mỗi internal node (node ở trong) của nó đều chỉ có một node con. Những cây nhị phân kiểu như vậy có hiệu suất tương tự với Linked List – Danh sách liên kết.
Ví dụ về Degenerate Tree:
10
/
20
\
30
\
40
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ){kind=link}