Đồ thị không có chu trình được gọi là đồ thị mạch hở. Tree là một đồ thị xoay chiều hoặc đồ thị không có chu trình.
Tree hay các General Tree được định nghĩa là một tập hợp hữu hạn không rỗng của các phần tử được gọi là đỉnh hoặc nút có đặc tính là mỗi nút có thể có bậc nhỏ nhất là bậc 1 và bậc lớn nhất là n. Nó có thể được phân chia thành n + 1 tập con rời rạc sao cho tập con đầu tiên chứa gốc của Tree và n tập con còn lại bao gồm các phần tử của n Tree con.
Directed Trees – Cây có hướng
Tree có hướng là một đồ thị có hướng xoay chiều. Nó có một nút với Tree thời hạn 1, trong khi tất cả các nút khác có Tree số không xác định 1 như được hiển thị trong hình:
Nút có độ lớn hơn 0 được gọi là nút bên ngoài hoặc nút đầu cuối hoặc lá. Các nút có độ lớn hơn hoặc bằng một được gọi là nút bên trong.
Ordered Trees – cây có thứ tự
Nếu trong một Tree ở mỗi cấp, một thứ tự được xác định, thì một Tree như vậy được gọi là Tree có thứ tự.
Ví dụ: Các Tree trong hình vẽ là cùng một Tree nhưng có thứ tự khác nhau.
Thuộc tính của Tree
Cây là một cấu trúc dữ liệu phân cấp và không tuần tự được sắp xếp theo hình thái giống như cây trong tự nhiên. Dưới đây là một số thuộc tính và khái niệm cơ bản liên quan đến cây:
- Đỉnh (Node): Mỗi nút trong cây được gọi là một đỉnh hoặc một nút. Mỗi đỉnh chứa một giá trị dữ liệu và có thể có các đỉnh con.
- Cạnh (Edge): Các cạnh là các liên kết giữa các đỉnh trong cây. Mỗi cạnh kết nối một đỉnh cha với một đỉnh con.
- Đỉnh Gốc (Root): Đỉnh gốc là đỉnh đầu tiên của cây. Nó là mức cao nhất trong cây và không có đỉnh cha.
- Đỉnh Con (Children): Đỉnh con của một đỉnh là các đỉnh được liên kết trực tiếp từ đỉnh cha đó.
- Đỉnh Cha (Parent): Đỉnh cha của một đỉnh là đỉnh trực tiếp kết nối với đỉnh đó.
- Đỉnh Anh Chị Em (Siblings): Các đỉnh con của cùng một đỉnh cha được gọi là các đỉnh anh chị em.
- Đỉnh Lá (Leaf): Các đỉnh lá là các đỉnh không có đỉnh con. Chúng là các đỉnh cuối cùng của cây.
- Mức (Level): Mức của một đỉnh là số cạnh trên đường đi từ đỉnh gốc đến đỉnh đó. Mức của đỉnh gốc là 0 và mức của các đỉnh con tăng dần.
- Chiều Cao (Height): Chiều cao của cây là mức cao nhất trong tất cả các đỉnh. Nó đo đạc số cạnh trên đường đi từ đỉnh gốc đến đỉnh lá xa nhất.
- Cây Con (Subtree): Cây con là một cây nhỏ nằm bên trong một cây lớn hơn. Nó được hình thành bởi một đỉnh gốc và tất cả các đỉnh con của nó.
Các thuộc tính và khái niệm này là cơ bản và cung cấp một cách để mô tả và tương tác với cây trong cấu trúc dữ liệu và thuật toán.
- Chỉ có một đường đi giữa mỗi cặp đỉnh của Tree.
- Nếu một đồ thị G thì có một và chỉ một đường đi giữa mỗi cặp đỉnh G là một Tree.
- Một Tree T với n đỉnh có n-1 cạnh.
- Biểu đồ là một Tree nếu và chỉ khi nó là một Tree tối thiểu được kết nối.
Xem thêm Adversarial Search trong AI
Rooted Trees
Nếu một Tree có hướng có chính xác một nút hoặc đỉnh được gọi là gốc có độ tới là 0 và tất cả các đỉnh khác có bậc tới là một, thì Tree được gọi là Tree có gốc.
Lưu ý:
- Tree không có nút là Tree có gốc (Tree rỗng)
- Một nút đơn không có nút con là Tree có gốc.
Độ dài cạnh của một Đỉnh
Độ dài đường đi của một đỉnh trong Tree gốc được định nghĩa là số cạnh trong đường đi từ gốc đến đỉnh.
Ví dụ: Tìm độ dài đường đi của các nút b, f, l, q như trong hình:
Giải:
- Độ dài đường đi của nút b là một.
- Độ dài đường đi của nút f là hai.
- Chiều dài đường đi của nút l là ba
- Chiều dài đường đi của nút q là bốn.
Xem thêm Spanning Tree – cây khung
Các loại cây phổ biến
Có nhiều loại cây phổ biến trong lĩnh vực khoa học máy tính và cấu trúc dữ liệu. Dưới đây là một số loại cây phổ biến:
- Cây nhị phân (Binary Tree): Cây nhị phân là một loại cây mà mỗi đỉnh có tối đa hai đỉnh con. Cây nhị phân có thể được phân loại thành cây nhị phân tìm kiếm, cây nhị phân cân bằng, cây nhị phân huffman, vv.
- Cây tìm kiếm nhị phân (Binary Search Tree): Cây tìm kiếm nhị phân là một loại cây nhị phân mà ở đó giá trị của mỗi đỉnh con bên trái nhỏ hơn giá trị của đỉnh cha, và giá trị của mỗi đỉnh con bên phải lớn hơn giá trị của đỉnh cha.
- Cây B (B-Tree): Cây B là một cây nhị phân cân bằng với khả năng chứa nhiều giá trị hơn mỗi đỉnh. Nó được sử dụng rộng rãi trong cơ sở dữ liệu và hệ thống tệp.
- Cây AVL (AVL Tree): Cây AVL là một cây nhị phân cân bằng trong đó độ cao của cây con trái và cây con phải của mỗi đỉnh không vượt quá 1. Điều này đảm bảo rằng cây AVL luôn cân bằng và tối ưu cho các thao tác tìm kiếm.
- Cây đỏ-đen (Red-Black Tree): Cây đỏ-đen là một loại cây nhị phân cân bằng với một số quy tắc màu sắc được áp dụng cho các đỉnh. Quy tắc này đảm bảo rằng cây luôn cân bằng và có thời gian chạy tối ưu cho các thao tác tìm kiếm và cập nhật.
- Cây Trie: Cây Trie (còn được gọi là cây tiền tố) là một loại cây mà các đỉnh biểu diễn các chuỗi ký tự. Nó thường được sử dụng để tìm kiếm và lưu trữ từ điển hoặc các cấu trúc dữ liệu liên quan đến văn bản.
- Cây đa cấp (Multiway Tree): Cây đa cấp là một loại cây mà mỗi đỉnh có thể có nhiều hơn hai đỉnh con. Các cây đa cấp thường được sử dụng trong cấu trúc dữ liệu dạng cây như cây Trie và cây huffman.
Đây chỉ là một số loại cây phổ biến, và còn nhiều loại cây khác nhau tùy thuộc vào mục đích sử dụng và yêu cầu của bài toán cụ thể. Mỗi loại cây có đặc điểm và ứng dụng riêng, và việc lựa chọn loại cây phù hợp là tùy thuộc vào yêu cầu và ràng buộc của bài toán.
Xem thêm Traversing Binary Trees
