Tại sao độ phức tạp của container bản đồ C++ STL O (log (n))?

Question

Đối với các thùng chứa C++ STL như vector và list, sự phức tạp của việc tìm kiếm các yếu tố và chèn hoặc loại bỏ chúng là tự giải thích. Tuy nhiên, đối với các container map, mặc dù tôi biết từ đọc của tôi rằng truy cập và chèn phức tạp/hiệu suất là O (log (n)), tôi không thể làm việc ra lý do tại sao. Tôi rõ ràng không hiểu bản đồ nhiều như tôi cần, vì vậy một số giác ngộ về chủ đề này sẽ được rất nhiều đánh giá cao.

Answer 1

Các yếu tố của bản đồ hoặc tập hợp được chứa trong cấu trúc cây; mỗi lần bạn kiểm tra một nút của cây, bạn xác định xem phần tử bạn đang cố gắng tìm/chèn có nhỏ hơn hoặc lớn hơn nút hay không. Số lần bạn cần thực hiện điều này (đối với cây cân đối đúng) là log2 (N) vì mỗi lần so sánh sẽ loại bỏ một nửa khả năng.

Answer 2

Khi slavik262 điểm, bản đồ thường được thực hiện với các cây đỏ đen, tự cân bằng. Kiểm tra độ phức tạp của cây đỏ-đen chẳng hạn như trong wikipedia Tôi không biết bất kỳ việc triển khai bản đồ nào với cây nhị phân; nếu Mark Ransom biết một, tôi sẽ rất vui khi biết cái nào.