Cây B so với cây nhị phân

NộI Dung

Nội dung: Sự khác biệt giữa cây B và cây nhị phân
Biểu đồ so sánh
Cây B
Cây nhị phân
Sự khác biệt chính
Phần kết luận
Video giải thích

Sự khác biệt giữa cây B và cây nhị phân là cây B là cây được sắp xếp trong đó các nút được sắp xếp theo thứ tự trong khi cây nhị phân là cây có thứ tự có một con trỏ ở mỗi nút.

Cấu trúc dữ liệu là các khái niệm quan trọng nhất trong lập trình máy tính và trong cấu trúc dữ liệu, hai khái niệm quan trọng nhất là cây B và cây nhị phân. Cả hai đều khác nhau. Cây B là một cây được sắp xếp trong đó các nút được sắp xếp theo thứ tự trong khi cây nhị phân là cây có thứ tự có một con trỏ ở mỗi nút. Cây B và cây nhị phân là các cấu trúc dữ liệu phi tuyến tính. Theo tên, cả hai thuật ngữ có vẻ giống nhau, nhưng chúng không giống nhau vì chúng khác nhau. Mã cây nhị phân được lưu trữ trong RAM trong khi mã cây B được lưu trữ trong đĩa.

Cây B là cây M-way được cân bằng, cây B được gọi là cây sắp xếp cân bằng. Có inorder traversal trong B-cây. Độ 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). Trong cây B, chiều cao của cây nên tối thiểu nhất có thể. Trong cây B, không nên có cây con trống. Tất cả các lá của cây nên ở cùng một cấp độ. Mỗi nút có thể có số lượng trẻ em M tối đa và số lượng trẻ em M / 2 tối thiểu. Mỗi nút trong B-tree nên có ít khóa hơn khóa con. Trong cây B, các khóa trong cây con có ở bên trái của khóa là tiền thân. Khi một nút đầy, và bạn cố gắng chèn một nút mới, cây được chia thành hai phần. Bạn có thể hợp nhất các nút trong cây B cho đến khi các nút bị xóa.

Cây nhị phân có hai con trỏ chứa địa chỉ của các nút con của nó. Có các loại 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 ... Trong cây nhị phân nghiêm ngặt, phải có cây con trái và cây con bên phải, trong một cây nhị phân hoàn chỉnh, cần có hai nút tại mỗi cấp độ và trong cây nhị phân luồng, nên có 0 đến 2 số nút. Nếu chúng ta nói về các kỹ thuật chuyển đổi ngang, ba kỹ thuật chuyển đổi theo thứ tự là ngang, đặt hàng trước và ngang theo thứ tự.

Nội dung: Sự khác biệt giữa cây B và cây nhị phân

Biểu đồ so sánh
Cây B
Cây nhị phân
Sự khác biệt chính
Phần kết luận
Video giải thích

Biểu đồ so sánh

Nền tảng	Cây B	Cây nhị phân
Nền tảng	Cây B là một cây được sắp xếp trong đó các nút được sắp xếp theo thứ tự truyền tải.	Cây nhị phân là cây có thứ tự có một con trỏ ở mỗi nút.
Cửa hàng	Mã cây B được lưu trữ trong đĩa.	Mã cây nhị phân được lưu trữ trên RAM
Chiều cao	Chiều cao của cây B sẽ là log N	Chiều cao của cây nhị phân sẽ là log₂ N
Ứng dụng	DBMS là ứng dụng của B-cây.	Mã hóa Huffman là một ứng dụng od Binary Tree.

Cây B

Trong cây B, không nên có cây con trống. Tất cả các lá của cây nên ở cùng một cấp độ. Mỗi nút có thể có số lượng trẻ em M tối đa và số lượng trẻ em M / 2 tối thiểu. Mỗi nút trong B-tree nên có ít khóa hơn khóa con. Trong cây B, các khóa trong cây con có ở bên trái của khóa là tiền thân. Khi một nút đầy, và bạn cố gắng chèn một nút mới, cây được chia thành hai phần. Bạn có thể hợp nhất các nút trong cây B cho đến khi các nút bị xóa.

Cây nhị phân

Cây nhị phân có hai con trỏ chứa địa chỉ của các nút con của nó. Có các loại 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.

Trong cây nhị phân nghiêm ngặt, phải có cây con trái và cây con bên phải, trong cây nhị phân hoàn chỉnh, cần có hai nút ở mỗi cấp và trong cây nhị phân có luồng, cần có 0 đến 2 số nút. Nếu chúng ta nói về các kỹ thuật chuyển đổi ngang, có ba kỹ thuật chuyển đổi theo thứ tự là ngang, đặt hàng trước và chuyển đổi theo thứ tự sau.

Sự khác biệt chính

Cây B là một cây được sắp xếp trong đó các nút được sắp xếp theo thứ tự trong khi cây nhị phân là cây có thứ tự có một con trỏ ở mỗi nút.
Mã cây B được lưu trữ trong đĩa trong khi mã cây nhị phân được lưu trữ trên RAM.
Chiều cao của cây B sẽ là logN trong khi chiều cao của cây nhị phân sẽ là log₂ N
DBMS là ứng dụng của B-tree trong khi mã Huffman là một ứng dụng od Binary Tree.