Nếu độ lớn hơn của mọi nút nhỏ hơn hoặc bằng 2, trong cây có hướng hơn cây được gọi là Binary Trees. Một cây bao gồm các nút (cây trống) cũng là một Binary Trees.
Binary Trees là gì ?
Binary Trees là một cấu trúc dữ liệu cây đặc biệt trong lập trình và toán học. Nó được gọi là “Binary” vì mỗi nút trong cây có tối đa hai nút con – một nút con trái và một nút con phải. Binary Trees được sử dụng rộng rãi trong các thuật toán tìm kiếm, xử lý cây, cấu trúc dữ liệu và các ứng dụng khác.
Một Binary Tree gồm các thành phần sau:
- Nút gốc: Là nút đầu tiên của cây, không có nút cha.
- Nút con trái: Là nút nằm bên trái của một nút cha.
- Nút con phải: Là nút nằm bên phải của một nút cha.
- Nút lá: Là nút không có con.
- Đường đi: Là chuỗi các nút từ nút gốc đến một nút lá.
- Mức của một nút: Là khoảng cách từ nút đó đến nút gốc.
- Chiều cao của cây: Là mức lớn nhất của các nút trong cây.
Binary Trees có nhiều dạng và loại khác nhau, bao gồm Binary Search Trees, AVL Trees, Red-Black Trees và nhiều hơn nữa. Mỗi loại cây có các thuộc tính và ứng dụng riêng biệt.
Binary Trees được sử dụng để lưu trữ dữ liệu có tổ chức theo cấu trúc cây. Chúng cung cấp khả năng tìm kiếm, thêm, xóa và sắp xếp dữ liệu một cách hiệu quả. Các thuật toán trên Binary Trees như tìm kiếm nhị phân, duyệt cây (preorder, inorder, postorder), cân bằng cây và nhiều thuật toán khác được áp dụng rộng rãi trong lập trình và xử lý dữ liệu.
Với tính chất linh hoạt và hiệu quả trong việc lưu trữ và xử lý dữ liệu, Binary Trees là một cấu trúc dữ liệu quan trọng và cơ bản trong khoa học máy tính và lập trình.
Các bài viết liên quan:
Thuật ngữ cơ bản
Root: Binary Trees có một nút duy nhất được gọi là gốc của cây.
Left Child: Nút bên trái của gốc được gọi là nút con bên trái của nó.
Right Child: Nút ở bên phải của gốc được gọi là nút con bên phải của nó.
Parent Node: Một nút có nút con bên trái hoặc nút con bên phải hoặc cả hai được gọi là nút cha của các nút.
Siblings: Hai nút có cùng cha mẹ được gọi là anh chị em.
Leaf: Một nút không có con được gọi là lá. Số lượng lá trong Binary Trees có thể thay đổi từ một (tối thiểu) đến một nửa số đỉnh (tối đa) trong một cây.
Descendant: Một nút được gọi là con của một nút khác nếu nó là con của nút hoặc con của một số con khác của nút đó. Tất cả các nút trong cây là con cháu của gốc.
Left Subtree: Cây con có gốc là con bên trái của một số nút được gọi là cây con bên trái của nút đó.
Ví dụ: Đối với cái cây như trong hình:
- Nút nào là gốc?
- Những nút nào là lá?
- Đặt tên cho nút cha của mỗi nút
- Binary Trees toán học rời rạc
Giải: (i) Nút A là nút gốc.
(ii) Các nút G, H, I, L, M, N, O là các lá.
(iii) Nodes Parent
B, C A
D, E B
F C
G, H D
I, J E
K F
L, M J
N, O K
Cây con phải: Cây con có gốc là con bên phải của một nút nào đó được gọi là cây con bên phải của nút đó.
Mức của một nút: Mức của một nút là khoảng cách của nó từ gốc. Mức gốc được xác định là không. Cấp của tất cả các nút khác hơn nút cha của nó một bậc. Số nút tối đa ở bất kỳ mức N nào là 2N.
Chiều sâu hoặc Chiều cao của cây: Chiều sâu hoặc chiều cao của cây được định nghĩa là số lượng nút tối đa trong một nhánh của cây. Đây là nhiều hơn mức tối đa của cây, tức là độ sâu của rễ là một. Số nút tối đa trong Binary Trees có độ sâu d là 2d-1, trong đó d ≥1.
Các nút bên ngoài: Các nút không có nút con được gọi là nút bên ngoài hoặc nút đầu cuối.
Các nút bên trong: Các nút có một hoặc nhiều hơn một nút con được gọi là nút bên trong hoặc nút không đầu cuối.
Cấu trúc của Binary Trees
Binary Trees là một cấu trúc dữ liệu cây mà mỗi nút trong cây có tối đa hai nút con – một nút con trái và một nút con phải. Một Binary Tree có thể được định nghĩa như sau:
truct Node {
int data;
Node* left;
Node* right;
};Thuộc tính của Binary Trees:
- Nút gốc (Root): Đây là nút đầu tiên của cây và không có nút cha.
- Nút con (Child): Mỗi nút trong cây có thể có tối đa hai nút con – một nút con trái và một nút con phải.
- Nút lá (Leaf): Là những nút trong cây không có nút con.
- Nút cha (Parent): Là nút trực tiếp trên một nút con.
- Nút anh em (Sibling): Là những nút cùng có cha mẹ.
- Đường đi (Path): Là chuỗi các nút từ nút gốc đến một nút lá.
- Mức (Level): Là vị trí của một nút trong cây, bắt đầu từ 0 với nút gốc.
- Chiều cao (Height): Là mức lớn nhất của các nút trong cây, tính từ nút gốc.
- Cây rỗng (Empty Tree): Là cây không có nút nào.
Các thuộc tính trên giúp xác định quan hệ giữa các nút trong cây và cung cấp thông tin về cấu trúc của Binary Trees. Thuộc tính chiều cao của cây và đường đi từ nút gốc đến các nút lá là những thuộc tính quan trọng để đánh giá hiệu suất và phân tích độ phức tạp của các thao tác trên cây.
Để tận dụng tối đa cấu trúc của Binary Trees, các thuật toán được áp dụng trên nó như tìm kiếm, thêm, xóa, duyệt cây và cân bằng cây.
Binary Expression Trees
Một biểu thức đại số có thể được biểu diễn một cách thuận tiện bằng cây biểu thức của nó. Một biểu thức có các toán tử nhị phân có thể được phân tách thành
<toán hạng bên trái hoặc biểu thức> (toán tử) <toán hạng bên phải hoặc biểu thức>
Tùy thuộc vào mức độ ưu tiên đánh giá.
Cây biểu thức là một Binary Trees có gốc chứa toán tử và cây con bên trái chứa biểu thức bên trái và cây con bên phải chứa biểu thức bên phải.
Ví dụ: Xây dựng cây biểu thức nhị phân cho biểu thức (a + b) * (d / c)
Giải pháp: Cây biểu thức nhị phân cho biểu thức (a + b) * (d / c) được hiển thị trong hình:
Binary Trees hoàn chỉnh: Binary Trees hoàn chỉnh là Binary Trees nếu nó là tất cả các cấp, ngoại trừ có thể là cấp cuối cùng, có số lượng nút tối đa cho bên trái càng tốt. Độ sâu của Binary Trees hoàn chỉnh có n nút là log2 n + 1.
Ví dụ: Cây trong hình là một Binary Trees hoàn chỉnh.
Binary Trees đầy đủ: Binary Trees đầy đủ là Binary Trees trong đó tất cả các lá ở cùng một mức và mọi nút không phải lá đều có hai nút con.
Đặc điểm của Binary Trees
Các đặc điểm của Binary Trees bao gồm:
- Mỗi node trong cây có tối đa hai con: Mỗi node trong cây nhị phân có thể có hoặc không có hai con, một con trái và một con phải.
- Thứ tự giá trị: Các node trong cây nhị phân được sắp xếp theo một số tiêu chuẩn nhất định, chẳng hạn như giá trị tăng dần hoặc giảm dần.
- Duyệt cây: Cây nhị phân có thể được duyệt theo một số cách khác nhau, chẳng hạn như duyệt theo chiều sâu hoặc chiều rộng.
- Tìm kiếm: Cây nhị phân là một cấu trúc dữ liệu tốt cho việc tìm kiếm vì các giá trị trong cây được sắp xếp theo một tiêu chuẩn nhất định.
- Tối ưu hóa: Các thuật toán sử dụng cây nhị phân thường có thể tối ưu hóa về thời gian và không gian, so sánh với các thuật toán khác.
- Cấu trúc đơn giản: Cây nhị phân có cấu trúc đơn giản và dễ hiểu, dễ dàng để xây dựng và chỉnh sửa.
Source code C++ của Binary Trees
Đây là một ví dụ của source code C++ để tạo một Binary Tree:
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
Node *newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main()
{
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "The root data is: " << root->data << endl;
cout << "Left child of root: " << root->left->data << endl;
cout << "Right child of root: " << root->right->data << endl;
return 0;
}Trong đó, một node trong cây được mô tả bằng một cấu trúc có tên Node với 3 thành phần: data lưu giá trị của node, left và right là con trái và con phải của node tương ứng. Hàm newNode được sử dụng để tạo một node mới với giá trị đã cho.
Trong hàm main, chúng ta tạo một node gốc với giá trị 1, và tiếp tục thêm các node con vào cây. Cuối cùng, chúng ta in ra giá trị của node gốc và hai con của nó.
Các loại Binary Trees
Có nhiều loại Binary Trees phổ biến được sử dụng trong lập trình và cấu trúc dữ liệu. Mỗi loại có các đặc điểm và thuộc tính riêng, phù hợp với các ứng dụng và yêu cầu cụ thể. Dưới đây là một số loại Binary Trees quan trọng:
- Binary Search Trees (BST): Là loại cây nhị phân đặc biệt, trong đó giá trị của mỗi nút con trái nhỏ hơn giá trị của nút cha, và giá trị của mỗi nút con phải lớn hơn giá trị của nút cha. BST được sử dụng rộng rãi trong các tìm kiếm và sắp xếp dữ liệu.
- AVL Trees: Là một dạng cân bằng của BST, trong đó chiều cao của cây luôn được duy trì cân bằng. AVL Trees đảm bảo thời gian tìm kiếm và các thao tác trên cây có độ phức tạp trung bình O(log n).
- Red-Black Trees: Là một dạng cân bằng khác của BST, trong đó các nút có màu đỏ hoặc đen. Red-Black Trees cũng đảm bảo chiều cao cây cân bằng và có độ phức tạp trung bình O(log n) cho các thao tác.
- Binary Heap: Là một cây nhị phân đầy đủ có thuộc tính heap, trong đó mỗi nút cha có giá trị lớn hơn (hoặc nhỏ hơn) giá trị của các nút con. Binary Heap được sử dụng trong các thuật toán tìm kiếm đỉnh lớn nhất (Max Heap) hoặc đỉnh nhỏ nhất (Min Heap).
- Cartesian Tree: Là một cây nhị phân được xây dựng từ một dãy số, trong đó giá trị của mỗi nút tương ứng với một phần tử trong dãy. Cartesian Tree có thể được sử dụng để giải các bài toán liên quan đến dãy số.
- Huffman Tree: Là một cây nhị phân đặc biệt được sử dụng trong mã hóa và nén dữ liệu. Huffman Tree gán các mã nhị phân cho các ký tự dựa trên tần suất xuất hiện của chúng.
Đây chỉ là một số loại Binary Trees phổ biến. Có nhiều loại khác nhau như Splay Trees, B Trees, Trie Trees, và nhiều hơn nữa, mỗi loại được thiết kế để giải quyết các vấn đề và ứng dụng cụ thể.
Các thao tác trên Binary Trees
Các thao tác phổ biến trên Binary Trees bao gồm:
- Thêm nút (Insertion): Thêm một nút mới vào cây theo quy tắc của Binary Trees. Nếu giá trị của nút mới nhỏ hơn giá trị nút hiện tại, nút mới được thêm vào nhánh trái; nếu giá trị của nút mới lớn hơn giá trị nút hiện tại, nút mới được thêm vào nhánh phải.
- Xóa nút (Deletion): Xóa một nút khỏi cây. Quy trình xóa có thể phức tạp hơn so với thêm nút, bởi vì cần duy trì tính cân bằng và sắp xếp các nút lại theo quy tắc của cây.
- Tìm kiếm nút (Search): Tìm kiếm một giá trị trong cây. Bắt đầu từ nút gốc, so sánh giá trị cần tìm với giá trị của nút hiện tại. Dựa trên quy tắc của Binary Trees, tiếp tục tìm kiếm ở nhánh trái hoặc phải cho đến khi tìm thấy giá trị hoặc hết nút để tìm kiếm.
- Duyệt cây (Traversal): Là quá trình duyệt qua các nút của cây theo một thứ tự nhất định. Có ba loại duyệt cây chính:
- Pre-order traversal: Duyệt nút gốc trước, sau đó duyệt nhánh trái và sau đó duyệt nhánh phải.
- In-order traversal: Duyệt nhánh trái trước, sau đó duyệt nút gốc và cuối cùng duyệt nhánh phải. Kết quả sẽ được sắp xếp theo thứ tự tăng dần.
- Post-order traversal: Duyệt nhánh trái trước, sau đó duyệt nhánh phải và cuối cùng duyệt nút gốc. Kết quả sẽ được sắp xếp theo thứ tự giảm dần.
- Kiểm tra tính cân bằng (Balanced Check): Kiểm tra xem cây có đạt được tính cân bằng hay không. Tính cân bằng của cây đảm bảo rằng chiều cao của các nhánh con không chênh lệch quá nhiều, giúp cải thiện hiệu suất các thao tác trên cây.
- Tìm kiếm nút lớn nhất và nhỏ nhất: Tìm nút có giá trị lớn nhất và nhỏ nhất
- Kiểm tra tính đầy đủ (Completeness Check): Kiểm tra xem cây có đạt được tính đầy đủ hay không. Tính đầy đủ của cây đảm bảo rằng tất cả các mức của cây đều được đầy đủ nút, trừ một số nút ở mức cuối cùng nếu có.
- Đếm số nút (Count Nodes): Đếm số lượng nút trong cây. Đây là một thao tác đơn giản nhưng quan trọng để biết kích thước của cây.
- Tính chiều cao (Height): Tính toán chiều cao của cây, tức là độ dài đường dài nhất từ gốc đến lá xa nhất. Chiều cao của cây cung cấp thông tin về cấu trúc và hiệu suất của cây.
- Tính tổng giá trị các nút: Tính tổng giá trị của tất cả các nút trong cây. Đây là một thao tác hữu ích khi muốn tính tổng các giá trị hoặc đối tượng trong cây.
- Tìm kiếm tổng các nút con (Sum of Child Nodes): Tính tổng giá trị của các nút con của một nút cho trước. Đây là một thao tác phụ thuộc vào cấu trúc và thuộc tính của cây.
- Kiểm tra tính đối xứng (Symmetry Check): Kiểm tra xem cây có đạt được tính đối xứng hay không. Tính đối xứng của cây xác định xem nhánh trái và nhánh phải của mỗi nút có cấu trúc và giá trị tương tự hay không.
- Tìm kiếm tổng đường đi (Sum of Paths): Tính tổng giá trị của tất cả các đường đi từ gốc đến các lá trong cây. Đây là một thao tác phức tạp yêu cầu duyệt qua tất cả các đường đi trong cây.
- Invert Tree: Đảo ngược cây, tức là hoán đổi nhánh trái và nhánh phải của mỗi nút. Thao tác này thường được sử dụng để thay đổi cấu trúc của cây và tạo ra một cây mới.
Các thao tác trên Binary Trees giúp chúng ta thực hiện các tác vụ như tìm kiếm, thêm, xóa, sắp xếp và thống kê dữ liệu một cách hiệu quả. Chúng cũng có ứng dụng rộng trong các thuật toán và cấu trúc dữ liệu
Hiệu suất của Binary Trees
Hiệu suất của Binary Trees có thể được đánh giá thông qua một số khía cạnh quan trọng sau:
- Thời gian truy cập: Thời gian để tìm kiếm, thêm hoặc xóa một phần tử trong cây. Trong trường hợp tốt nhất, thời gian truy cập là O(log n), trong đó n là số lượng nút trong cây. Tuy nhiên, trong trường hợp tồi nhất, thời gian truy cập có thể là O(n), khi cây không cân bằng.
- Tính cân bằng: Tính cân bằng của cây ảnh hưởng đến hiệu suất của nó. Một cây cân bằng có chiều cao nhỏ hơn, dẫn đến thời gian truy cập tốt hơn và cân bằng hơn trong việc phân chia dữ liệu. Các loại cây cân bằng như AVL Trees hoặc Red-Black Trees có thể cải thiện hiệu suất so với cây nhị phân thông thường.
- Tính đầy đủ: Một cây được coi là đầy đủ khi tất cả các mức (ngoại trừ mức cuối cùng) đều có đủ nút. Cây đầy đủ giúp tối ưu hóa việc lưu trữ và tìm kiếm dữ liệu.
- Duyệt cây: Thời gian duyệt qua tất cả các nút trong cây. Có ba phương pháp duyệt cây chính là Pre-order, In-order và Post-order. Thời gian duyệt cây là O(n), trong đó n là số lượng nút trong cây.
- Khả năng lưu trữ: Binary Trees sử dụng cấu trúc dữ liệu đệ quy, vì vậy sẽ tốn thêm bộ nhớ để lưu trữ các con trỏ và các nút trong cây. Hiệu suất của cây có thể bị ảnh hưởng nếu không đủ bộ nhớ được cấp phát.
Tổng quan, hiệu suất của Binary Trees phụ thuộc vào cấu trúc cây, tính cân bằng và đầy đủ, cùng với thao tác thực hiện trên cây. Việc chọn đúng loại cây phù hợp và thực hiện cân bằng và tối ưu cây đóng vai trò quan trọng trong việc đảm bảo hiệu suất tốt của Binary Trees trong ứng dụng thực tế.
Ứng dụng của Binary Trees
Binary Trees có rất nhiều ứng dụng trong lĩnh vực lập trình và khoa học máy tính. Dưới đây là một số ví dụ phổ biến về ứng dụng của Binary Trees:
- Cây tìm kiếm: Binary Trees được sử dụng rộng rãi trong cấu trúc dữ liệu cây tìm kiếm nhị phân. Các phép toán tìm kiếm, chèn và xóa phần tử có thể được thực hiện hiệu quả trên cây tìm kiếm nhị phân.
- Dự án Huffman: Cây Huffman là một dạng cây nhị phân đặc biệt được sử dụng để nén dữ liệu. Cây Huffman giúp tối ưu hóa việc lưu trữ và truyền tải dữ liệu bằng cách gán mã nhị phân ngắn hơn cho các ký tự xuất hiện thường xuyên.
- Cây AVL: Cây AVL là một loại cây tìm kiếm nhị phân cân bằng. Nó được sử dụng để đảm bảo rằng cây luôn cân bằng và thời gian truy cập là O(log n), nơi n là số lượng nút trong cây. Cây AVL thường được sử dụng trong các ứng dụng yêu cầu tìm kiếm nhanh và cân bằng dữ liệu.
- Xử lý biểu thức số học: Cây biểu diễn biểu thức số học là một dạng cây nhị phân đặc biệt được sử dụng để biểu diễn biểu thức toán học. Các phép toán và toán hạng được lưu trữ trong các nút và cây này được sử dụng để tính toán giá trị biểu thức.
- Cây thư mục: Trong hệ thống tệp và thư mục, cây nhị phân được sử dụng để tổ chức các tệp và thư mục. Mỗi nút trong cây đại diện cho một thư mục và các liên kết giữa các nút đại diện cho quan hệ thư mục con – thư mục cha.
- Cây Genealogical: Cây nhị phân cũng có thể được sử dụng để biểu diễn quan hệ gia đình trong cây gia phả. Mỗi nút đại diện cho một thành viên trong gia đình và quan hệ cha/mẹ và con cái được biểu thị bằng các liên kết giữa các nút.
Phân biệt giữa General Tree và Binary Tree
| General Tree | Binary Tree |
| Không có cây nào như vậy không có nút hoặc một cây tổng quát rỗng. | Có thể có một Binary Trees rỗng. |
| Nếu một số nút có con, thì không có sự phân biệt như vậy. | Nếu một số nút có con, thì nó được phân biệt là nút con bên trái hay nút con bên phải. |
| Những cây trong hình đều giống nhau, khi chúng ta coi chúng là những cây nói chung. | Các cây trong hình là khác biệt, khi chúng ta coi chúng là Binary Trees, vì ở (4) là con bên phải của 2 trong khi ở (ii) 4 là con bên trái của 2. |
Xem thêm Binary Operation
