Nguồn: wcipeg
Với một đồ thị bất kì, nếu 2 trong 3 mệnh đề sau là đúng, thì mệnh đề còn lại là đúng:
Điều đó có nghĩa là, chỉ cần thỏa 2 trong 3 điều kiện đó thì đồ thị chắc chắn sẽ là một cây, và cây đó sẽ thỏa cả 3 điều kiện trên (trừ cây rỗng - cây không có đỉnh nào).
Ngoài ra, nếu mỗi cặp đỉnh của đồ thị đều có chính xác 1 đường đi thì đồ thị là cây và ngược lại.
Mọi cây đều là đồ thị phẳng (planar graph), nhưng không phải mọi đồ thị phẳng đều là cây.
Cây có gốc (rooted tree) là cây có một đỉnh cụ thể gọi là gốc (root) của cây. Một số cây không có gốc (unrooted tree), có thể là do cây không cần đỉnh nào đặc biệt để làm gốc.
Cho một số thành phố không được nối với nhau, chúng ta muốn xây dựng một số con đường giữa các thành phố sao cho có đúng 1 đường đi giữa mỗi cặp thành phố. Ta sẽ xây dựng những con đường sao cho các thành phố là các đỉnh còn các con đường là các cạnh của cây. Đây là một ví dụ về cây không có gốc, bởi vì chẳng có lí do đặc biệt nào để để đánh dấu một thành phố là gốc cả.
Một vài chú ý:
Ta hoàn toàn có thể coi một cây có gốc là không gốc (bằng cách không quan tâm đỉnh nào là gốc) và ngược lại, coi một cây không gốc là 1 cây có gốc (bằng cách chọn một đỉnh bất kỳ làm gốc).
Trong một cây có gốc, gốc không được coi là lá kể cả khi nó có bậc là 1 (trừ khi cây chỉ có 1 đỉnh). Mặt khác, trong một cây không gốc, mọi đỉnh có bậc 1 được coi là lá.
Mọi đồ thị con liên thông của một cây cũng là một cây và được gọi là cây con (subtree).
Nếu cây có gốc, một đỉnh $u$ và tất cả các hâu duệ của nó được gọi là cây con gốc $u$. (Cây con có gốc ở đỉnh gốc chính là cây ban đầu).
Cây nhị phân (binary tree) là cây có gốc mà mỗi đỉnh có tối đa 2 con, gọi là con trái (left) và phải (right). Cây con có gốc là đỉnh con trái của một đỉnh gọi là cây con trái (left subtree). Cây con phải (right subtree) cũng định nghĩa tương tự. Cây nhị phân được sử dụng rất nhiều ví dụ như trong cây nhị phân tìm kiếm (binary search tree), Heap nhị phân,…
Một cây nhị phân được coi là có vô hạn số tầng (level), nhưng chỉ có một số tầng thường được sử dụng. Mỗi tầng của cây bao gồm tất cả các đỉnh có cùng độ sâu. Tầng $0$ của cây chỉ bao gồm $1$ đỉnh là gốc; tầng thứ nhất chứa những đỉnh con của gốc, như vậy tầng $1$ chứa tối đa $2$ đỉnh; tầng thứ $2$ chứa tất cả đỉnh cháu của gốc (con của con của gốc), như vậy tầng này chứa tối đa $4$ đỉnh;… tổng quát: tầng thứ $h$ của cây nhị phân có thể chứa tới $2^{h}$ đỉnh. Nếu một cây nhị phân có chiều cao $h$ thì số đỉnh tối đa nó có thể chứa là $1 + 2 + 4 + … + 2^{h} = 2^{h+1} - 1$. Mặt khác, cây nhị phân có $N$ đỉnh sẽ có chiều cao ít nhất là $\left \lceil log_2 (N + 1) \right \rceil - 1$.
Một cây nhị phân được gọi là hoàn chỉnh (complete) nếu tất cả các đỉnh từ tầng $0$ đến tầng $h - 1$ đều được sử dụng, và tất cả các đỉnh trên tầng $h$ đều dồn về bên trái nhiều nhất có thể. Một cây nhị phân hoàn chỉnh sẽ luôn có chiều cao thấp nhất có thể có.
Một cây nhị phân gọi là cân bằng (balance) nếu chênh lệnh chiều cao của 2 đỉnh lá bất kì đều không quá 1, nếu tất cả đỉnh lá đều có cùng chiều cao thì nó được coi là hoàn toàn cân bằng (perfectly balanced). Các cây cân bằng thường được sử dụng rất hiệu quả trong việc tìm kiếm dữ liệu.
Tổng quát, một cây k-phân (k-ary tree) là một cây có gốc mà mỗi đỉnh có tối đa k con, các thuật ngữ khác định nghĩa tương tự như cây nhị phân.
Duyệt cây là việc thăm tất cả đỉnh của cây. Liệt kê các đỉnh được thăm theo thứ tự, ta thu được một thứ tự duyệt cây. Nếu một cây có $N$ đỉnh thì sẽ có $N!$ thứ tự duyệt cây. Có 2 cách duyệt quan trọng là duyệt theo thứ tự trước (preoder) và duyệt theo thứ tự sau (postorder).
Trong cách duyệt theo thứ tự trước, chúng ta sẽ thực hiện một phép tìm kiếm theo chiều sâu (DFS) bắt đầu từ đỉnh gốc, mỗi đỉnh sẽ được đánh dấu đã đi qua ngay khi nó được đưa vào stack lần đầu.
DFS(u):
preorder <- u
for v in children(u):
DFS(v)
Phép duyệt theo thứ tự sau cũng tương tự, nhưng khác ở chỗ là một đỉnh được coi là đã thăm ngay khi tất cả các con của nó đã được thăm (các đỉnh lá được đánh dấu đã thăm khi chúng vừa được đưa vào stack vì chúng không có con).
DFS(u):
for v in children(u):
DFS(v)
postorder <- u
Ta có thể định nghĩa thứ tự cho các con của 1 đỉnh: "con thứ nhất", "con thứ hai",… Khi đó, phép duyệt theo thứ tự trước hay sau đều chỉ sinh ra một thứ tự duy nhất.
Ngoài duyệt theo thứ tự trước và sau, cây nhị phân còn có cách duyệt theo thứ tự giữa (inorder traversal). Một đỉnh được coi là đã thăm sau khi tất cả đỉnh thuộc cây con trái của nó được thăm và trước khi bất kì đỉnh nào thuộc cây con phải của nó được thăm. Trình tự duyệt theo thứ tự giữa là duy nhất đối với mỗi cây nhị phân, và duyệt cây nhị phân tìm kiếm theo thứ tự giữa luôn trả về một danh sách đã sắp xếp.
DFS(u)
DFS(u.left_child)
in_order <- u
DFS(u.right_child)
Các cấu trúc dữ liệu sau đều dựa trên cây có gốc, và thường là cây nhị phân:
Cây nhị phân tìm kiếm (binary search tree): nhãn của một đỉnh luôn không nhỏ hơn nhãn của đỉnh con trái của nó (nếu có) và không lớn hơn nhãn của đỉnh con phải của nó (nếu có). Cây 2-3-4 hay B-tree cũng giống vậy, nhưng mỗi đỉnh có thể có hơn 2 con.
Cây phân đoạn (segment tree, range tree hay interval tree): một cây nhị phân quản lý một dãy, với mỗi lá biểu diễn một phần tử của dãy, và giá trị của mỗi đỉnh khác lá là một hàm kết hợp giá trị 2 con của nó.
Binary indexed tree) hay Fenwick tree: cho phép tính toán và truy vấn trên các tiền tố (prefix) của một dãy số.
Parse tree: cây biểu diễn việc phân tích cú pháp của một chuỗi. Khi viết liên tiếp các ký tự trên các lá của cây từ trái sang phải thì ta được chuỗi ban đầu. Mỗi cây con quản lý một đoạn con của chuỗi, và các đỉnh không phải là lá mang thông tin về quan hệ cú pháp giữa các đoạn con mà các con của nó quản lí.
Abstract syntax tree: cũng giống như cây phân tích cú pháp nhưng nó mang thông tin trừu tượng hơn so với cây phân tích cú pháp. Lá của nó mang những khái niệm (concept) cơ bản và các đỉnh lưu giữ quan hệ logic hơn là quan hệ cú pháp của cây phân tích cú pháp (mối quan hệ có nghĩa).
Cây kd (k-dimensional tree hay kd-tree): lưu trữ và quản lý các điểm thuộc không gian k-chiều.
Cây trie hay cây tiền tố (prefix tree): mỗi đỉnh lưu giữ một ký tự và mỗi đường đi từ gốc đến một đỉnh thể hiện một tiền tố của chuỗi.
Tổ tiên chung gần nhất (Lowest Common Ancestor - LCA): cho một cặp đỉnh trên cây, yêu cầu tìm tổ tiên chung thấp nhất của 2 đỉnh này, tức đỉnh thấp nhất là tổ tiên của cả 2 đỉnh này.