Cấu trúc dữ liệu phân cấp trong Java - Giải mã cấu trúc dữ liệu quan trọng

Cấu trúc dữ liệu phân cấp trong Java

Cấu trúc dữ liệu phân cấp là cấu trúc dữ liệu phi tuyến tính. Các cấu trúc này chủ yếu đại diện cho dữ liệu có chứa mối quan hệ phân cấp giữa các phần tử của nó.

Binary tree - Cây nhị phân trong cấu trúc dữ liệu phân cấp

Binary trees - Cây nhị phân là một cấu trúc trong đó mỗi nút (giao điểm) có thể có nhiều nhất hai nhánh con (hai giao điểm). Trong cây nhị phân, tồn tại một con đường dẫn duy nhất từ nút gốc đến mọi nút khác. Nút trên cùng của cây nhị phân được gọi là nút gốc hoặc nút cha và các nút đền từ nút gốc được gọi là nút con.

Cây nhị phân hoặc rỗng (còn được gọi là cây null) hoặc nó bao gồm một nút gốc cùng với hai nút còn lại, mỗi nút là một cây nhị phân. Mỗi nút trong cây nhị phân có thể có không, 1 hoặc tối đa hai nhánh kế nghiệm hoặc nhánh con tiếp nối. Nhánh cuối được gọi là nhánh lá.

Mô hình cây nhị phân

Đại diện của cây nhị phân trong cấu trúc dữ liệu phân cấp

Mỗi đối tượng trong cây nhị phân được đại diện bởi một con trỏ trên nút trên cùng cùng hai tham chiếu của nút bên trái và bên phải của cây. Nếu các nút trong cây rỗng, tức là nút là thì tham chiếu trái và phải của nó là NULL.

Các phần của cây nhị phân là:

• Dữ liệu
• Tham chiếu đến nút bên trái
• Tham chiếu đến nút bên phải

Trong cây nhị phân, có một số cấp cho mỗi nhánh. Nhánh Root - nhánh gốc ở mức độ 0, khi đó mỗi nhánh con có số cấp lớn hơn cấp độ của nhánh cha một cấp.

Traversing Binary Trees

Traversing Binary Trees là quá trình đi qua cây nhị phân, theo cách đó, nó chỉ đi qua mỗi nút một lần. CÓ ba tiêu chuẩn để đi qua một cây nhị phân:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal

>>> Đọc thêm: Array & ArrayList - Sự khác biệt giữa Array và ArrayList trong Java

Thuộc tính của cây nhị phân

• Số lượng nhánh con của một nút được gọi là bậc của cây. Cây nhị phân là cây bậc 2, vì mỗi nút có thể có tối đa 2 nút con.
• Chiều sâu hoặc chiều cao của cây là số lượng nút tối đa trong một nhánh của nó. Nó luôn luôn nhiều hơn số cấp dài nhất của cây.
• Số nút tối đa ở cấp 'L' là 2 ^ (L-1)
• Số nút tối đa cho cây có chiều cao 'h' là 2 ^ (h - 1)
• Độ phức tạp thời gian của Traversal cây là O (n)

>>> Đọc thêm: Đệ quy trong Java - Tìm hiểu về đệ quy cho người mới bắt đầu

Binary Search Tree (BST)

Binary Search Tree là cấu trúc dữ liệu phân cấp quan trọng nhất khác trong Java. Nó tương tự như cây nhị phân nhưng có một số thuộc tính bổ sung như:

• Giá trị của mỗi nhánh N của cây con bên phải lớn hơn mọi giá trị trong cây con bên trái.
• Giá trị của mỗi nhánh N của cây con bên trái nhỏ hơn mọi giá trị trong cây con bên phải.
• Các cây con bên trái và bên phải là Binary Search Tree.

Sơ đồ mô tả:

Việc sử dụng chính của Binary Search Tree là tìm kiếm các ứng dụng như bản đồ nơi dữ liệu được nhập thường xuyên. Cây tìm kiếm nhị phân cung cấp các tùy chọn tìm kiếm và truy cập nhanh so với danh sách được liên kết.

Thuộc tính của Binary Search Tree :

• Tìm kiếm: O (h)
• Chèn: O (h)
• Xóa: O (h)

trong đó ' h ' là chiều cao của cây.

Tham khảo: Khóa học lập trình Java

Binary Heap

Binary Heap Là một cấu trúc dữ liệu phân cấp khác tương tự như một cây nhị phân hoàn chỉnh với một số thuộc tính bổ sung. Binary Tree hoàn chỉnh là cây nhị phân không có nhánh chỉ có một nhánh con, ngoài trừ mức sâu nhất. Việc sử dụng phổ biến của Binary Heap là triển khai các hàng đợi ưu tiên.

Binary heap có các thuộc tính sau:

• Một Binary heap có thể là một heap tối thiểu hoặc một heap tối đa.
• Trong một binary heap tối thiểu, dữ liệu ở gốc phải nhỏ nhất trong số tất cả dữ liệu có trong binary heap.
• Trong một binary heap tối đa, dữ liệu ở gốc phải là tối đa trong số tất cả dữ liệu có trong binary heap

Ví dụ về Binary Min Heap trong Java.

Ví dụ về Binary Max Heap trong Java

Kết luận:

Trong hướng dẫn này chúng ta đã tìm hiểu về cấu trúc dữ liệu phân cấp trong Java. Mong rằng bạn đã hiểu rõ về các loại cấu trúc dữ liệu như Binary Tree, Binary Search và Binary heap trong Java. Cùng tìm hiểu thêm các kiến thức về Java và các ngôn ngữ lập trình khác qua các khóa học lập trình tại T3H .

>>> Đọc thêm các thông tin về Java trong mục Blog của Viện công nghệ thông tin T3H