Khác với Mảng hay Danh sách liên kết vốn lưu trữ dữ liệu theo kiểu tuyến tính (tuần tự), Cây (Tree) là một cấu trúc dữ liệu phi tuyến tính (Non-linear) biểu diễn quan hệ phân cấp (Hierarchical) giữa các phần tử.
[ A ] <-- Root (Gốc) - Bậc 0
/ \
[ B ] [ C ] <-- Node cha của (D,E) và (F) - Bậc 1
/ \ \
[ D ] [ E ] [ F ] <-- Leaf Nodes (Lá) - Bậc 2
Root (Gốc): Nút duy nhất ở đỉnh trên cùng của cây, không có nút cha (Node A).
Parent / Child (Cha / Con): Nút A trỏ trực tiếp xuống Nút B thì A là cha của B, B là con của A.
Leaf Node (Nút lá): Các nút nằm ở tận cùng, không có bất kỳ nút con nào (Node D, E, F).
Depth (Độ sâu của 1 nút): Số cạnh tính từ Root tới nút đó. (Depth của D = 2).
Height (Chiều cao của cây): Độ sâu lớn nhất của một nút lá bất kỳ. (Chiều cao cây trên = 2).
Subtree (Cây con): Bất kỳ nút nào kết hợp với các thế hệ con cháu phía dưới nó đều tạo thành một cây con độc lập.
Cây nhị phân là mô hình cây đặc biệt trong đó mỗi nút có tối đa 2 nút con (thường gọi là Left Child và Right Child).
BST là cây nhị phân được bổ sung quy tắc sắp xếp vị trí cho mọi nút:
Tất cả các nút thuộc Cây con bên trái (Left Subtree) phải có giá trị nhỏ hơn Nút cha.
Tất cả các nút thuộc Cây con bên phải (Right Subtree) phải có giá trị lớn hơn Nút cha.
[ 50 ]
/ \
[ 30 ] [ 70 ]
/ \ / \
[ 20 ] [ 40 ] [60] [80]
Tìm kiếm / Thêm / Xóa:
Trường hợp cân bằng (Cây lý tưởng): $O(\log N)$ (Mỗi bước loại bỏ được 50% số nút, tương tự Binary Search).
Trường hợp suy hao (Cây lệch thành Danh sách liên kết): $O(N)$ (Xảy ra khi chèn dãy số đã sắp xếp tăng dần $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$).
Lưu ý: Để giải quyết trường hợp suy hao $O(N)$, người ta sử dụng các mô hình Cây tự cân bằng như AVL Tree hoặc Red-Black Tree (nền tảng của các CSDL hiện đại).