Cây nhị phân hoàn chỉnh vs Cây nhị phân đầy đủ
Cây nhị phân là cây mà mỗi nút có một hoặc hai nút con. Trong cây nhị phân, một nút không thể có nhiều hơn hai nút con. Trong cây nhị phân, các con được đặt tên là con "trái" và "phải". Các nút con chứa một tham chiếu đến cha mẹ của chúng. Cây nhị phân hoàn chỉnh là cây nhị phân trong đó mọi cấp của cây nhị phân đều được lấp đầy hoàn toàn ngoại trừ cấp cuối cùng. Ở cấp độ chưa được lấp đầy, các nút được gắn bắt đầu từ vị trí ngoài cùng bên trái. Cây nhị phân đầy đủ là cây trong đó mỗi nút trên cây có hai nút con ngoại trừ các lá của cây.
Cây nhị phân đầy đủ là gì?
Cây nhị phân đầy đủ là cây nhị phân trong đó mọi nút trong cây có chính xác không hoặc hai nút con. Nói cách khác, mọi nút trong cây ngoại trừ các lá đều có đúng hai nút con. Hình 1 dưới đây mô tả một cây nhị phân đầy đủ. Trong một cây nhị phân đầy đủ, số nút (n), số rãnh (l) và số nút bên trong (i) có liên quan theo một cách đặc biệt sao cho nếu bạn biết bất kỳ một trong số chúng, bạn có thể xác định hai nút còn lại các giá trị như sau:
1. Nếu một cây nhị phân đầy đủ có i nút bên trong:
- Số lá l=i + 1
- Tổng số nút n=2i + 1
2. Nếu một cây nhị phân đầy đủ có n nút:
- Số nút bên trong i=(n-1) / 2
- Số lá l=(n + 1) / 2
3. Nếu một cây nhị phân đầy đủ có l lá:
- Tổng số nút n=2l-1
- Số nút bên trong i=l-1
Cây Nhị phân Hoàn chỉnh là gì?
Như trong hình 2, một cây nhị phân hoàn chỉnh là một cây nhị phân trong đó mọi cấp của cây đều được điền đầy đủ ngoại trừ cấp cuối cùng. Ngoài ra, ở cấp độ cuối cùng, các nút nên được gắn bắt đầu từ vị trí ngoài cùng bên trái. Một cây nhị phân hoàn chỉnh có chiều cao h thỏa mãn các điều kiện sau:
- Từ nút gốc, mức trên mức cuối cùng đại diện cho một cây nhị phân đầy đủ có chiều cao h-1
- Một hoặc nhiều nút ở cấp độ cuối cùng có thể có 0 hoặc 1 nút con
- Nếu a, b là hai nút ở cấp trên cấp cuối cùng, thì a có nhiều nút con hơn b nếu và chỉ khi a nằm bên trái của b
Sự khác biệt giữa Cây nhị phân hoàn chỉnh và Cây nhị phân đầy đủ là gì?
Cây nhị phân hoàn chỉnh và cây nhị phân đầy đủ có sự khác biệt rõ ràng. Trong khi cây nhị phân đầy đủ là cây nhị phân trong đó mọi nút đều có 0 hoặc hai nút con, cây nhị phân hoàn chỉnh là cây nhị phân trong đó mọi cấp của cây nhị phân đều được lấp đầy hoàn toàn ngoại trừ cấp cuối cùng. Một số cấu trúc dữ liệu đặc biệt như đống cần phải là cây nhị phân hoàn chỉnh trong khi chúng không cần phải là cây nhị phân đầy đủ. Trong một cây nhị phân đầy đủ, nếu bạn biết tổng số nút hoặc số đường đi hoặc số nút bên trong, bạn có thể tìm thấy hai nút còn lại rất dễ dàng. Nhưng một cây nhị phân hoàn chỉnh không có thuộc tính đặc biệt liên quan đến ba thuộc tính này.
