Binary Search Tree (BST) – Cây tìm kiếm nhị phân 🌳

1. Binary Search Tree là gì? 🤔

Binary Search Tree (BST) hay Cây tìm kiếm nhị phân là một dạng cây nhị phân đặc biệt, trong đó:

Mọi node ở cây con bên trái đều có giá trị nhỏ hơn node hiện tại. Mọi node ở cây con bên phải đều có giá trị lớn hơn node hiện tại.

Nhờ tính chất này, việc tìm kiếm dữ liệu trở nên rất nhanh.

2. Ví dụ về BST 🧩

Với node 8:

Các số bên trái 8 đều nhỏ hơn 8

Các số bên phải 8 đều lớn hơn 8

Và quy tắc đó đúng với mọi node trong cây. 🌳

3. Tại sao BST quan trọng? 🚀

BST hỗ trợ rất hiệu quả các thao tác:

• Tìm kiếm

• Thêm phần tử

• Xóa phần tử

Độ phức tạp trung bình:

O(log n) 📈

Nhanh hơn nhiều so với tìm kiếm tuyến tính trên mảng.

So sánh: 📊

• Số phần tử: 10 Tìm kiếm tuyến tính: 5 lần lặp BST: 4 lần lặp

• Số phần tử: 100 Tìm kiếm tuyến tính: 50 lần lặp BST: 7 lần lặp

• Số phần tử: 1000 Tìm kiếm tuyến tính: 500 lần lặp BST: 10 lần lặp

• Số phần tử: 1000000 😵 Tìm kiếm tuyến tính: 500000 lần lặp BST: 20 lần lặp 🤯

4. Tổng kết 🎯

BST (Binary Search Tree) là một cấu trúc tìm kiếm dạng cây cực kỳ hữu dụng (dễ cài đặt 🛠️, tìm kiếm nhanh ⚡). Hiểu rõ BST sẽ giúp cho rất nhiều bài code sau này.

https://en.wikipedia.org/wiki/Binarysearchtree