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à gì?

Cây nhị phân là một cấu trúc dữ liệu phân cấp, trong đó mỗi nút có 0, một hoặc nhiều nhất là hai con. Mỗi nút chứa một con trỏ bên trái, một con trỏ bên phải và một phần tử dữ liệu. Con trỏ gốc của cơ sở dữ liệu đại diện cho nút trên cùng của cây. Mỗi nút trong cấu trúc dữ liệu được kết nối trực tiếp với số nút tùy ý ở hai bên, được gọi là con. Một con trỏ null đại diện cho cây nhị phân. Không có thứ tự cụ thể nào về cách các nút được tổ chức trong cây nhị phân. Các nút không có nút con được gọi là nút lá hoặc nút bên ngoài.

Nói một cách đơn giản, nó định nghĩa một hàm ghi nhãn có tổ chức trên các nút, lần lượt gán một số giá trị ngẫu nhiên cho mỗi nút. Bất cứ thứ gì có hai con và một nút cha là một cây nhị phân. Cây nhị phân được sử dụng để lưu trữ thông tin tạo thành một hệ thống phân cấp như hệ thống tệp trên máy tính cá nhân của bạn. Không giống như Mảng, Cây không có giới hạn trên về số lượng nút vì chúng được liên kết bằng cách sử dụng các con trỏ, như Danh sách được liên kết. Các chức năng chính của Cây nhị phân bao gồm biểu diễn dữ liệu phân cấp, sắp xếp danh sách dữ liệu, cung cấp các hoạt động chèn / xóa hiệu quả, v.v. Các nút cây được biểu diễn bằng các cấu trúc trong C.

Cây tìm kiếm nhị phân là gì?

Cây tìm kiếm nhị phân là một loại cấu trúc dữ liệu cây nhị phân, trong đó các nút được sắp xếp theo thứ tự, do đó còn được gọi là cây nhị phân có thứ tự. Đây là một cấu trúc dữ liệu dựa trên nút cung cấp một cách hiệu quả và nhanh chóng để sắp xếp, truy xuất, tìm kiếm dữ liệu. Đối với mỗi nút, các phần tử trong cây con bên trái phải nhỏ hơn hoặc bằng khóa trong nút cha (LP) của nó. Không nên có khóa trùng lặp. Nói một cách đơn giản, đó là một loại cấu trúc dữ liệu cây nhị phân đặc biệt lưu trữ và quản lý hiệu quả các mục trong bộ nhớ.

Nó cho phép truy cập nhanh thông tin, chèn và xóa dữ liệu, ngoài ra nó có thể được sử dụng để thực hiện các bảng tra cứu cho phép tìm kiếm các mục bằng các phím duy nhất của chúng, như tìm kiếm số điện thoại của một người theo tên. Các khóa duy nhất được sắp xếp theo cách có tổ chức, do đó việc tra cứu và các hoạt động động khác có thể được thực hiện bằng cách sử dụng tìm kiếm nhị phân. Nó hỗ trợ ba thao tác chính: tìm kiếm các phần tử, chèn các phần tử và xóa các phần tử. Cây tìm kiếm nhị phân cho phép truy xuất nhanh các phần tử được lưu trữ trong cây vì mỗi khóa nút được so sánh kỹ lưỡng với nút gốc, loại bỏ một nửa cây.

Sự khác biệt giữa cây nhị phân và cây tìm kiếm nhị phân

1. Định nghĩa cây nhị phân và cây tìm kiếm nhị phân - Cây nhị phân là một cấu trúc dữ liệu phân cấp, trong đó một đứa trẻ có thể có 0, một hoặc tối đa hai nút con; mỗi nút chứa một con trỏ trái, một con trỏ phải và một phần tử dữ liệu. Không có thứ tự cụ thể nào về cách các nút nên được tổ chức trong cây. Mặt khác, Cây tìm kiếm nhị phân là một cây nhị phân có thứ tự, trong đó có một thứ tự tương đối về cách các nút nên được tổ chức.
2. Kết cấu của Cây nhị phân và cây tìm kiếm nhị phân- Nút trên cùng trong cây đại diện cho con trỏ gốc trong cây nhị phân, và con trỏ bên trái và bên phải đại diện cho các cây nhỏ hơn ở hai bên. Đây là một dạng cây đặc biệt đại diện cho dữ liệu trong cấu trúc cây. Mặt khác, cây tìm kiếm nhị phân là một loại cây nhị phân trong đó tất cả các nút trong cây con bên trái nhỏ hơn hoặc bằng giá trị của nút gốc và của cây con bên phải lớn hơn hoặc bằng giá trị của nút gốc.
3. Hoạt động của Cây nhị phân và cây tìm kiếm nhị phân- Cây nhị phân có thể là bất cứ thứ gì có hai con và một bố mẹ. Các hoạt động phổ biến có thể được thực hiện trên cây nhị phân là chèn, xóa và truyền tải. Cây tìm kiếm nhị phân là nhiều cây nhị phân được sắp xếp cho phép tra cứu, chèn và xóa các mục nhanh chóng và hiệu quả. Không giống như cây nhị phân, cây tìm kiếm nhị phân giữ các khóa của chúng được sắp xếp, vì vậy việc tra cứu thường thực hiện tìm kiếm nhị phân cho các hoạt động.
4. Các loại của Cây nhị phân và cây tìm kiếm nhị phân- Có nhiều loại cây nhị phân khác nhau, phổ biến là Cây nhị phân Full, Cây hoàn chỉnh nhị phân Cây, Cây hoàn hảo nhị phân Cây, và Cây nhị phân mở rộng. Một số loại cây tìm kiếm nhị phân phổ biến bao gồm cây T, cây AVL, cây Splay, cây Tango, cây Đỏ-Đen, v.v..

Cây nhị phân so với cây tìm kiếm nhị phân: Biểu đồ so sánh

Tóm tắt về Cây nhị phân và Cây tìm kiếm nhị phân

Mặc dù cả hai đều mô phỏng cấu trúc cây phân cấp đại diện cho một tập hợp các nút với mỗi nút đại diện cho một giá trị, chúng khá khác nhau về cách chúng có thể được thực hiện và sử dụng. Cây nhị phân tuân theo một quy tắc đơn giản là mỗi nút cha không có nhiều hơn hai nút con, trong khi đó Cây tìm kiếm nhị phân chỉ là một biến thể của cây nhị phân theo thứ tự tương đối với cách các nút nên được tổ chức trong cây.