Trong lĩnh vực khoa học máy tính, cây nhị phân là một cấu trúc dữ liệu cây đặc biệt. Cấu trúc này giúp tổ chức và lưu trữ dữ liệu một cách hiệu quả. Mỗi nút trong cây có thể có tối đa hai nút con được gọi là nút trái và nút phải. Cây nhị phân có thể được định nghĩa thông qua khái niệm các tập hợp và lý thuyết tập hợp. Bên cạnh đó, các tác giả cũng cho phép cây nhị phân có thể là tập hợp trống.
Từ góc độ lý thuyết đồ thị, cây nhị phân cũng được gọi là arborescence phân nhánh đôi. Thuật ngữ này xuất hiện trong các sách lập trình từ rất lâu trước khi thuật ngữ khoa học máy tính hiện đại được sử dụng. Cây nhị phân cũng có thể được hiểu là một đồ thị vô hướng, trong đó cây có gốc và thứ tự. Cây nhị phân là 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
Thuật ngữ về cây nhị phân không được chuẩn hóa tốt và do đó có thể thay đổi trong các tài liệu. Dưới đây là một số loại cây nhị phân thường gặp:
-
Cây nhị phân gốc: Cây có một nút gốc và mỗi nút chỉ có tối đa hai nút con.
Hình ảnh: Cây nhị phân đầy đủ -
Cây nhị phân đầy đủ: Đây là một cây mà mỗi nút có hoặc không có hoặc có đúng hai nút con. Cây nhị phân đầy đủ có thể được định nghĩa bằng cách sử dụng định nghĩa đệ quy. Nó bao gồm một đỉnh đơn lẻ làm nút gốc và một cây có nút gốc có hai nhánh con, cả hai đều là cây nhị phân đầy đủ.
-
Cây nhị phân hoàn hảo: Đây là một cây nhị phân mà tất cả các nút bên trong đều có đúng hai nút con và tất cả các nút lá có cùng độ sâu hoặc cùng cấp độ. Một ví dụ điển hình của 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.
-
Cây nhị phân hoàn chỉnh: Đây là một cây nhị phân trong đó mọi cấp độ, 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 bên trái. Cây nhị phân hoàn chỉnh có thể có từ 1 đến 2^h nút ở cấp cuối cùng, với h là chiều cao của cây.
-
Cây nhị phân cân bằng: Đây là một cấu trúc cây nhị phân trong đó nhánh con trái và nhánh con phải của mỗi nút không chênh lệch về chiều cao quá 1. Điều này giúp tối ưu hóa việc tìm kiếm dữ liệu trong cây.
-
Cây tàu lượn: Đây là một cây mà mỗi nút cha chỉ có một nút con liên quan. Điều này khiến cây hoạt động như một cấu trúc dữ liệu danh sách liên kết.
Tổng kết
Cây nhị phân là một cấu trúc dữ liệu mạnh mẽ và đa dạng. Từ các loại cây nhị phân cơ bản như cây nhị phân đầy đủ đến các biến thể như cây nhị phân hoàn chỉnh và cây nhị phân cân bằng, chúng đóng vai trò quan trọng trong việc tổ chức và quản lý dữ liệu. Hiểu về cấu trúc này sẽ giúp chúng ta áp dụng nó một cách hợp lý trong việc giải quyết các vấn đề liên quan đến dữ liệu.
Nguồn tham khảo:
- Donald Knuth. The Art of Computer Programming vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4.