Sự khác biệt giữa cây nhị phân và cây tìm kiếm nhị phân
Share
Sự khác biệt chính - Cây nhị phân đấu với 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ấu trúc dữ liệu sẽ 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 trong một 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à nguồn gốc. Mỗi nút có thể có tối đa hai nút. Chúng được gọi là hạch 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 cây. Cây nhị phân là một loại 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 đó con trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút cha và ở đó con phải chỉ chứa các nút có giá trị lớn hơn nút cha. Đó là sự khác biệt chính. Không giống như các 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.
NỘI DUNG
1. Tổng quan và sự khác biệt chính
2. Cây nhị phân là gì
3. Cây tìm kiếm nhị phân là gì
4. Điểm tương đồng giữa Cây nhị phân và Cây tìm kiếm nhị phân
5. So sánh cạnh nhau - Cây nhị phân vs Cây tìm kiếm nhị phân ở dạng bảng
6. Tóm tắt
Cây nhị phân là gì?
Khi sắp xếp dữ liệu trong cấu trúc cây, nút ở đầu cây được gọi là nút gốc. Chỉ có thể có một gốc cho toàn bộ cây. Bất kỳ nút nào ngoại trừ nút gốc có một cạnh hướng lê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 trái và nút con phải. Một nút không có bất kỳ nút con nào được gọi là một cuống lá. Không có cách cụ thể để 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. Phần tử 2, ở ngọn cây, là gốc. 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 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 sang nút khác, luôn có một đường dẫn. 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 thể 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 tin của máy tính. Cấu trúc dữ liệu 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à 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 có một cạnh hướng lên một nút. Nó được gọi là nút cha. Nút bên dưới được cho kết nối bởi cạnh xuống của nó đượ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 một nút con trái và nút con phải. Phần tử trên cùng được gọi là nút gốc. Con trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút cha. Đứa trẻ bên phải chỉ chứa các nút có giá trị lớn hơn hoặc bằng nút cha.
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 trái trong khi 6 là nút con phải. Con 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ó phần tử nhỏ hơn hoặc bằng 3. Trong ví dụ này, nó là 1. 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 là 6. Tương tự, 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?
- 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 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 vs 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 đó con trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút cha và ở đó con phải chỉ chứa các nút có giá trị lớn hơn nút cha. |
| 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 thành phần dữ liệu. |
| Sử dụng | |
| Cây nhị phân được sử dụng như một tra cứu hiệu quả dữ liệu và thông tin 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 lược - Cây nhị phân đấu với Cây tìm kiếm nhị phân
Một 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 trong một 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 loại 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 đó con trái chỉ chứa các nút có giá trị nhỏ hơn hoặc bằng nút cha và ở đó con phải chỉ chứa các nút có giá trị lớn hơn nút cha.
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 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
Tài liệu tham khảo:
1. Điểm, Hướng dẫn. Cây cấu trúc dữ liệu và thuật toán dữ liệu.
2. Phân biệt giữa cây nhị phân và cây tìm kiếm nhị phân. | javopedia.Net, Javopedia.net, ngày 15 tháng 2 năm 2017. Có sẵn tại đây
Hình ảnh lịch sự:
1.'Binary tree'By Derrick Coetzee - Công việc riêng, (Tên miền công cộng) qua Commons Wikimedia
2.'Bộ tìm kiếm nhị phân'By Không có tác giả nào có thể đọc được bằng máy. (dựa trên khiếu nại bản quyền)., (Miền công cộng) qua Commons Wikimedia
