Triển khai cây nhị phân Python
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 Show
Các loại cây nhị phân1. 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ảoCâ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ỉnhCâ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
Để 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ênCâ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ằngNó 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ânMộ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à 1 cho các hoạt động tìm kiếm, chèn, cập nhật và xóa. 2 nhanh hơn nhiều so với thời gian tuyến tính 3 cần thiết để tìm các phần tử trong một mảng chưa sắp xếp. Nhiều cơ sở dữ liệu sản xuất phổ biến như PostgreSQL và MySQL sử dụng cây nhị phân để tăng tốc hoạt động CRUDƯu điểm của BST 🔗
Nhược điểm của BST 🔗
Nhận một công việc back-end mà không cần chi 10 nghìn đô la cho bootcamp
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 7 mà thay vào đó chỉ là lớp 8. Cây nhị phân thực sự chỉ là một con trỏ tới một nút gốc mà lần lượt kết nối với từng nút con, vì vậy chúng tôi sẽ chạy với ý tưởng đóĐầ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 9. Chúng tôi cũng sẽ khởi tạo cả hai nút con của nút mới thành 9Bướ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
Phương pháp chèn như sau 2Nếu nút chưa có giá trị, chúng ta chỉ cần đặt giá trị đã cho và 21. Nếu chúng tôi cố gắng chèn một giá trị cũng tồn tại, chúng tôi cũng có thể chỉ cần quay lại vì điều này có thể được coi là "no-op". Nếu giá trị đã cho nhỏ hơn giá trị nút của chúng ta và chúng ta đã có một con bên trái thì chúng ta gọi đệ quy 22 trên con bên trái của chúng ta. Nếu chúng ta chưa có con trái thì chúng ta chỉ tạo giá trị đã cho cho con trái mới của mình. Chúng ta có thể làm tương tự (nhưng đảo ngược) cho phía bên phải của mìnhBước 3 - Nhận tối thiểu và nhận tối đa 🔗 5 23 và 24 là các hàm trợ giúp hữu ích và chúng rất dễ viết. Chúng là các hàm đệ quy đơn giản duyệt qua các cạnh của cây để tìm các giá trị nhỏ nhất hoặc lớn nhất được lưu trữ trong đóBước 4 - Xóa 🔗 8Thao 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à 25 hoặc 26 thành 9Bướ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ề 28 hoặc 29 tùy thuộc vào việc giá trị đã cho đã tồn tại trong cây hay chưa 4Bướ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 50 in các giá trị trong cây theo thứ tự các khóa của chúng 6Bước 7 - Đặt trước 🔗 7Bước 8 - Đặt hàng sau 🔗 8Sử dụng BST 🔗 9Cây tìm kiếm nhị phân đầy đủ trong Python 🔗 0Bạ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 51Có 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
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à 3 khi được sử dụng để tìm kiếm một phần tử cụ thể - điều đó khá tệ. Danh sách được liên kết vượt trội trong việc loại bỏ và chèn các phần tử vào giữa danh sách một cách nhanh chóng |