Có bất kỳ cây tìm kiếm nhị phân tự cân bằng nào (RED-BLACK, AVL hoặc các loại khác) được tích hợp sẵn trong Python 2.7 hoặc Python 3.x?Cây tìm kiếm nhị phân tích hợp trong Python?
Tôi đang tìm kiếm thứ gì đó tương đương với số TreeMap hoặc TreeSet của Java.
Nếu không có các trình cắm sẵn như vậy, tại sao chúng bị bỏ qua? Có lý do đặc biệt nào, vì không bao gồm các công cụ như vậy?
Không có lý do đặc biệt nào, với kiến thức của tôi - tôi đoán lý do là vì rất nhiều ứng dụng được điều chỉnh cao dict và set triển khai (là bảng băm) hoạt động tốt. Chúng đủ tốt trong hầu hết các trường hợp. Có những tình huống chắc chắn mà bạn cần các đặc tính hiệu suất của cây tìm kiếm nhị phân cân bằng (giống như truyền tải theo thứ tự dựa trên khóa - thay vì thứ tự bổ sung), nhưng chúng đủ xa con đường bị đánh đập khiến mọi người hài lòng với việc lấy gói của bên thứ ba trong trường hợp đó.
Tôi đã có trải nghiệm tốt khi sử dụng gói bintrees trên PyPI. Điều này có triển khai thực hiện các cây nhị phân không cân bằng, AVL và màu đỏ-đen, trong cả Python thuần túy và các phần mở rộng được viết trong Cython.
Tôi nghĩ rằng phần còn lại của lý do cơ bản là tai nạn lịch sử. Nếu người viết bintrees đã vận động để đưa nó vào stdlib, và sẵn sàng đưa ra những ràng buộc áp đặt cho việc bảo trì và giải phóng, nó có thể sẽ đi vào. (Mặc dù sự phụ thuộc của Cython sẽ gây ra vấn đề, tôi đoán là .)
thuật toán phức tạp:
đối với các bảng băm (như dicts hoặc bộ), chèn và tra cứu là O (1), trong khi đối với một cây cân bằng này là O (log (n)). Trong quá trình truyền các khóa là O (n) trong một cây, nhưng để làm điều tương tự với bảng băm, bạn cần phải sắp xếp các khóa đầu tiên, vì vậy nó là O (n * log (n)). Khi bạn chọn loại cấu trúc dữ liệu nào để sử dụng, bạn cần phải suy nghĩ về những hoạt động bạn sẽ sử dụng và chọn sự cân bằng có ý nghĩa nhất trong ứng dụng của bạn.
Điều này làm cho rất nhiều ý nghĩa. Tôi đoán rằng có lẽ 'dict' và' set' thực sự là cây tìm kiếm nhị phân, hoặc thậm chí có thể hiệu quả hơn. Tôi sẽ thực hiện một số nghiên cứu về cách thực hiện chính xác chúng. –
@ChirilaAlexandru: 'dict' và' set' là các bảng băm. –
@wilberforce: Tôi sẽ cho 'blist' một cơ hội tốt hơn để hạ cánh stdlib. Tôi nghĩ rằng nó thực sự được xem xét tại một số điểm, nhưng tôi không nhớ lại các chi tiết. –
Bạn sẽ không tìm thấy bất kỳ cây nào trong thư viện chuẩn. Python sử dụng nhiều từ điển là bảng băm cho nội bộ của nó (đối tượng, các lớp và các mô-đun đều dựa trên các dicts). Do đó dicts đã được tối ưu hóa rất nhiều. Điều này làm cho nhu cầu tìm kiếm cây nhỏ hơn nhiều. Ngoài ra để có hiệu quả cây như vậy đã được thực hiện trong một loại mở rộng.
Không có thư viện nào trong thư viện chuẩn. Tại sao một người không được bao gồm là không thể trả lời. Phần còn lại của câu hỏi của bạn là một yêu cầu cho các tài nguyên bên ngoài, đó là chủ đề ngoài chủ đề. –
Gần-dupe của http://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree –