05. Trees (Cây)

🎯 Mục tiêu học tập

Hiểu cấu trúc cây và terminologies
Cài đặt Binary Tree và Binary Search Tree
Thuật toán duyệt cây (Traversal)
Ứng dụng cây vào bài toán thực tế

📚 Lý thuyết cơ bản

Tree là gì?

Định nghĩa: Cấu trúc dữ liệu phân cấp gồm các nodes liên kết theo mối quan hệ cha-con.

Terminologies:

Root: Node gốc (không có parent)
Leaf: Node lá (không có children)
Parent/Child: Mối quan hệ cha-con
Siblings: Các node cùng parent
Depth: Khoảng cách từ root đến node
Height: Khoảng cách từ node đến leaf xa nhất
Subtree: Cây con

🌳 Các loại Tree

1. Binary Tree

Mỗi node tối đa 2 children (left, right)
Full Binary Tree: Mỗi node có 0 hoặc 2 children
Complete Binary Tree: Tất cả levels đầy, trừ level cuối (fill từ trái)
Perfect Binary Tree: Tất cả levels đầy

2. Binary Search Tree (BST)

Left subtree < Node < Right subtree
Search, insert, delete: O(log n) trung bình

3. Balanced Trees

AVL Tree: Self-balancing BST
Red-Black Tree: Balanced BST với màu
B-Tree: Multi-way tree (databases)

🔄 Tree Traversal

1. Depth-First Search (DFS)

// Inorder: Left → Root → Right
// Preorder: Root → Left → Right  
// Postorder: Left → Right → Root

2. Breadth-First Search (BFS)

// Level Order: Dùng Queue

📋 Bài tập thực hành

Implement Binary Tree
Tree traversals (4 loại)
Binary Search Tree operations
Find height, diameter of tree
Lowest Common Ancestor (LCA)

🚀 Chuẩn bị code

mkdir 05-trees
# Files: BinaryTree.java, BST.java, TreeTraversal.java, TreeProblems.java

« Previous Next »