Sự khác biệt chính - Cây nhị phân và Cây tìm kiếm nhị phân
Cấu trúc dữ liệu là một cách có hệ thống để tổ chức dữ liệu để sử dụng nó một cách hiệu quả. Sắp xếp dữ liệu bằng cách sử dụng cấu trúc dữ liệu nên giảm thời gian chạy hoặc thời gian thực hiện. Ngoài ra, cấu trúc dữ liệu nên yêu cầu một lượng bộ nhớ tối thiểu. Đôi khi dữ liệu có thể được sắp xếp theo cấu trúc cây. Một cây đại diện cho một nút được kết nối bởi các cạnh. Nút trên cùng là nút gốc. Mỗi nút có thể có tối đa hai nút. Chúng được gọi là các nút con. Nút bên trái của nút cha là nút con bên trái trong khi nút ở bên phải của nút cha là nút bên phải. Cây nhị phân và cây tìm kiếm nhị phân là hai cấu trúc dữ liệu dạng cây. Cây nhị phân là một kiểu cấu trúc dữ liệu trong đó mỗi nút cha có thể có nhiều nhất hai nút con. Cây tìm kiếm nhị phân là cây nhị phân trong đó nút con bên trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút mẹ và trong đó nút con bên phải chỉ chứa các nút có giá trị lớn hơn nút mẹ. Đó là điểm khác biệt chính. Không giống như cấu trúc dữ liệu như mảng, cây nhị phân và cây tìm kiếm nhị phân không có giới hạn trên để lưu trữ dữ liệu.
Cây Nhị phân là gì?
Khi sắp xếp dữ liệu theo cấu trúc cây, nút ở trên cùng của cây được gọi là nút gốc. Chỉ có thể có một gốc cho cả cây. Bất kỳ nút nào ngoại trừ nút gốc đều có một cạnh hướng lên trên một nút. Nó được gọi là nút cha. Nút bên dưới mã cha được gọi là nút con của nó. Mỗi nút cha có thể có tối đa hai nút con. Chúng được gọi là nút con bên trái và nút con bên phải. Một nút không có bất kỳ nút con nào được gọi là nút lá. Không có cách cụ thể nào để sắp xếp dữ liệu trong cây nhị phân. Có một đường dẫn từ nút gốc đến mỗi nút.
Hình 01: Ví dụ về Cây nhị phân
Trên đây là một ví dụ về cây nhị phân. Yếu tố 2, ở ngọn cây, là rễ. Mỗi nút có tối đa hai nút. Nếu một cây chứa bất kỳ vòng lặp nào hoặc nếu một nút chứa nhiều hơn hai nút, nó không thể được phân loại là cây nhị phân. Để đi từ nút này đến nút khác, luôn có một con đường. Các nút con của nút gốc 2 là 7 và 5. Cũng có thể một nút không có nút. Nhưng bất kỳ nút nào cũng không được có nhiều hơn hai nút. Phần tử bên phải của gốc là 5. Phần tử 5 đó là nút cha của nút con 9. Nút 4 và 11 không có phần tử con. Do đó, chúng là các nút lá.
Cây nhị phân được sử dụng để lưu trữ dữ liệu theo thứ tự phân cấp. Nó tương tự như cấu trúc tệp của máy tính. Cấu trúc dữ liệu giống như một mảng có thể lưu trữ một lượng dữ liệu cụ thể. Nhưng trong cây nhị phân, không có giới hạn trên về số lượng nút.
Cây Tìm kiếm Nhị phân là gì?
Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cây nhị phân. Tương tự như cây nhị phân, cây tìm kiếm nhị phân cũng có thể có hai nút. Bất kỳ nút nào ngoại trừ nút gốc đều có một cạnh hướng lên trên một nút. Nó được gọi là nút cha. Nút bên dưới một cho trước được kết nối bởi cạnh của nó hướng xuống được gọi là nút con của nó. Một nút không có bất kỳ nút con nào được gọi là nút lá. Mỗi nút cha có thể có tối đa hai nút. Có các nút con tham chiếu đến nút con bên trái và nút con bên phải. Phần tử trên cùng được gọi là nút gốc. Nút con bên trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút cha. Nút con bên phải chỉ chứa các nút có giá trị lớn hơn hoặc bằng nút mẹ.
Hình 02: Ví dụ về Cây Tìm kiếm Nhị phân
Phần tử 8 là phần tử trên cùng. Do đó, nó là nút gốc. Nếu 3 là nút cha, thì 1 và 6 là nút con. Nút 1 là nút con bên trái trong khi nút 6 là nút con bên phải. Nút con bên trái chứa các giá trị nhỏ hơn hoặc bằng nút cha. Khi 3 là nút cha, phía bên trái phải có một phần tử nhỏ hơn hoặc bằng 3. Trong ví dụ này, nó là 1. Nút con bên phải chỉ chứa các nút có giá trị lớn hơn nút cha. Khi 3 là nút cha, nút con bên phải sẽ có giá trị cao hơn 3. Trong ví dụ này, nó là 6. Tương tự như vậy, có một thứ tự nhất định để sắp xếp mỗi phần tử dữ liệu một cây tìm kiếm nhị phân. Đây là một cấu trúc dữ liệu cung cấp một cách hiệu quả để thực hiện sắp xếp, truy xuất và tìm kiếm dữ liệu.
Điểm giống nhau giữa cây nhị phân và cây tìm kiếm nhị phân là gì?
- Cả Cây Nhị phân và Cây Tìm kiếm Nhị phân đều là cấu trúc dữ liệu phân cấp.
- Cả Cây Nhị phân và Cây Tìm kiếm Nhị phân đều có gốc.
- Cả Cây Nhị phân và Cây Tìm kiếm Nhị phân đều có thể có tối đa hai nút con.
Sự khác biệt giữa Cây Nhị phân và Cây Tìm kiếm Nhị phân là gì?
Cây nhị phân và Cây tìm kiếm nhị phân |
|
| Cây nhị phân là một kiểu cấu trúc dữ liệu trong đó mỗi nút cha có thể có tối đa hai nút con. | Cây tìm kiếm nhị phân là cây nhị phân trong đó nút con bên trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút mẹ và trong đó nút con bên phải chỉ chứa các nút có giá trị lớn hơn nút mẹ. |
| Thứ tự sắp xếp dữ liệu | |
| Cây nhị phân không có thứ tự cụ thể để sắp xếp các phần tử dữ liệu. | Cây tìm kiếm nhị phân có một thứ tự cụ thể để sắp xếp các phần tử dữ liệu. |
| Cách sử dụng | |
| Cây nhị phân được sử dụng như một công cụ tra cứu dữ liệu và thông tin hiệu quả trong cấu trúc cây. | Cây tìm kiếm nhị phân được sử dụng để chèn, xóa và tìm kiếm dữ liệu. |
Tóm tắt - Cây nhị phân vs Cây tìm kiếm nhị phân
Cấu trúc dữ liệu là một cách tổ chức dữ liệu. Đôi khi dữ liệu có thể được sắp xếp theo cấu trúc cây. Hai trong số đó là cây nhị phân và cây tìm kiếm nhị phân. Bài viết này đã thảo luận về sự khác biệt giữa cây nhị phân và cây tìm kiếm nhị phân. Cây nhị phân là một kiểu cấu trúc dữ liệu trong đó mỗi nút cha có thể có nhiều nhất hai nút con. Cây tìm kiếm nhị phân là cây nhị phân trong đó nút con bên trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút mẹ và trong đó nút con bên phải chỉ chứa các nút có giá trị lớn hơn nút mẹ.
Tải xuống bản PDF của Cây nhị phân vs Cây tìm kiếm nhị phân
Bạn có thể tải xuống phiên bản PDF của bài viết này và sử dụng nó cho các mục đích ngoại tuyến theo ghi chú trích dẫn. Vui lòng tải xuống phiên bản PDF tại đây: Sự khác biệt giữa Cây nhị phân và Cây tìm kiếm nhị phân
