Tree & Binary Search Tree (Day 38) | FE Master

Tree là một Graph không có vòng tròn (Cycle) và liên thông. Cấu trúc thư mục trong máy tính chính là Tree.

Mỗi cha chỉ có tối đa 2 con (Con Trái và Con Phải).

Quy tắc Vàng của BST:

graph TD 10((10)) --> 5((5)) 10 --> 15((15)) 5 --> 2((2)) 5 --> 7((7)) 15 --> 12((12)) 15 --> 20((20))

Ví dụ: Tìm số 12.

So với Gốc (10): 12 > 10 -> Đi sang Phải. (Bỏ luôn nửa trái 5,2,7 - Tiết kiệm 50% thời gian).
Gặp 15: 12 < 15 -> Đi sang Trái.
Gặp 12: BINGO!

Độ phức tạp tìm kiếm: Trung bình O(log N). Nhưng nếu cây bị lệch (như cái list thẳng tuột) thì thành O(N).

Có 3 cách đi hết các nút trong cây. Đề thi sẽ cho hình cây và hỏi thứ tự in ra.

Pre-order (Tiền thứ tự): Gốc -> Trái -> Phải. (Dùng để Copy cây).
VD: 10, 5, 2, 7, 15, 12, 20.
In-order (Trung thứ tự): Trái -> Gốc -> Phải.
VD: 2, 5, 7, 10, 12, 15, 20.
👉 Đặc biệt: In-order của BST luôn tạo ra dãy số tăng dần!
Post-order (Hậu thứ tự): Trái -> Phải -> Gốc. (Dùng để Xóa cây - Xóa con trước rồi mới xóa cha).
VD: 2, 7, 5, 12, 20, 15, 10.