Cây nhị phân là gì?

Một cây nhị phân là một loại cấu trúc dữ liệu được sử dụng trong lập trình máy tính để lưu trữ, sắp xếp và truy cập thông tin.Cây nhị phân là loại cây đơn giản nhất, nhưng rất hữu ích và dễ thực hiện.Một triển khai điển hình của một cây nhị phân dựa trên một nút gốc được liên kết với một loạt các nút tạo nên chính cây bằng các biến con trỏ.Loại cây này xuất phát từ tên của nó từ thực tế là không có nút nào trong cây có thể có nhiều hơn hai đứa trẻ. Các cấu trúc dữ liệu cây có nhiều giống.Chúng được tạo thành từ các nút khác nhau, được tổ chức theo mô hình phân cấp.Một nút duy nhất, gốc, là điểm truy cập mà qua đó toàn bộ cây dữ liệu có thể được tìm kiếm hoặc thao tác.Nút gốc này chỉ vào nút trên cùng trong chính cây.

Bất kỳ nút nào trong cây, lưu cho nút trên cùng, sẽ có một nút cha được đặt phía trên nó trong hệ thống phân cấp của cây.Nó cũng có thể có các nút trẻ em, nằm bên dưới nó.Một nút nhất định được truy cập thông qua các nút ở trên nó trong cây và cung cấp quyền truy cập vào những người bên dưới nó. Các cấu trúc dữ liệu cây nhị phân cho phép mỗi nút có không quá hai đứa trẻ.Do đó, một nút nhất định có thể không có nút 0, hoặc hai nút trẻ em được gắn vào nó.Cây nhị phân thông thường cho phép các nút với bất kỳ số lượng trẻ em nào tại bất kỳ điểm nào trên cây.Chúng cũng không có giới hạn về cách các giá trị được lưu trữ trong các nút bao gồm một cây được sắp xếp. Cấu trúc dữ liệu hữu ích nhất khi chúng cải thiện tốc độ mà dữ liệu có thể được truy cập bởi máy tính và các phiên bản được sửa đổi của cây nhị phân được sử dụng để sử dụngcải thiện hiệu quả của họ.Một cây tìm kiếm nhị phân là một trong đó tất cả các giá trị dữ liệu nằm ở nhánh giảm dần bên trái từ một nút nhất định có các giá trị bằng hoặc nhỏ hơn giá trị được lưu trữ trong nút đó.Các giá trị ở phía bên phải của một nút trong một cây nhị phân được đặt hàng phải, phải đến lượt nó lớn hơn giá trị trong nút cơ sở.Đặt hàng dữ liệu này cho phép viết thuật toán tìm kiếm hiệu quả hơn nhiều. Hình dạng của cây nhị phân cũng rất quan trọng trong việc xác định hiệu quả của thuật toán tìm kiếm.Sự đa dạng ít hiệu quả nhất của một cây nhị phân là một trong đó mỗi nút chỉ có một đứa trẻ.Một máy tính có thể cần kiểm tra mọi mục dữ liệu trong toàn bộ cây để xác định vị trí một mẩu thông tin duy nhất trong cấu hình này.Ngược lại, cây nhị phân hiệu quả nhất là một trong đó mọi nút đều lưu cho những người ở dưới cùng của cây có hai đứa trẻ và nơi tất cả các nút lá, các nút dưới cùng trong cây, có cùng khoảng cách so với gốc.