Cấu trúc liên kết cây là một loại cấu trúc đặc biệt trong đó nhiều yếu tố kết nối được sắp xếp giống như các nhánh của cây. Ví dụ, cấu trúc liên kết cây thường được sử dụng để tổ chức các máy tính trong mạng công ty hoặc thông tin trong cơ sở dữ liệu.

Trong cấu trúc liên kết cây, chỉ có một kết nối giữa hai nút được kết nối. Bởi vì bất kỳ hai nút nào cũng có thể chỉ có một kết nối lẫn nhau, các cấu trúc liên kết cây tạo thành một hệ thống phân cấp cha và con tự nhiên.

Trong các mạng máy tính, một cấu trúc liên kết cây cũng được gọi là cấu trúc liên kết bus sao . Nó kết hợp các yếu tố của cả cấu trúc liên kết xe buýt và cấu trúc liên kết sao. Dưới đây là một sơ đồ mạng ví dụ về cấu trúc liên kết cây, trong đó các nút trung tâm của hai mạng sao được kết nối với nhau.

Trong hình trên, nếu cáp chính hoặc đường trục giữa mỗi trong hai mạng cấu trúc liên kết sao bị lỗi, các mạng đó sẽ không thể liên lạc với nhau. Tuy nhiên, các máy tính trên cùng một cấu trúc liên kết sao vẫn có thể giao tiếp.

Cấu trúc liên kết cây trong lập trình máy tính

Trong lập trình máy tính, cấu trúc liên kết cây có thể được sử dụng để cấu trúc nhiều loại dữ liệu, bao gồm cả chính chương trình máy tính.

Ví dụ, đây là một chương trình máy tính đơn giản được viết bằng Lisp:

 (+ 1 2 (nếu (> p 10) 3 4)) 

Chương trình này cho biết "Nếu p lớn hơn 10, hãy thêm các số 1, 2 và 3. Nếu không, hãy thêm các số 1, 2 và 4." Giống như tất cả các chương trình Lisp, nó có cấu trúc cấu trúc liên kết cây vốn có. Nếu chúng ta vẽ nó dưới dạng biểu đồ, nó trông giống như cái cây được hiển thị ở bên phải. Đại diện cho một chương trình theo cách này có thể hữu ích vì nó cho thấy rõ tất cả các hoạt động và dữ liệu được kết nối như thế nào.

Các chương trình trong loại cấu trúc này cũng có công dụng đặc biệt. Ví dụ, các kỹ thuật lập trình di truyền có thể phát triển các chương trình máy tính mới bằng cách trao đổi các nhánh giữa các chương trình hiện có cấu trúc như cây.

Cấu trúc liên kết cây trong cây nhị phân

Cây nhị phân là một cấu trúc liên kết cây trong đó mỗi nút có tối đa hai con. Các nút con được dán nhãn là "con trái" hoặc "con phải". Kiểu cấu trúc dữ liệu này thường được sử dụng để sắp xếp và tìm kiếm lượng lớn dữ liệu. Trong cây nhị phân được hiển thị bên dưới, mỗi con trái của cha mẹ có giá trị nhỏ hơn con phải.

Cây B

Cây B là một biến thể của cây nhị phân được phát minh bởi Rudolf Bayer và Ed McCreight tại Boeing Labs vào năm 1971. Các nút của nó có con nằm trong phạm vi tối thiểu và tối đa được xác định trước, thường là từ 2 đến 7. Một cây B đơn giản đồ thị có thể trông giống như hình ảnh dưới đây.

Cây B là "tự cân bằng", nghĩa là chiều cao của các nhánh được quản lý để chúng không bị lớn tùy ý. Mỗi nút chứa phân vùng "giá trị khóa" cho biết giá trị của con. Thiết kế của chúng được tối ưu hóa để xử lý các tệp dữ liệu rất lớn và để ghi dữ liệu vào bộ nhớ hoặc đĩa. Chúng được sử dụng rộng rãi trong các hệ thống cơ sở dữ liệu như MySQL, PostgreSQL và Redis và các hệ thống tệp như NTFS, HFS + và ext4.

Điều khoản mạng, cấu trúc liên kết