Buzz
Trong lĩnh vực khoa học máy tính, cây nhị phân (tiếng Anh: binary tree) là một cấu trúc dữ liệu dạng cây mà mỗi nút có tối đa hai nút con, được gọi là con trái (left child) và con phải (right child). Một định nghĩa đệ quy sử dụng các khái niệm lý thuyết tập hợp là cây nhị phân không rỗng được biểu diễn như một tuple (L, S, R), với L và R có thể là các cây nhị phân hoặc tập hợp rỗng, và S là tập đơn (singleton set). Một số tác giả cho phép cây nhị phân cũng có thể là tập hợp trống.
Xét từ góc độ lý thuyết đồ thị, cây nhị phân (và K-ary) như định nghĩa ở đây thực sự là arborescence. Do đó, cây nhị phân có thể được gọi là arborescence phân nhánh đôi (bifurcating arborescence)—một thuật ngữ được sử dụng trong các tài liệu lập trình cũ, trước khi các thuật ngữ hiện đại trong khoa học máy tính trở nên phổ biến. Cây nhị phân cũng có thể được coi là một đồ thị vô hướng thay vì có hướng, trong trường hợp đó, cây nhị phân là một cây có gốc và có thứ tự. Một số tác giả dùng thuật ngữ cây nhị phân có gốc thay cho cây nhị phân để nhấn mạnh rằng cây có gốc, nhưng theo định nghĩa đã nêu, cây nhị phân luôn có gốc. Cây nhị phân là một trường hợp đặc biệt của cây K-ary, với k bằng 2.
Các loại cây nhị phân khác nhau
Thuật ngữ về cây không được chuẩn hóa tốt và do đó có sự khác biệt trong các tài liệu.
- Một cây nhị phân gốc có một nút gốc và mỗi nút có tối đa hai nút con.
- Một cây nhị phân đầy đủ (đôi khi được gọi là đúng đắn hay phẳng hoặc cây nhị phân nghiêm ngặt) là một cây mà mỗi nút có hoặc không có hoặc 2 nút con. Định nghĩa khác cho cây nhị phân đầy đủ là một định nghĩa đệ quy. Cây nhị phân đầy đủ bao gồm:
- Một đỉnh đơn lẻ (một nút đơn làm nút gốc).
- Một cây có nút gốc với hai nhánh con, cả hai đều là cây nhị phân đầy đủ.
- Một cây nhị phân hoàn hảo là cây mà tất cả các nút bên trong đều có hai nút con và tất cả các nút lá đều có cùng độ sâu hoặc cùng cấp độ (cấp độ của một nút được xác định là số đường nối từ nút gốc đến nút đó). Một ví dụ về cây nhị phân hoàn hảo là biểu đồ tổ tiên của một người đến một độ sâu nhất định nhỏ hơn mức mà tổ tiên xuất hiện nhiều hơn một lần trong biểu đồ (tại thời điểm này, biểu đồ không còn là một cây có các nút duy nhất; lưu ý rằng cùng một tổ tiên có thể xuất hiện ở các độ sâu khác nhau trong biểu đồ), vì mỗi người có đúng hai cha mẹ sinh học (một mẹ và một cha). Miễn là biểu đồ tổ tiên luôn hiển thị cha và mẹ ở cùng một bên cho một nút nhất định, giới tính của họ có thể được coi là tương đương với nút con trái và phải, con ở đây được hiểu là một thuật ngữ thuật toán. Một cây nhị phân hoàn hảo cũng là một cây nhị phân đầy đủ, nhưng ngược lại không nhất thiết đúng.
- Một cây nhị phân hoàn chỉnh là một cây nhị phân trong đó mọi cấp độ, ngoại trừ có thể là cấp cuối cùng, đều được lấp đầy hoàn toàn và tất cả các nút ở cấp cuối cùng nằm càng bên trái càng tốt. Nó có thể có từ 1 đến 2 nút ở cấp cuối cùng h. Do đó, một cây hoàn hảo luôn luôn là hoàn chỉnh nhưng một cây hoàn chỉnh không nhất thiết hoàn hảo. Một số tác giả sử dụng thuật ngữ hoàn chỉnh để chỉ một cây nhị phân hoàn hảo như được định nghĩa ở trên, trong trường hợp đó họ gọi loại cây này (với một cấp cuối không nhất thiết phải lấp đầy) là cây nhị phân gần như hoàn chỉnh hoặc hầu như hoàn chỉnh. Một cây nhị phân hoàn chỉnh có thể được biểu diễn hiệu quả bằng một mảng.
- Trong cây nhị phân vô hạn hoàn chỉnh, cây có cấp độ, trong đó ở mỗi cấp độ d số nút hiện có là 2. Số lượng phần tử trong tập hợp của tất cả các cấp độ là (vô hạn đếm được). Số lượng phần tử trong tập hợp tất cả các đường đi (các 'lá') là không đếm được, với số lượng liên tục.
- Một cây nhị phân cân bằng là cấu trúc cây mà nhánh con trái và phải của mỗi nút không chênh lệch về chiều cao (số đường nối từ nút gốc đến nút xa nhất trong nhánh) quá 1. Có thể xem xét các cây nhị phân mà không có lá nào xa gốc hơn lá khác.
- Một cây tàu lượn (hoặc bệnh lý) là cây mà mỗi nút cha chỉ có một nút con. Điều này khiến cây hoạt động như cấu trúc dữ liệu danh sách liên kết. Trong trường hợp này, lợi ích của việc sử dụng cây nhị phân giảm đáng kể vì nó thực chất là danh sách liên kết với độ phức tạp thời gian là O(n) (n là số nút), và sử dụng nhiều không gian hơn danh sách liên kết do mỗi nút có hai con trỏ, trong khi độ phức tạp O(log2n) cho tìm kiếm trong cây nhị phân cân bằng thường được kỳ vọng.
