Trình trực quan hóa cây tìm kiếm nhị phân

Cách dùng

1. 1 Nhập một số và nhấn Insert để thêm vào cây — quan sát quá trình tìm vị trí thích hợp cho nó.
2. 2 Nhấn Search để theo dõi đường đi tới một giá trị, hoặc Delete để xóa một giá trị.
3. 3 Dùng Random để chèn một giá trị ngẫu nhiên, hoặc Clear để bắt đầu lại từ đầu.
4. 4 Lùi lại và tiến tới qua từng bước của mỗi thao tác, đồng thời theo dõi phần mã giả được tô sáng tương ứng.

Vì sao dùng công cụ này

• Thấy rõ quy tắc của BST đang hoạt động: giá trị nhỏ hơn đi sang trái, giá trị lớn hơn đi sang phải.
• Quan sát cả ba trường hợp xóa nút — nút lá, nút có một con, và nút có hai con (dùng nút kế tiếp theo thứ tự - in-order successor).
• Hiểu vì sao một BST cân bằng cho độ phức tạp tìm kiếm O(log n), còn cây mất cân bằng sẽ suy biến thành O(n).
• Chạy hoàn toàn trên trình duyệt của bạn. Không cần đăng ký, không cần tải file lên.

Câu hỏi thường gặp

Trình trực quan hóa cây tìm kiếm nhị phân là gì?

Trình trực quan hóa cây tìm kiếm nhị phân (Binary Search Tree Visualizer) là công cụ tương tác minh họa động các thao tác chèn, tìm kiếm và xóa trên một BST — cây nhị phân mà mọi cây con bên trái chứa các giá trị nhỏ hơn và mọi cây con bên phải chứa các giá trị lớn hơn. Công cụ hiển thị đường đi duyệt cho từng thao tác cùng cả ba trường hợp xóa nút.

Tính năng

Ví dụ

insert 5, 3, 8, 1

5 (root); 3 ← left of 5; 8 → right of 5; 1 ← left of 3

Trường hợp sử dụng

1. 1

   Học các thao tác trên cây

   Xem cách chèn và tìm kiếm tuân theo tính chất thứ tự của BST.

2. 2

   Vì sao cân bằng lại quan trọng

   Quan sát các lần chèn theo thứ tự đã sắp xếp làm cây suy biến thành O(n) và lý giải vì sao cần cây AVL/đỏ-đen.

3. 3

   Duyệt cây theo thứ tự giữa (in-order)

   Hiểu cách duyệt in-order cho ra các khóa đã được sắp xếp.

Tài liệu tham khảo

• MIT OCW 6.006 — Introduction to Algorithms (CLRS) — MIT OpenCourseWare
• VisuAlgo — Binary Search Tree — VisuAlgo (NUS)
• Binary search tree — Wikipedia

Công cụ liên quan