Có mô-đun cho AVL hoặc Đỏ-Đen hoặc một số loại khác của cây nhị phân cân bằng trong thư viện chuẩn của Python không? Tôi đã cố gắng để tìm một, nhưng không thành công (Tôi là tương đối mới với Python).Thư viện chuẩn của Python - có mô-đun cho cây nhị phân cân bằng không?
Không, không có cây nhị phân cân bằng trong stdlib. Tuy nhiên, từ nhận xét của bạn, có vẻ như bạn có thể có một số tùy chọn khác:
O(log n). Nếu tìm kiếm là tất cả những gì bạn cần và dữ liệu của bạn đã được sắp xếp, mô-đun bisect cung cấp thuật toán tìm kiếm nhị phân cho danh sách.Nếu không có giải pháp nào phù hợp với bạn, bạn sẽ phải chuyển sang mô-đun bên thứ ba hoặc triển khai mô-đun của riêng bạn.
Cảm ơn bạn rất nhiều! Sử dụng một bộ giải quyết vấn đề của tôi. Tôi không có ý tưởng họ có O (1) tra cứu trong Python (tôi đã luôn luôn nghĩ rằng toàn bộ thiết lập nên được đi qua trước khi tìm đúng giá trị - nhưng như tôi đã nói, tôi mới đến Python). Cảm ơn bạn cũng cho lời giải thích của bạn cho các cấu trúc dữ liệu thông thường trong Python. – aeter
có gì thuộc loại này trong stdlib, as far as I can see, nhưng quick look at pypi brings up a few alternative:
Ngoài ra còn có một thực thi nhanh như C nhưng tinh khiết-Python được gọi là [linkedcontainers] (http://www.grantjenks.com/docs/sortedcontainers /) Các tài liệu có [so sánh hiệu suất] tốt (http://www.grantjenks.com/docs/sortedcontainers/performance.html) với các lựa chọn thay thế mà bạn liệt kê. – GrantJ
Không, nhưng có AVL Tree Objects for Python và (rất cũ!) một dự án (đóng) trên SourceForge - avl-trees for Python.
Đã có một vài trường hợp tôi tìm thấy heapq package (trong thư viện stadndard) hữu ích, đặc biệt là tại bất kỳ thời điểm nào bạn muốn O (1) thời gian truy cập vào phần tử nhỏ nhất trong bộ sưu tập của bạn.
Đối với tôi, tôi đã theo dõi bộ sưu tập bộ hẹn giờ và thường chỉ quan tâm đến việc kiểm tra xem thời gian nhỏ nhất (lần thực hiện đầu tiên) đã sẵn sàng để đi chưa.
Có một gói mới có tên "bintrees" hỗ trợ cây ubalanced, AVL và RB. Bạn có thể tìm thấy nó here.
Tôi đã cài đặt mô-đun bintrees (2.0.1), nhưng khi tôi nhập nó, tôi nhận được thông báo: 'Cảnh báo: FastBinaryTree không có sẵn, sử dụng phiên bản Python BinaryTree.' Bất kỳ ý tưởng nào để sửa lỗi này? Tôi đã cài đặt Cython, nhưng nó vẫn cho lỗi đó khi nhập. – yaraju
Xin lỗi, không có ý tưởng: ( –
Tôi đã tìm ra - Trên Windows, các phiên bản FastXTree cần một trình biên dịch C được cài đặt như MSVC hoặc Mingw32. Tôi chưa thử nó - vì tôi sẽ triển khai một cây tùy chỉnh – yaraju
Kiểm tra dự án Sorted Containers.
Đây là một PyCon nói về nó: https://www.youtube.com/watch?v=7z2Ki44Vs4E
Tôi chỉ sử dụng bộ hoặc từ điển. Nếu tôi cần sử dụng một thói quen băm tốt hơn, tôi định nghĩa '__hash __()'. Bạn có cần một cái gì đó fancier? Nếu vậy, tại sao? BTW, nếu bạn không thể tìm thấy nó trong docs.python.org, nó có lẽ không phải là một mô-đun chuẩn. –
@Mike - Tôi đang cố gắng giải quyết một nhiệm vụ từ Project Euler. Tôi nghĩ rằng việc sử dụng cây tìm kiếm nhị phân thay vì danh sách cho một trong các vùng chứa dữ liệu của tôi sẽ tăng tốc độ thuật toán với tỷ lệ logarit (vì các tìm kiếm O (logn)) sẽ giải quyết tác vụ mà không làm nóng máy tính của tôi. Ngoài ra, tôi chỉ tò mò về nó. – aeter
Điều gì về một bộ anh ta cho O (1) tra cứu – Mark