Một điểm khác biệt giữa cây B và cây nhị phân là cây B phải có tất cả các nút con của nó ở cùng cấp độ trong khi cây nhị phân không có ràng buộc như vậy. Cây nhị phân có thể có tối đa 2 cây con hoặc nút trong khi trong cây B có thể có M không có cây con hoặc nút trong đó M là thứ tự của cây B.
Biểu đồ so sánh
| Cơ sở để so sánh | Cây B | Cây nhị phân |
|---|---|---|
| Hạn chế thiết yếu | Một nút có thể có tối đa số M của các nút con (trong đó M là thứ tự của cây). | Một nút có thể có tối đa 2 số cây con. |
| Đã sử dụng | Nó được sử dụng khi dữ liệu được lưu trữ trên đĩa. | Nó được sử dụng khi các bản ghi và dữ liệu được lưu trữ trong RAM. |
| Chiều cao của cây | log M N (trong đó m là thứ tự của cây M-way) | đăng nhập 2 N |
| Ứng dụng | Mã cấu trúc dữ liệu lập chỉ mục trong nhiều DBMS. | Tối ưu hóa mã, mã hóa Huffman, v.v. |
Định nghĩa cây B
Cây B là cây M-way cân bằng và còn được gọi là cây sắp xếp cân bằng. Nó tương tự như cây tìm kiếm nhị phân nơi các nút được tổ chức trên cơ sở truyền tải theo thứ tự. Độ phức tạp không gian của cây B là O (n). Độ phức tạp thời gian chèn và xóa là O (log n).
Có một số điều kiện nhất định phải đúng với cây B:
- Chiều cao của cây phải nằm tối thiểu nhất có thể.
- Phía trên lá của cây, không nên có bất kỳ cây con trống nào.
- Lá của cây phải ở cùng cấp độ.
- Tất cả các nút nên có số lượng trẻ em ít nhất ngoại trừ các nút để lại.
Tính chất của cây B của đơn hàng M
- Mỗi nút có thể có số M con tối đa và số M / 2 con tối thiểu hoặc bất kỳ số nào từ 2 đến tối đa.
- Mỗi nút có một khóa nhỏ hơn trẻ em với các phím M-1 tối đa.
- Việc sắp xếp các khóa theo một số thứ tự cụ thể trong các nút. Tất cả các khóa trong cây con có ở bên trái của khóa là tiền thân của khóa và khóa có ở bên phải của khóa được gọi là kế.
- Tại thời điểm chèn một nút đầy đủ, cây chia thành hai phần và khóa có giá trị trung bình được chèn tại nút cha.
- Hoạt động hợp nhất diễn ra khi các nút bị xóa.
Định nghĩa cây nhị phân
Cây nhị phân là một cấu trúc cây có thể có nhiều nhất hai con trỏ cho các nút con của nó. Điều đó có nghĩa là mức độ cao nhất mà một nút có thể có là 2 và cũng có thể có nút 0 hoặc một độ.
Có một số biến thể nhất định của cây nhị phân như cây nhị phân nghiêm ngặt, cây nhị phân hoàn chỉnh, cây nhị phân mở rộng, v.v.
- Cây nhị phân nghiêm ngặt là một cây trong đó mỗi nút không đầu cuối phải có cây con trái và cây con bên phải.
- Một cây được gọi là cây nhị phân hoàn chỉnh khi nó thỏa mãn điều kiện có 2 i nút ở mỗi cấp trong đó i là cấp.
- Nhị phân luồng là một cây nhị phân bao gồm 0 không có nút hoặc 2 số nút.
Kỹ thuật truyền tải
Tree traversal là một trong những hoạt động thường xuyên nhất được thực hiện trên cấu trúc dữ liệu cây, trong đó mỗi nút truy cập chính xác một lần theo cách có hệ thống.
- Inorder- Trong cây này đi qua cây con bên trái được truy cập đệ quy sau đó nút gốc được truy cập và trong cây con bên phải cuối cùng được truy cập.
- Preorer- Trong cây này đi qua nút gốc được truy cập lúc đầu sau đó là cây con bên trái và ở cây con bên phải cuối cùng.
- Postorder- Kỹ thuật này truy cập cây con bên trái sau đó cây con bên phải và tại nút gốc cuối cùng.
Sự khác biệt chính giữa cây B và cây nhị phân
- Trong cây B, số nút con tối đa mà nút không đầu cuối có thể có là M trong đó M là thứ tự của cây B. Mặt khác, một cây nhị phân có thể có tối đa hai nút con hoặc nút con.
- Cây B được sử dụng khi dữ liệu được lưu trữ trong đĩa trong khi cây nhị phân được sử dụng khi dữ liệu được lưu trữ trong bộ nhớ nhanh như RAM.
- Một lĩnh vực khác của ứng dụng cho B-tree là cấu trúc dữ liệu lập chỉ mục mã trong DBMS, ngược lại, cây nhị phân được sử dụng trong tối ưu hóa mã, mã hóa huffman, v.v.
- Chiều cao tối đa của cây B là log M N (M là thứ tự của cây). Ngược lại, chiều cao tối đa của cây nhị phân là log 2 N (N là số nút và cơ sở là 2 vì nó dành cho nhị phân).
Phần kết luận
Cây B được sử dụng trên cây tìm kiếm nhị phân và nhị phân, lý do chính đằng sau đó là hệ thống phân cấp bộ nhớ trong đó CPU được kết nối với bộ đệm với các kênh băng thông cao trong khi CPU được kết nối với đĩa thông qua kênh băng thông thấp. Cây nhị phân được sử dụng khi các bản ghi được lưu trữ trong RAM (nhỏ và nhanh) và cây B được sử dụng khi các bản ghi được lưu trữ trong đĩa (lớn và chậm). Vì vậy, sử dụng cây B thay vì cây nhị phân làm giảm đáng kể thời gian truy cập vì yếu tố phân nhánh cao và giảm chiều cao của cây.
