Tôi muốn biết điều gì là tốt nhất: Mảng hoặc cây tìm kiếm nhị phân trong (chèn, xóa, tìm tối đa và tối thiểu) và làm cách nào tôi có thể cải thiện cả hai?Sự khác nhau giữa cây tìm kiếm và cây nhị phân hiệu quả là gì?
An mảng cho phép random access cho từng phần tử trong đó. do đó bạn có được chèn, xóa và tìm kiếm một phần tử cụ thể trong O(1) và tối đa/phút, xóa trong O(n). [bạn cũng có thể đặt tối đa/phút O(1) và xóa O(n) thay thế]. Nếu bạn sắp xếp mảng của mình, nó sẽ khiến chèn/xóa là O(n), nhưng bạn sẽ nhận được O(logn) tìm và O(1) phút/tối đa.
Một BST được sắp xếp theo định nghĩa, và cho một thường xuyên [không cân bằng] BST, bạn sẽ có được O(n) hành vi trường hợp xấu nhất. Đối với cân bằng BST, bạn nhận được O(logn) chèn/xóa/tìm. Bạn có thể nhận được O(1) phút/tối đa bất kỳ cách nào cho cả hai.
Mảng cũng thường nhanh hơn để iterate [giả định thứ tự lặp lại không quan trọng] vì bạn có hiệu suất tốt hơn cache. Ngoài ra, không giống như BST - có kích thước không bị chặn bởi tự nhiên, một mảng yêu cầu phân bổ lại và sao chép dữ liệu khi mảng của bạn đầy.
Cải thiện BST có thể được thực hiện bằng cách đặt số balanced - như AVL hoặc red-black-trees.
Cái nào tốt hơn? Nó phụ thuộc vào ứng dụng. Thông thường khi bạn đang có kế hoạch chèn dữ liệu và giữ cho nó được sắp xếp, BST sẽ được ưu tiên hơn. Nếu truy cập ngẫu nhiên hoặc lặp lại là mục đích chính: bạn thường sử dụng một mảng.
Tại sao hoạt động liên tục 'findMin/findMax' 'O (1)' cho BST cân bằng? – Cratylus
@ user384706: Bất cứ khi nào bạn chèn/loại bỏ một phần tử từ một BST cân bằng, nó là 'O (logn)' và 'O (n)' cho BST không cân bằng. Bạn có thể duy trì thêm các con trỏ 'min' và' max', mà sẽ chỉ được sửa đổi khi bạn chèn/remvoe các phần tử từ BST. Tìm tối đa/tối thiểu mới là 'O (logn)' cho BST cân bằng và 'O (n)' không cân bằng - do đó không có tổn thất hiệu năng [lớn O] trong hoạt động này, và về O lớn, bạn có thể duy trì các con trỏ này cho "miễn phí" – amit
Ah, vì vậy bạn có nghĩa là sử dụng các con trỏ thừa. Nhưng trong trường hợp này, đây là một tối ưu hóa không liên quan trực tiếp đến các thuật toán BST.Đó không phải là nó hơi không nhất quán/gây nhầm lẫn để yêu cầu so sánh với cấu trúc dữ liệu khác (trong trường hợp này là một mảng) rằng 'max/min' là' O (1) 'vì nó không phải là mặc định? Người ta phải thực hiện nó sao cho nó là – Cratylus
Performance so sánh Mảng và cây tìm kiếm nhị phân:
Array Binary search tree
Unsorted Sorted Average Worst case
Space O(n) O(n) O(n) O(n)
Search O(n) O(log n) * O(log n) O(n)
Max/Min O(n) O(1) O(1) ** O(1) **
Insert O(1) O(n) O(log n) O(n)
Delete O(1) O(n) O(log n) O(n)
* giả nhị phân tìm kiếm
** đòi hỏi gợi ý thêm để chuẩn tối thiểu và tối đa, nếu không nó là O (log n)
Tại sao 'O (1)' tìm tối đa/phút của BST? – Cratylus
Bây giờ bạn hỏi, tôi không chắc nó có đúng không. Cây nhị phân tìm kiếm được sắp xếp theo định nghĩa, nhưng (tùy thuộc vào việc thực hiện?) Nó có thể không thể có được min/max trong O (1). Trong trường hợp đó, nó sẽ là O (log n) thay thế. – Peladao
Nó không phải là 'O (1)' trừ khi thực hiện của bạn giữ một con trỏ đến 'min' và' max' values.Check cũng bình luận trong câu trả lời của amit – Cratylus
Bạn thử tìm kiếm thông tin này? Nó phải dễ tìm. – Howard
Bạn có nghĩa là cấu trúc dữ liệu trừu tượng [danh sách liên kết] (http://en.wikipedia.org/wiki/Linked_list) và [cây tìm kiếm nhị phân] (http://en.wikipedia.org/wiki/Binary_search_tree)? – Gumbo
cải thiện theo cách nào? tốt nhất cho cái gì? đó là những cấu trúc dữ liệu hoàn toàn khác nhau, và mỗi cấu trúc có thể là 'tốt nhất' cho một ứng dụng nhất định. – amit