Cây nhị phân là cấu trúc dữ liệu dạng cây trong đó mỗi nút cha có thể có nhiều nhất hai nút con. Mỗi nút của cây nhị phân bao gồm ba mục
mục dữ liệu
địa chỉ của đứa con bên trái
địa chỉ của đứa trẻ bên phải
Các loại cây nhị phân
1. Cây nhị phân đầy đủ
Cây nhị phân đầy đủ là một loại cây nhị phân đặc biệt trong đó mọi nút cha/nút bên trong đều có hai hoặc không có con
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân đầy đủ
2. Cây nhị phân hoàn hảo
Cây nhị phân hoàn hảo là loại cây nhị phân trong đó mỗi nút trong có đúng hai nút con và tất cả các nút lá đều ở cùng cấp
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân hoàn hảo
3. Cây nhị phân hoàn chỉnh
Cây nhị phân hoàn chỉnh giống như cây nhị phân đầy đủ, nhưng có hai điểm khác biệt chính
- Mọi cấp độ phải được điền đầy đủ
- Tất cả các phần tử lá phải nghiêng về bên trái
- Phần tử chiếc lá cuối cùng có thể không có anh chị em bên phải i. e. một cây nhị phân hoàn chỉnh không nhất thiết phải là một cây nhị phân đầy đủ
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân hoàn chỉnh
4. Cây thoái hóa hoặc bệnh lý
Cây thoái hóa, bệnh lý là cây chỉ có một con trái hoặc phải
5. Cây nhị phân xiên
Cây nhị phân lệch là cây bệnh lý/thoái hóa trong đó cây bị chi phối bởi các nút bên trái hoặc các nút bên phải. Như vậy, có hai loại cây nhị phân lệch. cây nhị phân lệch trái và cây nhị phân lệch phải
6. Cây nhị phân cân bằng
Nó là một loại cây nhị phân trong đó chênh lệch giữa chiều cao của cây con bên trái và bên phải cho mỗi nút là 0 hoặc 1
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân cân bằng
Biểu diễn cây nhị phân
Một nút của cây nhị phân được biểu diễn bằng một cấu trúc chứa một phần dữ liệu và hai con trỏ tới các cấu trúc khác cùng loại
Cây tìm kiếm nhị phân, viết tắt là BST, là một cây trong đó mỗi nút là một giá trị lớn hơn tất cả các nút con bên trái của nó và nhỏ hơn tất cả các nút con bên phải của nó. Đọc tiếp để triển khai cây tìm kiếm nhị phân trong Python từ đầu
Ngoài ra, nếu bạn quan tâm đến việc học cấu trúc dữ liệu Python từ đầu, hãy xem các khóa học Tìm hiểu Python và Tìm hiểu thuật toán của tôi trên Boot. nhà phát triển
Tại sao tôi lại sử dụng cây tìm kiếm nhị phân?
Cây nhị phân rất hữu ích để lưu trữ dữ liệu một cách có tổ chức để có thể nhanh chóng truy xuất, chèn, cập nhật và xóa. Sự sắp xếp các nút này cho phép mỗi phép so sánh bỏ qua khoảng một nửa phần còn lại của cây, do đó, toàn bộ thao tác diễn ra nhanh như chớp
Nói một cách chính xác, cây tìm kiếm nhị phân cung cấp độ phức tạp Big-O trung bình là
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Ưu điểm của BST 🔗
- Khi được cân bằng, BST cung cấp các thao tác chèn, xóa và tra cứu
1 nhanh như chớp10 10 / \ Insert 5 / \ 2 60 ---------> 2 60 / \ / \ 1 3 1 3 \ 5 - Cây tìm kiếm nhị phân rất đơn giản để thực hiện. Một BST bình thường, không giống như cây đỏ đen cân bằng, cần rất ít mã để chạy
Nhược điểm của BST 🔗
- Chậm cho một tìm kiếm vũ phu. Nếu bạn cần lặp lại từng nút, bạn có thể thành công hơn với một mảng
- Khi cây trở nên mất cân bằng, tất cả các hoạt động của
1 nhanh chóng suy giảm thành10 10 / \ Insert 5 / \ 2 60 ---------> 2 60 / \ / \ 1 3 1 3 \ 5
310 10 / \ Insert 5 / \ 2 60 ---------> 2 60 / \ / \ 1 3 1 3 \ 5 - Vì các con trỏ tới toàn bộ đối tượng thường có liên quan, BST có thể yêu cầu bộ nhớ nhiều hơn một chút so với mảng, mặc dù điều này phụ thuộc vào việc triển khai
Nhận một công việc back-end mà không cần chi 10 nghìn đô la cho bootcamp
- Tìm hiểu Python, Javascript và Go
- Xây dựng các dự án chuyên nghiệp mà bạn cần để có được công việc đầu tiên
- Dành khoảng 6 tháng [khi làm bán thời gian]
- Giá thấp tới $24/tháng*
- Không mạo hiểm. Hủy bỏ bất cứ lúc nào
Triển khai cây B trong Python 🔗
Bước 1 - Lớp BSTNode 🔗
Việc triển khai của chúng tôi sẽ không sử dụng lớp
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Đầu tiên, chúng ta tạo một constructor
________số 8
Chúng tôi sẽ cho phép cung cấp một giá trị, cũng sẽ đóng vai trò là khóa. Nếu một cái không được cung cấp, chúng tôi sẽ chỉ đặt nó thành
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bước 2 - Chèn 🔗
Chúng ta cần một cách để chèn dữ liệu mới vào cây. Việc chèn một nút mới sẽ nối nó dưới dạng một nút lá ở vị trí thích hợp
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Phương pháp chèn như sau
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Nếu nút chưa có giá trị, chúng ta chỉ cần đặt giá trị đã cho và
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bước 3 - Nhận tối thiểu và nhận tối đa 🔗
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bước 4 - Xóa 🔗
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Thao tác xóa là một trong những thao tác phức tạp hơn. Đây cũng là một hàm đệ quy, nhưng nó cũng trả về trạng thái mới của nút đã cho sau khi thực hiện thao tác xóa. Điều này cho phép cha mẹ có con đã bị xóa đặt đúng thành phần dữ liệu của nó là
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bước 5 - Tồn tại 🔗
Hàm tồn tại là một hàm đệ quy đơn giản khác trả về
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bước 6 - Đặt hàng 🔗
Thật hữu ích khi có thể in cây ở định dạng có thể đọc được. Phương thức
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bước 7 - Đặt trước 🔗
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bước 8 - Đặt hàng sau 🔗
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Sử dụng BST 🔗
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Cây tìm kiếm nhị phân đầy đủ trong Python 🔗
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Bạn sẽ sử dụng cây tìm kiếm nhị phân ở đâu trong đời thực?
Có nhiều ứng dụng của cây tìm kiếm nhị phân trong đời thực và một trong những trường hợp sử dụng phổ biến nhất là lưu trữ các chỉ mục và khóa trong cơ sở dữ liệu
Ví dụ: trong MySQL hoặc PostgreSQL khi bạn tạo một cột khóa chính, những gì bạn thực sự đang làm là tạo một cây nhị phân trong đó các khóa là các giá trị của cột và các nút đó trỏ đến các hàng cơ sở dữ liệu. Điều này cho phép ứng dụng dễ dàng tìm kiếm các hàng cơ sở dữ liệu bằng cách cung cấp khóa. Ví dụ: lấy bản ghi người dùng bằng khóa chính
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5
Có nhiều ứng dụng của cây tìm kiếm nhị phân trong đời thực và một trong những trường hợp sử dụng phổ biến nhất là lưu trữ các chỉ mục và khóa trong cơ sở dữ liệu
Ví dụ: khi bạn tạo một cột khóa chính trong MySQL hoặc PostgreSQL, bạn tạo một cây nhị phân trong đó các khóa là giá trị của cột và các nút trỏ đến các hàng cơ sở dữ liệu. Điều này cho phép ứng dụng dễ dàng tìm kiếm các hàng cơ sở dữ liệu bằng cách chỉ định một khóa, ví dụ: để tìm bản ghi người dùng bằng khóa chính email
sử dụng phổ biến khác bao gồm
- Thuật toán tìm đường trong trò chơi điện tử [A*] sử dụng BST
- Nén tệp bằng sơ đồ mã hóa Huffman sử dụng cây tìm kiếm nhị phân
- Tính toán kết xuất - Doom [1993] nổi tiếng là trò chơi đầu tiên sử dụng BST
- Trình biên dịch cho ngôn ngữ mã hóa cấp thấp phân tích cú pháp bằng BST
- Hầu hết mọi cơ sở dữ liệu tồn tại đều sử dụng BST để tra cứu chính
Sự khác biệt giữa Cây nhị phân và Danh sách được liên kết là gì?
Trong khi cây nhị phân và danh sách liên kết đều sử dụng con trỏ để theo dõi các nút, cây nhị phân hiệu quả hơn cho việc tìm kiếm. Trên thực tế, danh sách được liên kết là
10 10
/ \ Insert 5 / \
2 60 ---------> 2 60
/ \ / \
1 3 1 3
\
5