Cây đỏ đen có phải là cấu trúc dữ liệu lý tưởng của tôi không?

Question

Tôi có một bộ sưu tập các mặt hàng (hợp lý lớn) mà tôi sẽ được xử lý. Trong mỗi trường hợp, quá trình xử lý sẽ bao gồm việc xóa mục nhỏ nhất trong bộ sưu tập, thực hiện một số công việc và sau đó thêm 0-2 mục mới (sẽ luôn lớn hơn mục đã xóa). Bộ sưu tập sẽ được khởi tạo với một mục và công việc sẽ tiếp tục cho đến khi nó trống. Tôi không chắc chắn kích thước bộ sưu tập có khả năng đạt được, nhưng tôi mong đợi trong phạm vi các mục 1M-100M. Tôi sẽ không cần phải tìm bất kỳ mục nào khác ngoài mục nhỏ nhất.

Tôi hiện đang có kế hoạch sử dụng cây đỏ đen, có thể được điều chỉnh để giữ con trỏ đến mục nhỏ nhất. Tuy nhiên tôi chưa bao giờ sử dụng một cái trước đây, và tôi không chắc liệu mô hình sử dụng của tôi có phù hợp với đặc điểm của nó hay không.

1) Có nguy cơ khi xóa mô hình chèn trái + ngẫu nhiên sẽ ảnh hưởng đến hiệu suất, ví dụ bằng cách yêu cầu số lần quay cao hơn đáng kể so với xóa ngẫu nhiên? Hoặc sẽ xóa và chèn các hoạt động vẫn là O (log n) với mẫu sử dụng này?

2) Một số cấu trúc dữ liệu khác sẽ cho tôi hiệu suất tốt hơn, do mô hình xóa hoặc lợi dụng thực tế tôi chỉ cần tìm mục nhỏ nhất?

Cập nhật: vui lòng tôi hỏi, đống nhị phân rõ ràng là giải pháp tốt hơn cho trường hợp này, và như đã hứa hóa ra rất dễ thực hiện.

Hugo

Answer 1

A binary heap tốt hơn rất nhiều cho những gì bạn muốn. Việc triển khai và nhanh hơn dễ dàng hơn vì bạn chỉ quan tâm đến việc xác định phần tử nhỏ nhất và chèn vào. Định vị phần tử nhỏ nhất là O (1), loại bỏ nó là O (log N), và chèn cũng là O (log N).

Answer 2

Một đống sẽ cung cấp cho bạn O (1) O (log n) loại bỏ và O (log n) chèn, và là nhiều dễ thực hiện hơn so với một cây đỏ-đen

Answer 3

Bạn nên biết cách tạo cấu trúc dữ liệu phức tạp hơn nếu cần. Tuy nhiên, nói chung đặt cược tốt nhất của bạn là bắt đầu đơn giản như bạn có thể, và chỉ sử dụng một cái gì đó phức tạp hơn khi nó quay ra bạn cần.

Thời gian duy nhất tôi từng thực hiện một cây tự cân bằng là một lần khi tôi tình cờ biết rằng cây của tôi sẽ rất lớn (hơn 10.000 nguyên tố), và dữ liệu sẽ đi vào những nhánh được sắp xếp. Điều đó có nghĩa là nếu tôi đã sử dụng một cây nhị phân bình thường, tôi sẽ kết thúc với gần như một danh sách liên kết.

Nếu dữ liệu của bạn được nhập theo thứ tự ngẫu nhiên, bạn thực sự không nên bận tâm với thuật toán cân bằng.